Chuyên đề bồi dưỡng giáo viên tin học THCS

Nội dung
I. Rèn luyện tư duy thuật toán cho học sinh THCS
1. Tại sao phải rèn luyện kỹ năng tìm tòi thuật toán
2. Xác định rõ INPUT và OUTPUT.
3. Mịn dần thuật toán.
II. Rèn luyện phong cách lập trình tốt cho học sinh THCS .
1.Quy ước về cách đặt tên cho các định danh.
3. Phong cách viết mã nguồn
4.Tối ưu sự thực thi mã nguồn
5. Tạo các bộ thử
III.Các dạng toán bồi dưỡng môn tin cho HSG THCS
1.Các bài toán số học
2.Các bài toán về mảng một chiều , hai chiều.
3. Các bài toán về xử lý xâu
I. Rèn luyện tư duy thuật toán cho học sinh THCS.
1. Tại sao phải rèn luyện tư duy thuật toán cho học sinh THCS.
Trong quyển sách nổi tiếng của mình về NNLT Pascal ( viết năm 1970), tác giả
N.With đã viết một dòng ngay từ trang đầu:

CHƯƠNG TRÌNH= THUẬT TOÁN +CẤU TRÚC DỮ LIỆU
Như vậy thuật toán là phần quan trong bậc nhất để tạo nên một chương trình.
Nhưng hết tiểu học, học sinh vẫn chưa được làm quen với khái niệm thuật toán.
Do vậy khi học lập trình cái khó khăn ban đầu của học sinh chính là tìm thuật
toán để giải bài toán đã cho. Một học sinh muốn tiến sâu, tiến xa trong tương lai
phải có tư duy thuật toán tốt.
1
Bởi vậy làm quen và rèn luyện tư duy thuật toán cho học sinh mới bắt đầu học
lập trình là một yêu cầu thiết yếu. Không nên vội vàng cho học sinh làm việc
trên máy tính luôn khi mới bát đầu học. Có thầy giáo khi dạy tin học cho lớp

c) Đặt tên cho chương trình con: Tên chương trình con thường bắt đầu bằng chữ hoa. Vì chương
trình con thường thực hiện một chức năng nào đó nên tên hay bắt đầu bằng động từ.
Ví dụ: TimMax( ); GetNum( );
2. Phong cách viết mã nguồn.
a) Quy tắc trình bày tổng thể chương trình:
- Chương trình nên tách thành nhiều đơn thể (mô _ đun), mỗi đơn thể thực hiện một công việc,
càng độc lập với nhau càng tốt (chương trình con). Điều này sẽ giúp cho chương trình dễ cải tiến và
khi đọc chương trình ta sẽ dễ hình dung được vấn đề đang được thực hiện.
- Nên sử dụng các tham số khi truyền thông tin cho các chương trình con. Tránh sử dụng các biến
toàn cục để truyền thông tin giữa các chương trình con vì như vậy sẽ làm mất đi tính độc lập giữa các
chương trình con và rất khó khăn khi kiểm soát giá trị của chúng khi chương trình con thi hành.
- Cách trình bày chương trình càng nhất quán càng dễ đọc, dễ hiểu.
- Chương trình nên giữ được tính đơn giản, rõ ràng.
- Chương trình nên thực hiện như một dòng chảy từ trên xuống:
+ Sau đó đến khai báo đơn vị, khai báo hằng, khai báo kiểu, khai báo biến toàn cục, khai báo
chương trình con.
+ Không nên sử dụng Goto vì sẽ phá vỡ tính tuần tự của việc thực hiện chương trình.
b) Quy tắc trình bày dòng lệnh
- Mỗi câu lênh nên được đặt riêng trên một dòng để chương trình dễ đọc và dễ quan sát cách thực
hiên khi dùng watch để tìm lỗi.
- Sử dụng tab để canh lề chương trình (các lệnh ngang cấp thì phải tab vào như nhau): Điều này sẽ
giúp chương trình rõ ràng và dễ quản lý.
Ví dụ:
Không nên Nên
For i := 1 to n do Begin Action1;
Action2;
End;
For i := 1 to n do
Begin
Action1;

