Tài liệu tập huấn tin học

Tổng quan chương trình bồi dưỡng HSG 9
1.Các kiểu dữ liệu đơn giản:Số nguyên, số thực, kí tự, lôgic,..
2.Các kiểu dữ liệu có cấu trúc :Mảng,xâu,file
3.Chương trình con: Hàm, thủ tục
4.Các thuật toán cơ bản : Tìm UCLN, tìm số nguyên tố, sắp xếp,..
5. Đệ quy


Một số chuyên đề bồi dưỡng HSG9
Chuyên đề 1: BÀI TOÁN SỐ HỌC
Yêu cầu: Học sinh phải nắm được các kiến thức cơ bản như:
Viết được các hàm xác định số nguyên tố, số chính phương, tính giai thừa..
Biết cách biểu diễn một số trong hệ thập phân.
Xác định được số dư, chữ số hàng đơn vị, hàng trăm, hàng ngàn,…. bằng cách sử dụng các phép toán DIV, MOD..
VD1_1: Tìm số tự nhiên n nhỏ nhất sao cho (n+1)(2n+1) chia hết cho 6 và thương là số chính phương
Program Tim_so;
var i,m,n,l:longint;
ch_phuong:boolean;
BEGIN
i:=0;
repeat
i:=i+1;
n:=(i+1)*(2*i+1);
m:=n div 6;
l:=trunc(sqrt(m));
ch_phuong:= sqr(l)=m;
until (n mod 6 =0) and (ch_phuong);
writeln(i);
readln;
END.
Kết quả
n= 377
VD2_1(HSG9-2010)
Đặt SN = 21+22+...+2N. Viết chương trình tìm số dư khi chia SN cho 30. Yêu cầu : Nhập từ bàn phím số nguyên dương N ( N<=50). In ra màn hình số dư r khi chia SN cho 30
Ví dụ : Với N=10; kết quả là 6
var r,r1,r2,r3,i,N:integer;
Function Haimu(k:integer):longint;
var temp:longint;
begin
temp:=1;
for i:=1 to k do temp:=temp*2;
Haimu:=temp;
end;
Function TongS(k:integer):longint;
var temp :longint;
i:integer;
begin
temp:=0;
for i:=1 to k do
begin
temp:=temp+ haimu(i);
end;
TongS:=temp;
end;
BEGIN
write(`N=`); readln(N);
if N<=30 then
r:= tongS(N) mod 30
else
begin
r1:=TongS(30) mod 30;
r2:=Haimu(30) mod 30;
r3:=TongS(N-30) mod 30;
r:= (r1+ r2*r3 ) mod 30
end;
writeln(`r=`,r); readln;
END.
VD3_1 (HSG9-TKY/2010):
Viết chương trình tìm tất cả các số nguyên dương N = abcd thỏa mãn các điều kiện sau
i) abd = (b+d-2a)2
ii) N+72 là số chính phương.
var N,t:integer;
a,b,c,d:byte;
function ch_ph(i:integer):boolean;
begin
ch_ph:=false;
if i= sqr(trunc(sqrt(i))) then ch_ph:=true;
end;
BEGIN
for a:=1 to 9 do
for b:=0 to 9 do
for c:=0 to 9 do
for d:=0 to 9 do
begin t:=(b+d-2*a)*(b+d-2*a);
N:= 1000*a+100*b+10*c+d;
if (100*a+10*b+d=t) and ch_ph(N+72) then writeln(N);
end;
readln;
END.
Kq 1069
VD4_1(HSG 9-2006)
Viết chương trình in ra màn hình tất cả các số nguyên tố có bốn chữ số, sao cho tổng các chữ số của nó bằng tích các chữ số của nó.
var N,t:integer;
a,b,c,d:byte;
Function Ngto(i:integer):boolean;
var j:integer;
Begin j:=1;ngto:=true;
if i=1 then ngto:=false
else
repeat
j:=j+1;
until (i mod j=0) or (i=j);
if jend;
BEGIN
for a:=1 to 9 do
for b:=0 to 9 do
for c:=0 to 9 do
for d:=0 to 9 do
begin
N:=1000*a+100*b+10*c+d;
if (a+b+c+d=a*b*c*d) and ngto(N) then writeln(N);
end;
readln;
END.
VD5_1:(HSG9-2006)
Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Cho trước hai số tự nhiên N, M. Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không.
Ví dụ: 15, 75 là nguyên tố tương đương
const maxN=maxint;
var M,N,i,i0:integer;
a:array[1..maxN] of boolean;
stop:boolean;
BEGIN
fillchar(a,sizeof(A),false);
Write(`Nhap vao 2 so M,N=`); readln(M,N);
i:=2;
if N Repeat
while M mod i <>0 do i:=i+1;
A[i]:=true; m:=m div i;
Until m=1;
i:=2;
stop:=false;
Repeat
While N mod i <>0 do i:=i+1;
N:=N div i;
if (not A[i]) then stop:=true;
Until (stop) or (N=1);
if stop then write(‘Khong ngto tuong duong`)
else write(‘Ngto tuong duong’);
readln;
END.
VD6_1:
Số “siêu nguyên tố” là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn là một số nguyên tố( Ví dụ 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố).
Viết chương trình nhập vào một số nguyên N (0< N <10) và đưa ra kết quả là một số siêu nguyên tố có N chữ số.
BEGIN
��� Write (`Nhap N: `);��� Readln (N);
��� ka:=1;� a[ka]:=0;
��� For i:=1 to N do
�������� Begin
����������� Kb:=0;
����������� For k:=1 to ka do
�������������� For cs:=0 to 9 do
���������������� If Prime(a[k]*10+cs) then
���������������� Begin
������������������������ Inc(kb);
������������������������ b[kb]:=a[k]*10+cs;
����������������� End;
���������� ka:=kb;
For k:=1 to ka do���� a[k]:=b[k];
End;
� For k:=1 to ka do� Write(a[k]:10);�
��Readln;
END.
var a,b: array [1..100] of longint;
      N,i,k,ka,kb,cs: byte;
Function Prime(N: longint): boolean;
Var i: longint;
Begin
   If (N=0) or (N=1) then   Prime:=false
   else
   begin
i:=2;
    While (N mod i <> 0) and
(i <= Sqrt(N)) do Inc(i);
      If i > Sqrt(N) then   Prime:=true  
else Prime:=false;
   end;
End;
VD7_1: Tìm nghiệm nguyên dương của phương trình:
Program Pt_nghiem_nguyen;
var x,y:byte;
begin
for x:=15 to 210 do
for y:=15 to 210 do
if (x-14)*(y-14)=196 then
write(`(`,x,`,`,y,`),`);
readln;
end.
Đáp số:
Có 9 cặp nghiệm:
(15;210), (16;112), (18;63), (21; 42), (28;28), (42;21),(63;18), (112;16), (210; 15)
Chuyên đề 2: DÃY SỐ
Dãy số là một trong những nội dung thường ra trong các đề thi HSG 9. Để làm tốt nội dung này yêu cầu hsinh cần phải nắm vững các kỹ thuật xử lý, nhập xuất mảng một chiều; cách thức tạo ra một mảng mới thỏa mãn một điều kiện nào đó.
VD1_2(HSG9-2006):
Cho dãy a1 , a2 ,…, aN . Ta gọi một đoạn con [i, j] của dãy là dãy ai, ai+1,..,aj. Viết chương trình nhập vào một dãy và in ra màn hình đoạn con [i, j] có tổng các phần tử là nhỏ nhất (nếu có nhiều phương án thì chỉ đưa ra 1 phương án)
Ví dụ : Dãy nhập vào 2, -1, 3, -8, 5, -4, 3, -6, 2, 2
Kết quả in ra là : -8, 5, -4, 3, -6 (Tồng Smin = -10)
Thuật giải: Xét tất cả các đoạn con tạo ra từ tập có n phần tử. Số lần xét là n(n+1) div 2.
Procedure Inkq;
var i:integer;
S:longint;
Begin
S:=0;
for i:=dau to cuoi do
begin
S:=S+a[i];
write(a[i],` `);
end;
writeln(` Tong S=`,S);
readln;
end;
Begin
Nhap;
Xuly;
Inkq;
end.
const maxN=100;
Var T,a:array[1..maxN] of integer;
N, dau, cuoi:integer;
Procedure Nhap;
var i:integer;
Begin
write(`Cho so luong phan tu day:`); readln(N);
for i:=1 to N do
begin
write(`A[`,i,`]=`); readln(a[i]);
end;
end;
Procedure Xuly;
Var i,j,min:integer;
Begin
T[1]:=A[1]; min:=maxint;
for i:=2 to N do T[i]:=T[i-1]+a[i];
for i:=1 to N do
for j:=i to N do
begin
if (T[j]-T[i]+a[i])< min then
begin
min:=T[j]-T[i]+a[i];
dau:=i; cuoi:=j;
end;
end;
end;
VD2_2 (HSG9-2010)
Dãy (an) được thiết lập theo cách thức: Với mỗi ai đã xác định thì ai+1 là số nguyên dương nhỏ nhất thỏa mãn hai tính chất sau:
ai+1 > ai
Tổng các chữ số của ai+1 bằng tổng các chữ số của 4ai .
Cho trước a1 và N. Hãy xác định dãy a1, a2, ..., aN

Input (a1 và N) Output
4 5 4 7 19 49 79
Thuật giải :
Mấu chốt của bài toán là tính tổng các chữ số của một số t.
Với một số a[i] cho trước, tìm số tiếp theo như sau:
Xét số so =a[i]+1. Nếu tổng các chữ số của số này thỏa mãn thì in ra, nếu không thì xét số tiếp theo so+1. Lặp lại cho đến khi tìm được.
Procedure Sinhday;
var so:longint; i: integer;
begin
i:=1;
while i begin
so:=a[i]+1;
while sumchuso(so)<>
sumchuso(4*a[i]) do inc(so);
inc(i);
a[i]:=so;
end;
end;

BEGIN
write(`a[1],N =`); readln(a[1],N);
sinhday;
for i:=1 to N do write(a[i],` `);
readln;
END.

Var a: array[1..100] of longint;
N: integer;
function Sumchuso(t:longint): integer;
var temp,r :integer;
begin
temp:=0;
while t>0 do
begin
r:= t mod 10;
temp:=temp+r;
t:=(t-r) div 10;
end;
sumchuso:=temp;
end;
VD4_2 (Dãy vô hạn các số)
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314.....
Nhập số K từ bàn phím và in ra trên màn hình số nằm ở vị trì thứ K trong dãy

*Mở rộng : Với các dãy số chẵn, số nguyên tố, số chính phương,…
Var k: longInt;
Function chuso(NN: longInt):char;
Var st : string[10];
dem,M :longInt;
Begin
dem:=0; M:=1;
Repeat
str(M,st);
dem := dem+length(st);
inc(M);
Until dem >= NN;
chuso := st[length(st) - (dem - NN)]
end;
BEGIN
write(`Nhap k:`); Readln(k);
writeln(`Chu so thu `, k,` =’,chuso(k));
Readln;
END.
Chuyên đề 3: Các bài toán về bảng
Yêu cầu:
Học sinh cần phải nắm vững các thao tác truy xuất bảng hai chiều theo hàng, cột, đường chéo; kỹ năng viết nhiều vòng lặp For lồng nhau.
VD1_3(HSG9-2009):
Một bàn cờ 8 x 8 ô vuông mỗi ô được đánh địa chỉ là cặp số (x,y), (trong đó: x là số thứ tự của hàng từ 1 đến 8; y số thứ tự của cột từ 1 đến 8). Trên bàn cờ có đặt trước các chú chuột máy ở một số ô. Một chú mèo máy có thể nhìn thấy các chú chuột này nếu chuột cùng nằm trên một đường thẳng hoặc một đường chéo với nó. Hãy xác định vị trí để đặt một chú mèo máy sao cho nó có thể nhìn thấy được tất cả các chú chuột đã đặt trên bàn cờ.
Input (dữ liệu vào): Nhập vào từ bàn phím N cặp số nguyên x, y (0- Output (dữ liệu ra): Ghi ra file text có tên là MOUSECAT.OUT, gồm một dòng ghi cặp số (x, y) là vị trí đặt chú mèo máy( trường hợp có nhiều vị trí đặt thì chỉ cần đưa ra một vị trí. Nếu không tìm thấy vị trí để đặt thì ghi là ‘Khong tim thay’).
Thuật giải: Dựng các đường thẳng(dọc, ngang, chéo) đi qua các chú chuột. Giao điểm các đường thẳng này là nghiệm của bài toán
var a: array[1..8,1..8] of integer;
f:text;
N,i,j:integer;
x,y : array[1..8] of integer;
Procedure DDau_cheo_trai (h,c:integer);
var x,y:integer;
begin x:=h; y:=c;
while (x>1) and (y>1) do
begin
dec(x); dec(y); inc(a[x,y]);
end;
x:=h; y:=c;
while (x<8) and (y<8) do
begin
inc(x); inc(y); inc(a[x,y]);
end;
end;

Procedure DDau_cheo_phai (h,c:integer);
var x,y:integer;
begin x:=h; y:=c;
while (x>1) and (y<8) do
begin
dec(x); inc(y); inc(a[x,y]);
end;
x:=h; y:=c;
while (x<8) and (y>1) do
begin
inc(x); dec(y); inc(a[x,y]);
end;
end;
Procedure DDau_cot (h,c:integer);
var x,y:integer;
begin
x:=h; y:=c;
while x>1 do
begin
dec(x); inc(a[x,y]);
end;
x:=h; y:=c;
while (x<8) do
begin
inc(x); inc(a[x,y]);
end;
end;

Procedure DDau_hang (h,c:integer);
var x,y:integer;
begin
x:=h; y:=c;
while y>1 do
begin
dec(y); inc(a[x,y]);
end;
x:=h; y:=c;
while (y<8) do
begin
inc(y); inc(a[x,y]);
end;
end;
Procedure Inkq;
var i,j,x,y:integer;
begin
x:=0; y:=0;
for i:=1 to 8 do
for j:=1 to 8 do if a[i,j]=N then
begin
x:=i; y:=j; break;
end;
if (x>0 )and (y>0) then
writeln(‘(`,x,`,`,y,`)`)
else writeln(`Khong tim thay!`);
readln;
end;
Procedure Nhap
Begin
Writeln(‘N=‘); readln(N);
for i:=1 to N do
begin
readln(f,x[i],y[i]);
a[x[i],y[i]]:= -10
end;
End;
BEGIN
fillchar(a,sizeof(a),0);
Nhap;
for i:=1 to N do
begin
DDau_cheo_trai(x[i],y[i]);
DDau_cheo_phai(x[i],y[i]);
DDau_cot(x[i],y[i]);
DDau_hang(x[i],y[i]);
end;
Inkq;
END.
VD2_3(HSG11-2005):
Cho bảng A kích thước MxN. Phần tử Aij được gọi là phần tử yên ngựa nếu nó là phần tử nhỏ nhất trong hàng của nó đồng thời là phần tử lớn nhất trong cột của nó. Ví dụ trong bảng số sau đây:
15 3 9
55 4 6
76 1 2
thì phần tử A[2,2] chính là phần tử yên ngựa. Lập chương trình nhập từ bàn phím một bảng số kích thước MxN và kiểm tra xem nó có phần tử yên ngựa hay không?
Chuyên đề 4 : Sắp xếp
Các bài toán liên quan đến kỹ thuật sắp xếp được vận dụng trong các trường hợp tìm nghiệm tối ưu.
Chương trình không yêu cầu học sinh biết các kỹ thuật sắp xếp với các độ phức tạp khác nhau. Học sinh chỉ cần năm vững một hoặc hai kỹ thuật sắp xếp cơ bản là được
VD1_4:
Trong đợt tổ chức đi tham quan Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm quan địa điểm có cự ly là di (i=1,2,...., N). Hội thi có M xe taxi đánh số từ 1 đến M (MN) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj cho 1 đơn vị cự ly.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu vào: File văn bản P2.INP:
- Dòng đầu tiên chứa hai số nguyên dương N, M (NM200);
- Dòng thứ hai chứa các số nguyên dương d1, d2, ..., dN
- Dòng thứ ba chứa các số nguyên dương v1, v2, ..., vM.
Kết quả: Ghi ra file văn bản P2.OUT:
Dòng đầu tiên chứa tổng lượng xăng cần cho việc đưa các đoàn đi thăm quan
Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i



Thuật toán :
-Sắp xếp các di tăng dần
-Sắp xếp các vi giảm dần .
-Số lượng xăng tiêu thụ là tổng d1*v1 + d2*v2 +…+dN*vN
VD2_4 (HSG12-2010)
Trong thời niên thiếu, ai cũng đã từng chơi trò chơi “rồng, rắn lên mây”. Trong trò chơi này, các người chơi thường đặt tay lên vai nhau để tạo thành một hàng dài làm “rắn” để chơi đuổi bắt.
Trong quá trình đuổi bắt, “rắn” có thể bị đứt thành nhiều khúc và để tiếp tục trò chơi, cần phải nối các khúc lại với nhau. Hai khúc được nối lại với nhau thông qua một người chơi, người chơi này khi đó sẽ đứng cuối của một khúc này đồng thời lại đứng đầu của một khúc kia. Để biết người chơi nào sẽ là tác nhân nối hai khúc, người quản trò sẽ phát cho người đó một lá cờ làm hiệu. Người có cờ hiệu được phép nối vào đuôi của một khúc hoặc yêu cầu một khúc nào đó nối vào sau mình. Hãy giúp người quản trò phát ít cờ nhất nhưng vẫn đủ để nối lại các khúc đã đứt.
Dữ liệu vào : File BL2.INP. Dòng đầu ghi số N (2≤N ≤ 20000), để chỉ N khúc đã bị đứt. Dòng tiếp theo ghi N số dương, mỗi số thứ i trong dòng này để chỉ số người chơi có trong khúc thứ i .
Dữ liệu ra : Đưa ra màn hình một số nguyên duy nhất, là số cờ tối thiểu mà người quản trò phải phát.
Ví dụ :
Input Output
5
1 3 2 5 6 3
Chuyên đề 5: Giải toán Casio
Trong quá trình bồi dưỡng giáo viên nên đưa một số bài toán sử dụng máy tính Casio bằng cách giải bằng ngôn ngữ lập trình Pascal để gây hứng thú trong học tập.
Một số bài toán kiểu này cũng đã được ra thi học sinh giỏi 9 cấp tỉnh.
Program Bai_Casio_THPT_2006;
var a,b,c:longint;
i:byte;
begin
a:=1; b:=2; i:=2;
repeat
i:=i+1;
c:=3*b+2*a;
a:=b; b:=c;
until i =15;
writeln(`u15=`,c);
readln;
end.
VD1_5 (Thi Casio khu vực 2006-THPT)
Biết dãy số {Un} được xác định như sau:
U1=1; U2 =2; Un+2= 3*Un+1 + 2*Un . Tính U15
VD2_5: (Thi Casio khu vực-THCS-2006)
Tìm tất cả các số tự nhiên n (1000cũng là số tự nhiên
Program Thi_casio_khu_vuc_THCS_2006;
Var i:integer;
a:longint;
Begin
for i:= 1001 to 1999 do
begin
a:=trunc(sqrt(54756+15*i));
if (a*a =54756+15*i) then write(i:6);
end;
readln;
end.
VD3_5(HSG9-2009)
Viết chương trình tìm số nguyên dương T nhỏ nhất có N chữ số, biết rằng khi chia T cho 19 thì dư 13 và khi chia T cho 31 thì dư 12.
Yêu cầu : Nhập từ bàn phím số nguyên dương N (N10). In ra màn hình số T phải tìm. Trong trường hợp không tồn tại, phải thông báo ra màn hình “ Khong ton tai”
Ví dụ:
Input Output
4 1438


Xin chân thành cám ơn!