(Lời giải của bạn Lê Thanh Tùng - Vĩnh Yên - Vĩnh Phúc)
Bài 65/2001 - Lưới ô vuông vô hạn
(Dành cho học sinh THCS và PTTH)
Program bai65;
uses crt;
var
a:array[1..100,1..100] of integer;
b,i,j,n,m,k:integer;
f:text;
t:boolean;
Begin
clrscr;
write('Nhap so n: '); readln(n);
write('Nhap so m: '); readln(m);
for i:=1 to m do
for j:=1 to n do a[i,j]:=-1;
for i:=m downto 1 do
for j:=1 to n do
begin
b:=-1;
repeat
inc(b); t:=true;
for k:=1 to n do if a[i,k]=b then t:=false; {kt hang}
for k:=1 to m do if a[k,j]=b then t:=false; {kt cot}
until t;
a[i,j]:=b;
end;
assign(f,'KQ.TXT');
rewrite(f);
for i:=1 to m do
begin
for j:=1 to n do write(f,a[i,j]:5);
writeln(f);
end;
close(f);
write('Mo file KQ.TXT de xem ket qua!');
readln;
END.
(Lời giải của bạn Nguyễn Trường Đức Trí)
Bài 66/2001 - Bảng số 9 x 9 (Dành cho học sinh Tiểu họcvà THCS)
Ta sẽ điền vào các ô ở cột thứ năm các số lớn nhất có thể được. Nếu số lớn nhất trong các cột còn lại (chưa điền vào bảng) là a, thì số lớn nhất có thể điền vào cột thứ năm là a- 4 vì các số phải điền theo thứ tự tăng dần theo hàng mà sau cột thứ 5 còn có 4 cột nữa. Ta thực hiện điền các số giảm dần từ 81 vào nửa phải của bảng trước, sau đó dễ dàng điền vào nửa còn lại với nhiều cách khác nhau:
-
1
|
2
|
3
|
4
|
77
|
78
|
79
|
80
|
81
|
5
|
6
|
7
|
8
|
72
|
73
|
74
|
75
|
76
|
9
|
10
|
11
|
12
|
67
|
68
|
69
|
70
|
71
|
13
|
14
|
15
|
16
|
62
|
63
|
64
|
65
|
66
|
17
|
18
|
19
|
20
|
57
|
58
|
59
|
60
|
61
|
21
|
22
|
23
|
24
|
52
|
53
|
54
|
55
|
56
|
25
|
26
|
27
|
28
|
47
|
48
|
49
|
50
|
51
|
29
|
30
|
31
|
32
|
42
|
43
|
44
|
45
|
46
|
33
|
34
|
35
|
36
|
37
|
38
|
39
|
40
|
41
|
Program bai66;
Uses ctr ;
Var i,j : integer ;
Begin
Clsscr;
for i:= 1 to do
begin
for j:= 1to 4 do write (4*(i-1) + j :3);
for j:= 0 to 4 do write (81-4*i-(i-1)+j :3) ;
Writeln;
end ;
Write (‘tong cac so o cot 5: ‘,(37+77)*9div2);
Readln
End.
(Lời giải của bạn Nguyễn Chí Thức - Lớp 11A1 - Khối PTCTT - ĐHSPHN - Thôn Đại Đồng - xã Thuỵ Phương - Từ Liêm - Hà Nội)
Bài 67/2001 - Về các phép biến đổi "Nhân 2 trừ 1" (Dành cho học sinh THCS và PTTH)
Để biến đổi ma trận A thành 0, ta biến đổi từng cột thành 0
Xét một cột bất kì có n số a1, ..., an (ai >= 0)
Đặt X = max(a1, ..., an).
- Bước 1:
+ Nếu dãy a1, ..., an có một số 0 và một số khác 0, dừng ở đây vì không thể đưa A về 0;
- Bước 2:
+ Nếu dãy a1, ..., an có ai = 0 (i = 1..n) thì cột này đã được biến đổi xong, qua cột tiếp theo,
+ Nếu không thì ai = 2ai nếu 2ai <= X (nhân hàng có chứa số ai lên 2), tiếp tục thực hiện đến khi không nhân được nữa, qua bước 3;
- Bước 3:
X:= X-1;
ai:= ai-1;
Quay lại bước 2.
Đây không phải là lời giải tốt ưu nhưng rất đơn giản, dễ dàng cài đặt (việc viết chương trình tương đối đơn giản)
Nhận xét: Bài này thực sự dễ nếu chỉ dừng lại ở mức tìm thuật toán? Nếu đặt lại điều kiện là có thể nhân hàng, cột cho 2, trừ hàng, cột cho 1, tìm lời giải tối ưu với giới hạn của M, N thì hay hơn nhiều.
(Lời giải của bạn Vũ Lê An - Lớp 11T2 - Lê Khiết - Quảng Ngãi)
Thuật toán của bạn Vũ Lê An rất đúng. Song trên thực tế thuật toán này còn một điểm chưa chuẩn vì nếu các số của mảng số thì nhỏ, số thì lớn thì thuật toán này mất rất nhiều bước. Việc nhân có thể gây ra tràn số.
Ví dụ:
2 3
1 100 1
100 1 100
số bước sẽ rất lớn.
Nhưng thuật toán này trên lý thuyết là giải được. Chương trình theo thuật toán trên.
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
program bai67_bien_doi_mang; {Author : Nguyen Van Chung}
uses crt;
const max =100;
fi ='bai67.inp';
fo ='bai67.out';
var a :array[1..max,1..max]of longint;
m,n :integer;
procedure docf;
var f :text;
i,j :integer;
begin
assign(f,fi);
reset(f);
read(f,m,n);
for i:=1 to m do
for j:=1 to n do read(f,a[i,j]);
close(f);
end;
procedure lam;
var f :text;
i,j,ma,mi,k :longint;
begin
assign(f,fo);
rewrite(f);
for j:=1 to n do
begin
ma:=0;mi:=maxlongint;
for i:=1 to m do
begin
if a[i,j]>ma then ma:=a[i,j];
if a[i,j]
end;
if (ma>0)and(mi=0) then
begin
rewrite(f);
writeln(f,'No solution');
break;
end;
repeat
for i:=1 to m do
begin
while a[i,j]*2<=ma do
begin
for k:=1 to n do a[i,k]:=a[i,k]*2;
writeln(f,'nhan 2 dong :',i);
end;
a[i,j]:=a[i,j]-1;
end;
dec(ma);
writeln(f,'tru 1 cot :',j);
until ma=0;
end;
close(f);
end;
BEGIN
docf;
lam;
END.
Bài 68/2001 - Hình tròn và bảng vuông
(Dành cho học sinh PTTH)
+ Tính số ô vuông bị cắt bởi hình tròn:
Nếu trục toạ độ là (0,0) thì tâm vòng tròng có toạ độ (n,n). Xét 1 phần 4 vòng tròn từ 6 giờ đến giờ ô bị cắt là ô có đỉnh (i,j) nằm ngoài vònh tròn và 1 đến 3 đỉnh (i+1, j), (i, j+1), (i+1, j+1) trong vòng tròn. Do tính đối xứng ta chỉ cần tính số ô của 1 phần 4 vòng tròn rồi nhân với 4. Tuy nhiên nếu nhận xét kĩ hơn ta thấy với n = 2, số ô bị cắt là 12, khi n tăng 1 đơn vị, số ô bị cắt tăng lên 8 ô. Do đó ta có thể tính thẳng số ô bị cắt bằng công thức : Số ô bị cắt =12 + (n-2)*8
+ Tính số ô nằm trong vòng tròn:
Cũng do tính đối xứng ta chỉ cần tính số ô nằm trong 1 phần 4 vòng tròn rồi nhân với 4, ô nằm trong vòng tròn khi tất cả 4 đỉnh nằm trong vòng tròn.
Chương trình Pascal
Uses Ctr;
Const S1 =’INPUT.TXT’;
S2=’OUTPUT.TXT’;
VarF1F2: text;
I,J,N : word;
Dem :longint;
FunctionTrong(X,Y: longint): boolean;
Begin
Trong:= 4*(sqr(X-N)+sqr(Y-N))<=sqr(2*N-1);
End
BEGIN
Clrscr;
Assign(F1,S1);
Reset(F1);
Assign(F2,S2);
Rewrite(F2);
While not eof(F1) do
Begin
Readln(F1,N);
Write(F2,’N=,’=>’,12+((N-2)*8));
Dem:= 0;
For I:= 0 to N-1 do
For J:= 0 to J-1 do
If Trong (I,J) and Trong (I+1,J) and Trong (I,J+1) and Trong (I+1, J+1) then(Dem)
Writeln(F2,’’,Dem*4);
End;
Close(F1);
Close(F2);
End.
(Lời giải của bạn Lâm Tấn Minh Tâm - 12 Tin trường PTTH Chuyên Tiền Giang- Tiền Giang)
Bài 69/2001 - Bội số của 36
(Dành cho học sinh Tiểu học)
Một số đồng thời chia hết cho 4 và 9 thì sẽ chia hết cho 36 (vì 4 và 9 nguyên tố cùng nhau: (4, 9) = 1).
Ta thấy, tổng của tất cả các số từ 1 đến 9 = 1 + 2 + ... + 9 = 45 chia hết cho 9.
Một số chia hết cho 4 khi và chỉ khi hai chữ số cuối cùng của nó chia hết cho 4. Mà ta cần tìm số nhỏ nhất chia hết cho 36, do đó số đó phải là số nhỏ nhất có đầy đủ các chữ số từ 1 đến 9 và hai số cuối cùng của nó phải là một số chia hết cho 4. Vậy số phải tìm là: 123457896
Bài 70/2001 - Mã hoá theo khoá
(Dành cho học sinh THCS và THPT)
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
uses crt;
Const MaxVal=256;
Var
n:Integer; S,KQ:String;
a:array[0..MaxVal] of Integer;
Procedure InPut;
Var i:Integer;
Begin
CLrscr;
Write('Nhap N=');Readln(n);
For i:=1 to n do
Begin Write('a[',i,']=');Readln(a[i]); End;
Write('Nhap Xau:');Readln(S);
End;
Procedure Main;
Var i,j:Integer;
Begin
if (Length(S) Mod n) <>0 then
For i:=1 to n-(Length(S) Mod n) do S:=S+' ';
KQ:='';
For i:=0 to (Length(S) Div n)-1 do
For j:=(n*i)+1 to n*(i+1) do
KQ:=KQ+S[a[j-(n*i)]+(n*i)];
Writeln('Xau Ma Hoa: ',KQ);
End;
Begin
InPut;
Main;
Readln;
End.
(Lời giải của bạn Nguyễn Cao Thắng - Lớp 12A2 chuyên Vĩnh Phúc - tỉnh Vĩnh Phúc)
Bài 71/2001 - Thực hiện phép nhân
Program Thuc_hien_phep_nhan;
Uses Crt;
Type so = 0..9;
Var a,b,c,d: string;
can,i: byte;
Procedure Nhap;
Begin
Clrscr;
Write('Nhap so a : '); Readln(a);
Write('Nhap so b : '); Readln(b);
Writeln('Phep nhan a va b : ');
can:=length(a)+length(b)+1;
Writeln(a:can);
Writeln('X');
Writeln(b:can);
For i:=1 to can do Write('-');
Writeln;
End;
Procedure Nhan(a: string; k: so);
Var nho: so;
x,i: byte;
Begin
nho:=0;
c:='';
For i:=length(a) downto 1 do
Begin
x:=(ord(a[i])-48)*k+nho;
nho:=x div 10;
c:=chr((x mod 10)+48)+c;
End;
If nho>0 then c:=chr(nho+48)+c;
Writeln(c:can);
can:=can-1;
End;
Procedure Cong(var c,d: string; z:byte);
Var nho: so;
x,i: byte;
Begin
for i:=1 to length(b)-z do c:=c+'0';
If length(c) > length(d) then
For i:=1 to length(c)-length(d) do d:='0'+d
Else
For i:=1 to length(d)-length(c) do c:='0'+c;
nho:=0;
For i:=length(d) downto 1 do
Begin
x:=ord(d[i])+ord(c[i])-96+nho;
d[i]:=chr((x mod 10)+48);
nho:=x div 10;
End;
If nho>0 then d:='1'+d;
End;
Begin
Nhap;
d:='';
For i:=length(b) downto 1 do
Begin
Nhan(a,ord(b[i])-48);
Cong(c,d,i);
End;
can:=length(a)+length(b)+1;
For i:=1 to can do Write('-');
Writeln;
Writeln(d:can);
Readln;
End.
(Lời giải của bạn Đặng Trung Thành - PTTH Nguyễn Du - Buôn Mê Thuột)
Bài 72/2001 - Biến đổi trên lưới số
const Inp ='bai72.inp';
Out ='bai72.out' ;
maxn=100;
Var dem, n, i, j, d:integer; f:text;
a:array[0..maxn+1,0..maxn+1] of Boolean;
Procedure Init;
Var t:integer;
Begin
Fillchar(a, Sizeof(a), true);
Assign(f, inp); reset(f);
dem:=0;
Readln(f, n);
for i:= 1 to n do
for j:=1 to n do
begin
read(f, t);
If t=1 then a[i,j]:=true else begin a[i,j]:=false;inc(dem); end;
If j=n then readln(f);
end;
Close(f);
End;
Procedure Solve1;
Begin
for i:=1 to n do
for j:=1 to n do
begin
If not a[i,j] then
begin
a[i,j]:= not (a[i,j-1] xor a[i,j+1] xor a[i-1,j] xor a[i+1,j]);
If a[i,j] then begin dec(dem);writeln(f,i,' ',j) end
end;
end;
End;
Procedure Solve2;
Begin
for i:=1 to n do
for j:=1 to n do
If not a[i,j] then
begin
If i >1 then
begin
a[i-1,j]:=false;
inc(dem);
writeln(f, i-1, ' ', j);
end
else
If i
begin
a[i+1,j]:=false;
inc(dem);
writeln(f, i+1, ' ', j);
end
else
If j >1 then
begin
a[i,j-1]:=false;
inc(dem);
writeln(f, i, ' ', j-1);
end
else
begin a[i,j+1]:=false; inc(dem); writeln(f, i, ' ', j+1) end;
exit;
end;
End;
BEGIN
Init;
Assign(f,out); rewrite(f);
While dem >0 do
begin
writeln(dem); d:=dem; solve1;
If (d=dem) and (dem >0) then solve2;
end; Close(f);
END.
(Lời giải của bạn Nguyễn Chí Thức - khối PTCTT - ĐHSP - Hà Nội)
Bài 73/2001 - Bài toán chuỗi số
Chia sẻ với bạn bè của bạn: |