- Viết chú thích cho chương trình: Biến, hàm khi định nghĩa nên viết chú thích ý nghĩa và chức
năng rõ ràng. Đôi khi các đoạn lệnh thực thi cũng cần giải thích nếu chúng quá phức tạp. Nên viết
chú thích ngắn gọn nhưng đầy đủ và dễ hiểu.
Ví dụ: Var iCount : Integer; // đếm số cách thực hiện
Procedure Try( i : Integer); // Tìm từ i
Tuy nhiên không phải bất cứ lệnh nào cũng chú thích, việc chú thích tràn lan ngay cả với câu
lệnh đơn giản không có ý nghĩa gì mà còn làm chương trình khó nhìn hơn.
- Nên viết biểu thức điều kiện mang tính tự nhiên: Biểu thức nên viết dưới dạng khẳng định, việc
viết dưới dạng phủ định sẽ làm khó hiểu.
Ví dụ:
Không nên Nên
If not(a mod 5<>0) then …. If a mod 5 = 0 then ….
4
c) Qui tắc khai báo tên tệp dữ liệu dùng trong chương trình.
Dùng tệp nên khai báo tên têp trước trong phần khai báo hằng:
Ví du:
Const fi=’BAI1.INP’;
Fo=’BAI1.OUT’ ;
3. Tối ưu sự thực thi mã nguồn
Mục đích của việc tối ưu mã nguồn là nâng cao tốc độ xử lý và hạn chế không gian bộ nhớ mà
chương trình chiếm dụng. Thông thường có thể mâu thuẫn giữa tốc độ và không gian lưu trữ, do đó
tùy theo điều kiện cụ thể mà người lập trình có sự lựa chọn thích hợp. Một số thủ thuật sau có thể
giúp người lập trình hình thành nên phong cách lập trình tốt.
- Lưu tạm giá trị thường sử dụng: Nếu một biểu thức tính toán được dùng nhiều lần thì nên tính kết
quả một lần rồi lưu vào một biến và dùng lại.
Ví dụ:
Không nên Nên
F:=sqrt(x*x+y*y)+(sqrt(x*x+y*y)*sqrt(x*y)-sqrt(y*y);
x2 := x*x;
y2 := y*y;

Không nên Nên
If x > y then d:=True else d:= False; d := x>y;
- Tránh lãng phí bộ nhớ: Bằng cách sử dụng kiểu dữ liệu nhỏ nhất đủ để lưu trữ. Việc sử dụng tài
nguyên nhiều hơn mức đòi hỏi của chương trình là một thói quen xấu mà người lập trình hay mắc
phải. Hơn nữa tốc độ chương trình sẽ nhanh hơn khi sử dụng kiểu dữ liệu nhỏ hơn.
- Khai báo biến cục bộ trong phạm vi gần nhất: Khai báo biến cục bộ gần với điểm sử dụng nhất.
Việc khai báo ở phạm vi rộng hơn chỉ làm lãng phí và khó kiểm soát.
6
Không nên Nên
bkt := true;
For i := 2 to n do
If n mod i = 0 then
bkt := False;
bkt := true;
For i := 2 to n do
If n mod i = 0 then
Begin
bkt := False;
Break;
End;
- Giảm số lượng tham số truyền vào hàm: Việc sử dụng hàm có quá nhiều tham số được truyền
vào có thể làm ảnh hưởng đến ngăn xếp dành cho việc gọi hàm. Nhất là trường hợp tham số là kiểu
dữ liệu có cấu trúc. Sử dụng con trỏ hay tham chiếu trong trường hợp này để đơn giản hóa.
4) Kiểm nghiệm chương trình với các bộ test đầy đủ nhất.
- Test đầu bài,
- Các test đơn giản
- Test các trường hợp đặc biệt.
- Test lớn
- Xem lại đề để không bỏ sót trường hợp.
III. Các dạng toán bồi dưỡng môn tin cho HSG THCS .

