Bài 13/1999 -
Phân hoạch hình chữ nhật
(Dành cho học sinh THPT)
{Recommend:m,n<5}
const
m=4;n=4;max=m*n;
var
a: array[1..m,1..n] of byte;
i1,j1,dem,daxep,tg: integer;
f: text;
time: longint absolute $0:$46C;
save: longint;
{------------------------------------}
procedure
init;
begin
for
i1:=1 to m do
for j1:=1 to n do a[i1,j1]:=0;
dem:=0;
daxep:=0; tg:=0;
end;
{------------------------------------}
procedure
kq;
begin
for
i1:=1 to m do
begin
for j1:=1 to n do write(f,a[i1,j1],' ');
writeln(f);
end;
end;
{------------------------------------}
procedure
try(i,j: integer);
var
i2,j2,flag: integer;
begin
if
(daxep=max) then begin kq; writeln(f); tg:=tg+1; end
else
begin
flag:=j;
while (flag
if (a[i,flag]<>0) then flag:=flag-1;
for i2:=i to m do for j2:=j to flag do
begin
dem:=dem+1;
for i1:=i to i2 do for j1:=j to j2 do a[i1,j1]:=dem;
daxep:=daxep+(i2-i+1)*(j2-j+1);
i1:=i;j1:=j2;
while (a[i1,j1]<>0) do
begin
j1:=j1+1;
if j1=n+1 then begin j1:=1; i1:=i1+1; end;
end;
try(i1,j1);
daxep:=daxep-(i2-i+1)*(j2-j+1);
for i1:=i to i2 do
for j1:=j to j2 do a[i1,j1]:=0;
dem:=dem-1;
end;
end;
end;
{------------------------------------}
BEGEN
init;
assign(f,'kq.dat');
rewrite(f);
save:=time;
try(1,1);
write(f,tg);
close(f);
write('Time
is about:',(time-save)/18.2);
readln;
END.
Bài 14/2000 - Tìm
số trang sách của một quyển sách
(Dành cho học sinh Tiểu học)
Để tiện tính toán, ta sẽ đánh số lại quyển sách bằng các số
001, 002, 003,..., 009, 010, 011, 012, 013,..., 098, 099, 100, 101,... tức là
mỗi số ghi bằng đúng 3 chữ số. Như vậy ta phải cần thêm 9x2=18 chữ số cho các
số trước đây chỉ có 1 chữ số và 90 chữ số cho các số trước đây chỉ có 2 chữ số,
tổng cộng ta phải dùng thêm 108 chữ số. Với cách đánh số mới này, ta phải cần
tới 1392+108=1500 chữ số. Vì mỗi số có đúng 3 chữ số nên có tất cả 1500:3=500
số, bắt đầu từ 001. Vậy quyển sách có 500 trang.
Bài 15/2000
- Hội nghị đội viên
(Dành cho học sinh Tiểu học)
Để tiện tính toán, cứ mỗi một cặp bạn trai-bạn gái quen
nhau ta sẽ nối lại bằng một sợi dây. Như vậy mỗi bạn sẽ bị "buộc" bởi
đúng N sợi dây vì quen với N bạn khác giới. Gọi số bạn trai là T thì tính được
số dây nối là TxN. Gọi số bạn gái là G thì tính được số dây nối là GxN. Nhưng
vì 2 cách tính cho cùng kết quả là số dây nối nên TxN=GxN, suy ra T=G. Vậy
trong hội nghị đó số các bạn trai và các bạn gái là như nhau.
Bài 16/2000 -
Chia số
(Dành cho học sinh THCS)
Lập một
bảng 2NxN ô. Lần lượt ghi N2 số 1, 2, 3,..., N2-1,
N2 vào N cột, mỗi cột N số theo cách sau:
|
1
|
|
|
|
|
|
2
|
N+1
|
|
|
|
|
3
|
N+2
|
2N+1
|
|
|
|
...
|
...
|
...
|
...
|
...
|
|
N
|
2N-1
|
3N-2
|
...
|
(N-1)N+1
|
|
|
2N
|
3N-1
|
...
|
N2-(N-2)
|
|
|
|
3N
|
...
|
N2-(N-3)
|
|
|
|
|
...
|
N2-(N-4)
|
|
|
|
|
|
...
|
|
|
|
|
|
|
Trong N
hàng trên, tổng i số trong hàng thứ i là:
i+[N+(i-1)]+[2N+(i-2)]+...+[(i-1)N+1]
=
N[1+2+...+(i-1)]+[i+(i-1)+(i-2)+...+1]
=
Ni(i-1)/2+i(i+1)/2
= (Ni2-Ni+i2+i)/2
Trong N
hàng dưới, tổng (N-i) số trong hàng thứ N+i là
(i+1)N+[(i+2)N-1]+[(i+3)N-2]+...+[N2-(N-i-1)]
=
N[(i+1)+(i+2)+...+N]-[1+2+...+(N-i-1)]
=
N(N+i+1)(N-i)/2 - (N-i-1)(N-i)/2
= (N2+Ni+i+1)(N-i)/2
= (N3+Ni+N-Ni2-i2-i)/2
Cắt đôi
bảng ở chính giữa theo đường kẻ đậm và ghép lại thành một bảng vuông như sau:
|
1
|
2N
|
3N-1
|
...
|
N2-(N-2)
|
|
2
|
N+1
|
3N
|
...
|
N2-(N-3)
|
|
3
|
N+2
|
2N+1
|
...
|
N2-(N-4)
|
|
...
|
...
|
...
|
...
|
...
|
|
N
|
2N-1
|
3N-2
|
...
|
(N-1)N+1
|
Khi đó
tổng các số trong hàng thứ i là
(Ni2-Ni+i2+i)/2
+ (N3+Ni+N-Ni2-i2-i)/2 = (N3+N)/2
= N(N2+1)/2
Rõ ràng
trong mỗi hàng có N số và tổng các số trong mỗi hàng là như nhau.
Bài 17/2000 - Số nguyên tố tương đương
(Dành
cho học sinh THCS)
Có thể
viết chương trình như sau:
Program
Nttd;
Var
M,N,d,i: integer;
{------------------------------------}
Function
USCLN(m,n: integer): integer;
Var r:
integer;
Begin
While
n<>0 do
begin
r:=m mod n; m:=n; n:=r;
end;
USCLN:=m;
End;
{------------------------------------}
BEGIN
Write('Nhap
M,N: '); Readln(M,N);
d:=USCLN(M,N);
i:=2;
While
d<>1 do
begin
If d mod i =0 then
begin
While d mod i=0 do d:=d div i;
While M mod i=0 do M:=M div i;
While N mod i=0 do N:=N div i;
end;
Inc(i);
end;
If
M*N=1 then Write('M va N nguyen to tuong duong.')
Else
Write('M va N khong nguyen to tuong duong.');
Readln;
END.
Bài 18/2000 - Sên bò
(Dành
cho học sinh THCS và THPT)
Ta có
thể thấy ngay là con sên phải đi N bước (vì xi+1 = xi+1), và nếu đi
lên k bước thì lại di xuống k bước (vì yN = y0 = 0). Do đó,
h = N div 2;
Chương
trình có thể viết như sau:
Program Senbo;
Uses Crt, Graph;
Var f:Text;
gd, gm, N, W,xo,yo:Integer;
Procedure Nhap;
Begin
Write('Nhap so N<50:');Readln(N);
If N>50 Then N:=50;
End;
Procedure Veluoi;
Var
i,j,x,y:Integer;
Begin
W:=(GetMaxX -50) Div N;
yo:=GetMaxY-100;
xo:=(GetMaxX-W*N) Div 2-25;
For i:=0 To N Do
For j:=0 To N Div 2 Do
Begin
x:=i*W+xo;
y:=yo-J*W;
Bar(x-1,y-1,x+1,y+1);
End;
End;
Procedure Bo
Var
i,j,xo,yo,x,y:Integer;
Sx,Sy,S:String;
Begin
j:=0;xo:=xo;y:=yo;
Writeln(f,N:2,N Div 2:3);
SetColor(2);
OutTextXY(xo,yo+5,'(0,0)');
For i:=1 To N Do
Begin
If i<=N-i Then Inc(j)
Else If j>0 Then Dec(j);
Writeln(f,i:2,j:3);
x:=i*W+xo;y:=yo-j*W;
Line(xo,yo,x,y);
Str(i,sx);str(j,sy);
S:='('+sx+','+sy+')');
OutTextXY(x,y+5,s);
Delay(10000);
xo:=x;yo:=y;
End;
End;
Begin
Nhap;
Assign(F,'P5.Out');
ReWrite(F);
Dg:=Detect;
InitGraph(Gd,Gm,'');
VeLuoi;
Bo;
Readln;
Close(F);
CloseGraph;
End.
Bài 19/2000 - Đa giác
(Dành
cho học sinh THPT)
Ta sẽ chứng minh khẳng định sau cho n ³ 3:
Các số thực dương a1, a2, a3,...,
an lập thành các cạnh liên tiếp của một đa giác n cạnh khi và chỉ khi với mọi
k=1, 2,..., n ta có các bất đẳng thức sau:
a1 + a2 +... (thiếu k)... +
an > ak
(1)
(tổng của n-1 cạnh bất kỳ phải lớn hơn độ dài cạnh
còn lại)
Chứng minh
Chứng minh được tiến hành qui nạp theo n. Với n = 3 thì (1) chính là
bất đẳng thức tam giác quen thuộc.
Giả sử (1) đúng đến n. Xét (1) cho trường hợp n+1.
Trước tiên ta có nhận xét sau: Các số a1, a2,...,
an, an+1 lập thành một đa giác n +1 cạnh khi và chỉ khi tồn tại một
số g sao cho a1, a2, a3,..., an-1,
g tạo thành một đa giác n cạnh và g, an, an+1 tạo thành một tam
giác.
Giả sử a1, a2, a3,...,
an, an+1 lập thành một đa giác n +1 cạnh. Khi đó theo nhận xét trên
thì tồn tại đa giác n cạnh a1, a2, a3,..., an-1,
g và tam giác g, an, an+1. Do đó ta có các bất đẳng thức sau suy từ
giả thiết qui nạp và bất đẳng thức tam giác:
a1 + a2 + a3 +.... + an-1
> g
(2)
an + an+1 > g > |an - an+1|
(3)
Do vậy ta có
a1 + a2 + a3 +.... + an-1
> |an - an+1|
(4)
từ (4) suy ra ngay các khẳng định sau:
a1 + a2 + a3 +.... + an-1 +
an > an+1
(5)
a1 + a2 + a3 +.... + an-1 +
an+1 > an
(6)
Mặt khác từ giả thiết qui nạp cho đa giác n cạnh a1, a2,
a3,..., an-1, g, tương tự như (2) ta có các bất đẳng thức
sau với k < n:
a1 + a2 +... (thiếu k)... + an-1 + g
> ak
thay thế vế trái của (3) ta phải có với k <N:< p>
a1 + a2 +... (thiếu k)... + an-1 + an
+ an+1 > ak (7)
Các bất đẳng thức (5), (6) và (7) chính là (1). Điều kiện cần được
chứng minh.
Giả sử ngược lại, hệ bất đẳng thức (1) thoả mãn, ta có
a1 + a2 +... + an-1 + an > an+1
(8)
a1 + a2 +... + an-1 + an+1
> an
(9)
và với mọi k < n ta có:
a1 + a2 +...(thiếu k)... + an-1 + an +
an+1 > ak (10)
Từ (8) và (9) ta có ngay:
a1 + a2 +... + an-1 > |an - an+1|
(11)
Từ (10) suy ra với mọi k < n ta có:
an + an+1 > ak - a1 - a2 -...(thiếu
k)... - ak (12)
Từ các bất đẳng thức (11) và (12) suy ra tồn tại một số dương g thỏa
mãn đồng thời các điều kiện sau:
an + an+1 > g > |an - an+1|
(13)
a1 + a2 +... + an-1 > g
(14)
g > ak - a1 - a2 -...(thiếu k)... - ak
(15)
Các bất đẳng thức (13), (14) và (15) chính là điều kiện để tồn tại đa
giác n cạnh a1, a2, a3,..., an-1, g
và tam giác g, an, an+1. Điều kiện đủ đã được chứng minh.
Chương trình:
Program Dagiac;
Uses Crt;
Const fn = 'P6.INP';
Var i,j,N: integer;
a: array[1..100] of real;
s: real;
Kq: boolean;
{------------------------------------}
Procedure Nhap;
Var f: text;
Begin
Assign(f,fn); Reset(f);
Readln(f,N);
For i:=1 to N do Read(f,a[i]);
Close(f);
End;
{------------------------------------}
BEGIN
Nhap;
Kq:=true;
For i:=1 to N do
begin
s:=0;
For j:=1 to N do If j<>i then s:=s+a[j];
If s<=a[i] then Kq:=false;
end;
If Kq then Write('Co.') Else Write('Khong.');
Readln;
END.
Bài 20/2000 - Bạn
Lan ở căn hộ số mấy?
(Dành cho học sinh Tiểu học)
Ta coi như các căn hộ được đánh số từ 1 đến 64 (vì ngôi nhà
có 8 tầng, mỗi tầng có 8 căn hộ). Ta có thể hỏi như sau:
- Có phải số nhà bạn lớn hơn 32?
Sau khi Lan trả lời, dù "đúng" hay
"không" ta cũng biết chính xác căn hộ của Lan ở trong số 32 căn hộ
nào. Giả sử câu trả lời là "không" ta cũng biết chính xác căn hộ của
Lan ở trong số 32 căn hộ nào. Giả sử câu trả lời là "không", ta hỏi
tiếp:
- Có phải số nhà bạn lớn hơn 16?
Sau câu hỏi này ta biết được 16 căn hộ trong đó có căn hộ
Lan đang ở.
Tiếp tục hỏi như vậy đối với số đứng giữa trong các số còn
lại. Sau mỗi câu trả lời khoảng cách giữa các số giảm đi một nửa. Cứ như vậy,
chỉ cần 6 câu hỏi, ta sẽ biết được căn hộ Lan ở.
Bài 21/2000 -
Những trang sách bị rơi
(Dành cho học sinh Tiểu học)
Nếu trang
bị rơi đầu tiên đánh số 387 thì trang cuối cùng sẽ phải đánh số lớn hơn và phải
là số chẵn. Do vậy trang cuối cùng phải là 738.
Như vậy, có 738 - 378 + 1= 352 trang sách (176 tờ ) bị
rơi.
Bài 22/2000 - Đếm đường
đi
(Dành cho học sinh THCS)
a) Có tất
cả 8 đường đi từ A đến B sao cho mỗi đường đi qua một đỉnh nào đó chỉ đúng một
lần. Cụ thể:
A B
A E B
A E F B
A E D F B
A E F C B
A E D C B
A E F D C
B
A E D F C B
b). Có tất cả 8 đường đi từ A đến D, sao cho đường đi đó
qua mội cạnh nào đó chỉ đúng một lần, cụ thể:
A B C D
A B E D
A B F D
A E D
A E B F D
A E B C D
A E F D
A E F C D
c). Các đường đi qua tất cả các
cạnh của hình, qua mỗi cạnh đúng một lần (điểm bắt đầu và điểm kết thúc trùng
nhau):
-
+ Các đường đi qua tất cả các cạnh
của hình, qua mỗi cạnh đúng một lần (điểm bắt đầu và điểm kết thúc không trùng
nhau):
- Điểm bắt đầu là C và điểm kết
thúc là D:
CFBCDFEBAED
CFBCDFEABED
CDFCBFEBAED
....
Tương tự như thế với điểm bắt đầu
là D và điểm kết thúc là C ta cũng tìm được các đường thoả mãn tính chất này.
Bài 23/2000 - Quay
Rubic
(Dành cho học sinh THPT)
Khai
triển mặt rubic và đánh số các mặt như hình vẽ sau:
Khi đó ta có thể xây dựng thủ tục Quay (mặt thứ i) để đổi
màu 8 mặt con của mặt này và 12 mặt con kề với mặt này. Trên cơ sở đó giải được
2 bài toán này. Chương trình có thể viết như sau:
Program Rubic;
uses Crt;
Type
Arr= array[0..5, 0..7] of byte;
const color: Array [0..5] of char=('F', 'U','R', 'B', 'L',
'D');
Var
A1, A2, A0, A: Arr;
X, X1, X2: String;
k: byte;
Procedure
Nhap;
Var i, j: byte;
Begin
Clrscr;
Writeln ('Bai toan 1. So sanh hai xau:');
Writeln ('Nhap xau X1:');
Readln (X1);
Writeln (' Nhap xau X2:');
Readln (X2);
Writeln ('Bai toan 2. Tinh so lan xoay:');
Write ('Nhap xau X:');
Readln (X);
For i:= 0 to 5 do
For j:= 0 to 7 do A[i, j]:= i;
A:=A0; A1:=A0; A2:=A0;
End;
Procedure
Quay (Var A: Arr; k: byte);
Const Dir
: array
[0.. 5,
0.. 3, 0.. 3] of byte = ( ( (1,2,5,4), (6,0,2,4), (5,7,1,3), (4,6,0,2) ),
(
(0,4,3,2), (0,0,4,0), (1,1,5,1), (2,2,6,2) ),
(
(0,1,3,5), (4,4,4,4), (3,3,3,3), (2,2,2,2) ),
(
(1,4,5,2), (2,0,6,4), (1,7,5,3), (0,6,4,2) ),
( (0,5,3,1), (0,0,0,0),
(7,7,7,7),(6,6,6,6) ),
( (0,2,3,4), (6,6,2,6),
(5,5,1,5), (4,4,0,4) ) );
var
i,j,tg: byte;
Begin
tg:=A[k,6];
for i:=3
downto 1 do A[k,0] := A[k,2*i-2];
A[k,0]:=tg;
tg:=A[k,7];
for i:=3
downto 1 do A[k,2*i] := A[k,2*i -2];
A[k,1]:=tg;
for i:=1
to 3 do
begin
tg:=A[dir[k,0,3],
Dir[k,i,3];
for j:=3
downto 1 do A[ dir[k,0,j], Dir[k,i,j] ]:= A[ dir[k,0,j-1], Dir[k,i,j-1] ];
A[
[dir[k,0,0], Dir[k,i,0] ]:=tg;
end;
End;
Function
Eq(A,B:Arr):Boolean;
Var
i,j,c:byte;
Begin
c:=0;
for i:=1
to 5 do
for j:=1
to 7 do
If A[i,j]
<> B[i,j] then inc(c);
If c=0
then Eq:=true else Eq:=false;
End;
Procedure
QuayXau(x:string; var A: arr);
Var
i,j:byte;
Begin
for i:=1
to length(X) do
begin
for j:= 1
to 5 do
If
Color[j] = X[i] then Quay(A,j);
end;
End;
Procedure
Bai1;
Begin
QuayXau(X1,A1);
QuayXau(X2,A2);
End;
Procedure
Bai2;
Begin
k:=0;
Repeat
QuayXau(X,A);
Inc(k);
Until
Eq(A,A0);
End;
Procedure
Xuat;
Var
i,j:byte;
Begin
writeln;
writeln('Ket
qua:');
writeln('Bai
toan 1. So sanh 2 xau:') ;
If
Eq(A1,A2) then writeln('Hai xau X1 va X2 cho cung mot ket qua.');
writeln('Can
ap dung xau X ',k,' lan de Rubic quay ve trang thai ban dau.');
Readln;
End;
Begin
Nhap;
Bai1;
Bai2;
Xuat;
END.
Không có nhận xét nào:
Đăng nhận xét