Dân CNTT giúp đỡ

[MSW]

Mình cần nhờ một số cao thủ tin học giải giúp Tt này: Lập trình tìm số hình vuông có trong hình vuông diện tích NxN (cạnh = N) biét hình này được chia làm NxN ô vuông nhỏ????

[a2k46_bien]

lập trình C++ hay pascal bạn?

[EvenSteven]

Mấy cái này chú em lên các diễn đàn IT tìm còn nhanh hơn:))
Trông chờ vào ai

[Bạch Dương]

Thật ra đâu cần như vậy.
Tôi xin đề ra một giải thuật sau:
Hãy coi hình vuông này là tập hợp của các đường chéo.
Trên mỗi đg chéo, nếu ta lấy 2 ô vuông (k0 cần khác nhau) sẽ thu được một hình vuông. Như vậy tổng số HV có trong HV NxN ô vuông này sẽ bằng tổng số HV thu đc trên mỗi đg chéo trên.
Vậy, ta lập một lớp để tính số HV trên đg chéo
public sealed class Sum_S
{
public static void sum_S( )
{
this.n=n;
this.h = h;
this.f=f;
this.k=k;
this.a=a;
}
public static int sum( int n)
{
h = (n+1)*n/2;
return h;
}
//Phương thức này dùng để tính tổng HV
public static int thv (int k, int n)
{
for(int a=1; a<=n;a++)
{
int f=a;
Sum_S.sum(a);
a=a+f;
k=2a-(n*n+1/2);
}
return k;
}
public int a;
Public int k;
public int f;
public int h;
public int n;
}


Cuối cùng tạo một lớp sử dụng Phương thức Main để gọi tất cả các PT trên, việc này chắc không cần mất nhiều thời gian

[Vietnamnet.vn]

Khó hiểu. viết nốt đi

[trantiendat_a9k49]

bài này em hiểu chết liền

[Bạch Dương]

Phần còn lại như sau: ta lập một class tester để sử dụng các phương thức từ lớp Sum_S. (bạn có thể để sum_s đánh dấu là static hoặc nếu MSW muốn tạo đối tươgj hay ko thì..tuỳ)
public class nhap
{
public void nhap()
{
this.n = n
}
public int nhapn()
{
System.Console.WriteLine ("nhap n");
n = System.Console.ReadLine();
return n;
}
public int n;
}

public static class Sum_S
{
public void main()
{
Sum_S t= new Sum_S();
nhap n= new nhap();
int a= n.nhapn;
t.thv (a);
System.Console.WriteLine ("Vay so hv la: {0}";a);
}
}

BÀI NÀY CÓ THỂ CÒN NHIỀU SAI XÓT TRONG QUÁ TRÌNH VIẾT CHỮ MONG BẠN THÔNG CẢM, LÂU LẮM RỒI TÔI MỚI LÀM MẤY BÀI LT NÀY

[sasuke_kool]

sorry đã lật lại topic đã lâu, nhưng em muốn xem lời giải của em có đúng ko

uses crt;
var S:integer;
i,j,n:integer;
Begin
Write('nhap n: '); Readln(N);
if n=1 then S:=1
Else
begin
S:=N*N+1; { +1 là cái hình vuông to nh?t}
if N=2 then Write('so hv là: ',S)
else
begin
For i:=2 to N do
for j:=2 to N do
S:=S+1;



Write('so hv là: ',S);
end;
end;

Readln;
end.


Em chẳng biết kiểu thuật toán thía nào, đây là nhìn hình đoán qui luật :d

[sasuke_kool]

Thấy nó ra kết qua có vẻ khả quan nên post thử mợi người xem xét, đúng thanks hộ em một phát lấy khích lệ

[Bạch Dương]

Ý tưởng của em là khá thông minh. Ngay khi đọc bài, người ta đã hiểu em định làm gì. Em coi HV đó là trục tọa đọvwois i là chiều dài và j là chiều rộng, với mỗi i=j ta có một hình vuông, và cho 2 chỉ số này chạy rồi đếm hình
Nếu để ý kỹ em sẽ thấy lỗi sai của mình mà chưa cần xem kết quả
Em hãy nhìn câu lệnh
For i:=2 to N do
for j:=2 to N do
S:=S+1;

Ý tuởng của câu lệnh này là đếm. 2 vòng lặp lồng nhau I chạy từ 2 đến N, J chạy từ 2 đến N, thì S tăng một đơn vị. Ban đầu, người ta nghĩ đó là đúng. Nhưng thật ra ko phải vậy. Bởi lẽ với 2 vòng lặp lồng nhau như vậy, i chạy n-1 lần, j chạy n-1 lần, sẽ có tất cả (N-1)^2 lần tăng đơn vị

Vậy có thể thay cả đoạn lênh lặp dài và tốn quá nhiều dung lượng và thời gian kia chỉ bằng câu lệnh

S:=S+(N-1)^2 (!?)

Như vậy chả lẽ đáp án bài toán lại là S=N*N+1+(N-1)^2? Như thế thì cần gì viết chương trình