m:=n;
n:=r;
End;
+UCLN:=m
Với thuật toán này khi m=1000000000, n=1, chỉ mất vài phép toán để tính được
UCLN(m,n).
Để tìm UCLN của dãy a1, a2,…,an, cần lập hàm:
FUNCTION UCLN(a, b: longint): longint;
Khi đó + d:=a1;
+ for i:=2 to n do Begin b:=ai; d:=UCLN(d, b);End;
• Thuật toán tìm BCNN của 2 số:
Ta có BCNN(m,n)= (m * n) div UCLN(m, n).
Ở đây học sinh thường mắc 2 sai lầm sau :
Sai lầm 1 : d :=UCLN(m, n) ;
BCNN :=m*n div d ;
Đúng ra phải là :
BCNN :=m * n (lưu tích m.n)
8
d := UCLN(m, n) ;
BCNN := BCNN div d
Sai lầm 2 : BCNN(m, n, k) = m*n*k div UCLN(m, n k)
Để tìm BCNN của dãy số nguyên dương a1, a2, …,an (n>=2)
BCNN:=a1; d:=a1;
For i:=2 to n do n do
Begin
b:=ai
BCNN:=BCNN*b;
d:=UCLN(BCNN,b);
BCNN:=BCNN div d ;
End ;

Dùng mảng : array[0 20] of byte ;
+ d:=-1;
+ While n<>0 do
Begin
Inc(d);
a[d]:= n mod q
n:=n div q;
End; { lưu dãy chữ số q- phân theo thứ tự ngược}
+ for i:=d downto 0 do write(a[i]);
Một số bài toán số học.
Bài 1. Phân tích ra thừa số nguyên tố
Cho số tự nhiên n (n>1). Hãy phân tích n thành tích các thừa số nguyên tố.
Ví dụ: Cho n=12 thì n=2.2.3, cho n=300 thì n=2.2.3.5.5
+ Phân tích: Chỉ cần duyệt qua các ước nguyên tố từ bé đến lớn rồi ghi ra.
+ Thuật toán: If Ngto(n) then writeln(n)
10
Else
Begin
m:=n;
For p:=2 to n div 2 do
If Ngto(p) then
Begin
While m mod p = 0 do write(p,’.’);
m:= m div p;
End;
Bài 2. Rút gọn phân số.
Cho phân số a/ b trong đó a nguyên còn b là số tự nhiên khác không. Hãy tìm 2 số
c, d sao cho phân số c/ d tối giản và a/b=c/d.
+ Phân tích:
Đây là bài toán đơn giản, nhưng phải chú ý số a có thể âm.

For m:=2 to n do
Begin
K:=m;
While K mod 2 = 0 do Begin inc(so2), k:= k div 2 End;
While K mod 5 = 0 do Begin inc(so5), k:= k div 5 End;
P:=P* K mod 10.
End.
For i:= 1 to so2-so5 do Begin p:=p * 2 mod 10
In ra kết quả : P
Bài 4. Tính tổng chữ số. (Đê thi HSG thành phố Hà nội năm 2010)
Một quyển sách có n trang. Hỏi
a/ Tổng tất các chữ số đã ghi trên các trang sách.
b/ Mỗi chũa số xuất hiện bao nhiêu lân.
Thuật toán :
+ Lập hàm TongCS(K) để tính tổng các chữ số trong K
+ Dùng mảng a[0], a[1],…,a[9], trong đó a[i] số lần xuất hiện của chữ số i:
+ Sum:=0; fillchar(a, sizeof(a),0);
+ For m:=1 to n do
12
Begin
K:=m;
Sum:=Sum+TongCS(K);
While K <> 0 do
Begin
Inc( a[ k mod 10])
K:=K div 10
End;
In ra kết quả: Sum, a[0],…, a[9]
Bài 5. Phân tích (Thi HSG MOSKVA)
Cho số tự nhiên n. Hãy phân tích n =A+B sao cho UCLN(A, B) là lớn nhất.

For p:= n1 to n2 do
If p thỏa mãn then tăng biến đếm.
+ Thuật toán này cũng được 40 % số test
• Thuật toán tốt.
+If n=1 thì a[1]:=2;[2]:=3; a[3]:=5, a[4]:=7; slg:=4
+ If n>1 then
Begin c[1]:=1; c[2]:=3; c[3]:=7; c[4]:=9;scs:=1;
Repeat inc(scs); tg:=0; fillchar(b, sizeof(b),0)
For k:=1 to slg do For g:=1 to 4 do
Begin if NT(a[k]*10+c[g]) then
Begin inc(tg); b[tg]:= NT(a[k]*10+c[g]) End
End;
a:=b;Slg:=tg; tg:=0;
Until scs=n.
End; {kết quả là Slg}
Bài 8. Phân số ( Đề thi HSG thành phố Hà nội)
Phân số
q
p
( p, q là 2 số nguyên dương) gọi là phân số đúng nếu
q
p
<1. Còn
q
p
gọi là
phân số tối giản nếu UCLN(p,q)=1
Yêu cầu: Cho trước số nguyên n (3≤ n ≤ 50000000).
14
a) Tính số lượng các phân số đúng, tối giản

33
12
Số hạng thứ 13 trong dãy mới là số 33
Có 12 giá trị khác nhau trong dãy số mới
Lời giải:
• +Dùng mảng : a[0], a[1], a[2],…, a[99];
• A[i]=0 nếu I không xuất hiện trong dãy rút gọn), a[i]=1 nếu I xuất hiện trong
dãy.
+ If (n=1) or (n=2) then writeln (1,’ ‘, 1);
15
Else Begin a:=1; b:=1; d:=2;
Repeat Inc(d);
I c:=(a+b) mod 100; a:=b;b: =c;
If a[c] =0 then a[c]:=1;
Until d=n;
End; {In ra C, a[0]+a[1]+…+a[99]}
Bài 2 Tổng max.
Cho dãy n số nguyên dương a
1
, a
2
,…a
n
. Hãy tìm 2 số a
i
, a
j
, sao cho i≠j và a
i
+a

16
+ For i:=3 to n do
Begin
Read(f, c);
If c>= max1 then
Begin max2:=max1; max1:=c End
Else If c>= max2 then max2:=c;
End; { Đáp số là max1+max2
Bài 3. Bao nhiêu điểm.
Trong một cuộc thi đấu thể thao n người tham gia . Người thứ I có điểm là ai . Biết
rằng có đủ các giải nhất ,nhì, ba và những người có điểm ngang nhau có giải như
nhau và ngược lại. An được giảI 3. Hỏi số điểm của An là bao nhiêu.
Ví dụ: Input n=6, a: 10 9 1 7 3 10 7
Output: 7
Lời giải:

• Thuật toán:
• +sắp xếp giảm dần
• +i:=1;
• + While a[i+1]=a[i] do i:=i+1;
• + i:=i+1;
• +While a[i+1]=a[i] do i:=i+1;
Đáp số : a[i+1]
3. Nhóm các bài toán xử lý xâu.
Để giải các bài toán về xâu cần cho học sinh nắm vững các hàm, thủ tục xử lý
xâu như hàm COPY(), LENGTH(), INSERT(), STR() , VAL()…
Bài 1. Tìm số (Đề thi HSG thành phố Hà nội 2011)
Cho một xâu S, trong đó có chứa một số cụm số. Không có quá 6 chữ số liên tuc
trong S.
Hãy tìm xâu con của S, biểu diễn một số nguyên tố lớn nhất.

Yêu cầu:
a/ Tính số lượng các chữ số khác nhau có mặt trong dãy.
b/ Sắp xếp tăng dần các số trong xâu sau khi loại bỏ các số 0 vô nghĩa ở đầu mỗi số.
Các kí tự khác giữ nguyên thứ tự. Giả thiết mỗi xâu con của S có không quá 6 chữ số
liên tục.
Dữ liệu: Vào từ tệp văn bản SXT.INP gồm một dòng duy nhất ghi xâu S.
Kết quả: Ghi ra tệp văn bản SXT.OUT:
18
- Dòng 1 ghi số lượng các chữ số khác nhau có mặt trong dãy.
- Dòng 2 ghi xâu S sau khi đã sắp xếp lại các số, các kí tự khác số giữ nguyên thứ tự.
Ví dụ:
SXT.INP SXT.OUT SXT.INP SXT.OUT
a212921hda456e3b 7
a3hda456e212921b
t994a0046ui00t148
x
6
t0a46ui148t994x
Lời giải:
a/ Dùng mảng a[0 9] , a[i]=0 nếu I không có mặt, a[i]=1 nếu I có mặt.
b/+ Tách số và chèn dấu * vào vị trí số:
so[1]=994, so[2]=0046, s0[3]=00, so[4]= 148
⇒ S=t*a*ui*t*x
+ Chuẩn và sắp sếp tăng:
so[1]=0, so[2]=46, so[3]=148, so[4]= 994
+ Lần lượt thay dấu * bởi so[1], so[2],…
=> S=t0a46ui148t994x .

19