Đây là một bài toán tương đối đau đầu. nhưng không phải không có cách. làm sao để đếm đủ số hình vuông mà không xót cái nào?

Theo cách giải mà anh đưa ra:
Hãy coi hình vuông này là tập hợp của các đường chéo.
Trên mỗi đg chéo, nếu ta lấy 2 ô vuông (k0 cần khác nhau) sẽ thu được một hình vuông. Như vậy tổng số HV có trong HV lớn này sẽ bằng tổng số HV thu đc trên mỗi đg chéo trên.
Vậy, ta lập một lớp để tính số HV trên đg chéo

Trong pascal, hãy thay một lớp của C# bằng một hàm.
Em hãy quan sát thử bàn cờ vua, sẽ thấy có các đường chéo theo đường đi của quân Tịnh chạy từ ô đầu đến ô cuối cùng, cứ lấy hai ô trên mỗi đường chéo, ta thu được 1 hình vuông. Bằng cách đó có thể thu được tất cả các hình vuông trong toàn bàn cờ


Cách 2 hay hơn rất nhiều, nhưng người ta sẽ bắt phân tích thuật toán:

Với mỗi hình vuông cạnh NxN, ta thu được 1 hình vuông
Với mỗi hình vuông cạnh (N-1)x(N-1), ta thu được 4 hình vuông
Với mỗi hình vuông cạnh (N-2)x(N-2), ta thu được 9 hình vuông
...
Với mỗi hình vuông cạnh 2x2, ta thu được (N-1)^2 hình vuông
Với mỗi hình vuông cạnh 1x1, ta thu được N^2 hình vuông

Như vậy tổng số hình vuông sẽ bằng những con số thu được cộng lại

Chứng minh thuật toán này rất đơn giản, chỉ bằng những kiến thức hình học nhỏ. Em thử viết chương trình đi

[sasuke_kool]

S=N*N+1+(N-1)^2 đối với N=3,4,5...

[Thần Thoại]

Mấy cái này chú em lên các diễn đàn IT tìm còn nhanh hơn:))
Trông chờ vào ai

Đừng bao h nghi ngờ khả năng của BDHers rồi xem những người khác giỏi hơn mình, nếu bạn không giúp được thì đừng comment vào topic của người khác như thế và comment kiểu xem thường khả năng của BDHers như thế thì càng không nên

[sasuke_kool]

Ah đúng rùi,e nhầm/sai, Cách đường chéo của anh hay thiệt đấy.Thanks
-Giả sử đường chéo của hình vuông nhỏ nhất là 1 đv (là đường chéo của hv có cạnh =1)
Đơn giản là chỉ cần tính số đường chéo có chiều dài 2,3,.. và cộng số đường chéo lại
ta thấy trong hinh có: 1^2 đường chéo có độ dài N đv
2^2 ............................ N-1 đv
3^2 ............................ N-2 đv
...................................
(N-1)^2 ............................. 2 đv
N^2 ....................................1 đv
=> tổng số hình vuông là S=1+2^2+3^2+.....+N^2
dùng 1 vong for là xong: for i:=1 to N do S:=S+i*i;
Liệu cái bài lập phương có làm đc như thế này ko anh Đức Anh

[Bạch Dương]

Uhm. Đúng. Cách dđường chéo chỉ áp dụng trong không gian 2 chiều (mặt phẳng). Cách thứ hai sẽ áp dụng tổng quát hơn (kể cả với 4 chiều không gian: V = [v_t, v_x, v_y, v_z] = [v_t, v])
Tức là với hình lập phương, đếm lần lượt
Với mỗi hình LP cạnh NxN, ta thu được 1 hình LP
Với mỗi hình LP cạnh (N-1)x(N-1)x(N-1), ta thu được 8 hình LP
Với mỗi hình LP cạnh (N-2)x(N-2)x(N-2), ta thu được 27 hình LP
...
Với mỗi hình LP cạnh 2x2x2, ta thu được (N-1)^3 hình LP
Với mỗi hình LP cạnh 1x1x1, ta thu được N^3 hình LP

Vậy tổng số hình :LP tính là: N^3 + (N-1)^3 + (N-2)^3 + ... + 2^3+ 1

Để có điểm cao nhất thì bài này nên dùng đệ quy (chứ ko dùng vòng lặp)

Còn Bài C# trên nói về cách đường chéo của bàn cờ:
public sealed class Sum_S
{
public static void sum_S( )
{
this.n=n;
this.h = h;
this.f=f;
this.k=k;
this.a=a;
}
public static int sum( int n)
{
h = (n+1)*n/2;
return h;
}
//Phương thức này dùng để tính tổng HV
public static int thv (int k, int n)
{
for(int a=1; a<=n;a++)
{
int f=a;
Sum_S.sum(a);
a=a+f;
k=2a-(n*n+1/2);
}
return k;
}
public int a;
Public int k;
public int f;
public int h;
public int n;
}
Đó là lớp tính số hình vuông trên 1 đường chéo

Với không gian 3 chiều mà dùng cách chéo, em phải nghĩ đến "mặt phẳng chéo", như thế rất phức tạp

[Sponsored content]