Rèn luyện kỹ năng lập trình cho HSG tin học

1
Chuyên đề:
RÈN LUYỆN KỸ NĂNG LẬP TRÌNH
Cho HSG tin THCS




GV: Võ Văn Sửu.
Nội dung chuyên đề
I. Rèn luyện PP tìm tòi thuật toán
II. Rèn luyện phong cách lập trình.
III. Các dạng toán bồi dưỡng HSG THCS
2
I. Rèn luyện PP tìm tòi thuật toán

1. Tại sao phải rèn luyện cho hs khả năng tìm tòi thuật toán.



4

5
Thuật toán là phần quan trong bậc nhất để tạo nên một chương trình.
Ở tiểu học, học sinh 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.

6
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.

7
Xác định bài toán

Xác định INPUT và OUTPUT của bài toán.
Đặc tả mô hình toán học của bài toán.




3. Tìm thuật toán
8

Ở THCS nên sử dụng cách trình bày thuật toán bằng SĐK.
Khai thác ví dụ, hiểu ví dụ đã có và tìm các ví dụ khác.
Trình bày thuật toán từ tổng thể đến chi tiết
( phương pháp min dần)
Ví dụ: Kiểm tra số n có nguyên tố?
Phương án thô:
9
Nhập n
Có ước
Thực sự
n
N không
NT
N là sô
NT
+
-
BĐ
KT

Phương án mịn bước 1.
Đếm số ước của n
10
i:=0; d:=0
i:=i+1
n mod i=0
d:=d+1
I >=n
D=2
N khgnt
N nt
Nhập n
-
+
+
-
+
-
Phương án mịn 2:
Duyệt nếu có ước trong khoảng từ
2 đến căn n thì n không phải NT
P:=Trunc(Sqrt(n))
OK: Biến Boolean;
11
N
Ok:=N>1
i:=1
i:=i+1
N modi=o
Ok:=False
I > p
Ok=true
N NT
N kg NT
+
-
+
-
+
--
4. Giải một bài, gợi ý nhiều bài.
Có nhiều bài toán tuy phát biểu khác nhau nhưng cùng thuật toán, cùng cách giải.

Khi ra và hướng dẫn HSG giải một bài tập, phải chỉ cho họ biết nhiều bài toán khác có các giải hoàn toàn tương tự
12
Ví dụ:
Cho dãy các phần tử a1, a2,…, an
Yêu cầu tìm số lớn nhất.
TT: +max:=a1;
+ For i:=1 to n do
if max< ai then max:=ai
Nhận xét TT bài này có dạng:
+ Khởi tạo giá trị ban đầu
+ Duyệt, lưu lại giá trị tối ưu hơn.
13
Cho học sinh đề xuất các bài toán tương tự và cách giải: Cho dãy số nguyên ai
+ Tìm ai mà tổng chữ số của nó là lớn nhất.
+ Tìm số nguyên tố lớn nhất trong dãy.
+ Tìm số ai có nhiều chữ số nhất
+ Tìm 3 số liên tiếp có tổng lớn nhất…
+ Tìm 2 chỉ số i≠ j để ai+aj max
+ Tìm đoạn nhiều nhất các số liên tiếp bằng nhau
+ Tìm đoạn các số liên tiếp mà tổng max
+ Tìm số ai có tổng chữ số đầu và cuối max
…..
14
II. Rèn luyện phong cách lập trình.
.


CHƯƠNG TRÌNH=TT+CTDL+NTLT
15
Tuân theo các quy chuẩn, các quy ước.
Cách trình bày rõ ràng, sáng sủa nổi bật được cấu trúc logic của chương trình.
Người dùng dễ đọc, dễ hiểu nó.
16
Lợi ích của việc trình bày cẩn thận:

Thể hiện tốt cấu trúc lôgic của mã lệnh
Cải thiện khả năng đọc
Bảo đảm sự chính xác trong các thay đổi
Các lợi ích hệ quả của các lợi ích trên
+ Chương trình ít mắc lỗi và dễ sửa
chữa khi mắc lỗi.
+ Tăng khả năng làm việc theo nhóm,
17
1. Quy ước về cách đặt tên cho các
định danh.
a) Đặt tên cho biến.

Tên biến nên thể hiện được ý nghĩa: thông thường các biến nguyên như i, j, k, n dùng làm biến lặp; x, y dùng làm biến tọa độ…
Biến lưu trữ nên đặt tên gợi nhớ.
18
19

b) Đặt tên hằng: Tất cả các ký tự nên viết hoa.

Ví dụ: Const MAXN = 10000;
INPUT = ‘Baitap.inp’;
OUTPUT = ‘Baitap.out’;
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) 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ỗi đơn thể thực hiện một công việc, (chương trình con).
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.
20
Cách trình bày chương trình phải nhất quán dễ đọc, dễ hiểu.
Tính đơn giản, rõ ràng.
Văn bản chương trình không trườn ra khỏi màn hình
Thứ tự: 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ự khi thực hiện chương trình.
21
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ý.
22
Ví dụ:
Không nên
For i := 1 to n do Begin Lệnh1;
Lệnh2;
End;
Nên
For i := 1 to n do
Begin
Lệnh1;
Lệnh2;
End;
23
c) Sử dụng khoảng trắng:
Khó đọc
If (aa:=b*c
TimMax(a,b,c);
Dễ đọc
If ( a < c ) and ( c mod 2 = 0 ) then d := a + c;
a := b * c;
TimMax(a, b, c);
24
d) Nên định nghĩa hằng:
Không nên
……………
For i := 1 to 100 do A[i] := Random(100);
While i<=100 do…
Nên
Const MAXN = 100;
……..
For i :=1 to MAXN do
A[i] :=Random(MAXN)
While i <= MAXN do …..
25
Không nên:
…..
Assign(f, ‘Bai1.inp’);
Reset(f);
….
Assign(f,’Bai1.out’);
…..
Nên:
Const fi=‘Bai1.inp’;
fo=‘Bai1.out’;
…..
Assign(f, fi);
Reset(f)
….
Assign(f,fo);
…..
26
e) Dùng biến, chú thích
Biến chạy i, j…phải dùng biến địa phương
Cách đặt tên biến phải gợi nhớ,
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. 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 }
27

3. Tối ưu sự thực thi mã nguồn

Không nên
If b * b – 4 * a * c >0 then
Begin
x1 := (-b +sqrt( b * b – 4* a* c)) / (2 * a);
x2 := (-b – sqrt(b * b – 4* a* c)) / (2* a);
end;
 
28
Nên

Delta := b * b – 4 * a * c
If delta >0 then
Begin
Delta:=sqrt(delta);
x1 := (-b + delta) / (2 * a);
x2 := (-b – delta) / (2 * a);
End;
29

Kết thúc vòng lặp sớm nhất có thể


Không nên
bkt := true; {n không có ước thực sự}
For i := 2 to n-1 do
If n mod i = 0 then
bkt := False;

Nên
bkt := true;
For i := 2 to n-1 do
If n mod i = 0 then
Begin
bkt := False;
Break;
End;
30
Nhiều kết quả xử lý ngay khi nhập liệu

Không nên

For i := 1 to n do readln(f, a[i]);
For i:=1 to n do s := s+a[i];


Nên

For i := 1 to n do
Begin readln(f, a[i]);
s := s+a[i];
end;
31
Hạn chế lệnh rẽ nhánh
Không nên

If x > y then d:=True else d:= False;
Nên
d := x>y;
32
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
33

II. Các dạng toán bồi dưỡng HSG THCS


Nhóm các bài toán số học:
Nhóm các bài toán thao tác trên mảng
Nhóm các bài toán xử lý xâu .
Các bài toán khác.
34
1. Các bài toán số học.

Để giải các bài toán về số học giáo viên cần cho học sình ứng dụng nhuần nhuyễn các kiến thức số học ở THCS chủ yếu dựa vào 2 phép toán DIV, MOD
35
Thuật toán tìm UCLN
Cho 2 số nguyên m, n>0 . UCLN(m,n)=?

Thuật toán 1: Sử dụng phép trừ liên tục cho đến khi 2 số bằng nhau:
+ Nhập m, n
+ While m<>n do
If m>n then m:=m-n
Else n:=n-m;
+UCNN:=n;
36
Thuật toán 2: (Đối với HSG nên hướng các em sử dụng thuật toán này)
+ Nhập m, n
+ While n <> 0 do
Begin
r:= m mod n
m:=n;
n:=r;
End;
+UCLN:=m
37
So sánh 2 thuật toán:
Với m=1000000000, n=1.
Thuật toán 1 thực hiện 1000000000 thao tác mới cho UCLN=1
Thuật toán 2 chỉ thực hiện 3 thao tác đã cho UCLN=1.
38
Hàm kiểm tra số nguyên tố.
FUNCTION Ngto(P:Integer): Boolean;
Var NT: Boolean; I: integer;
Begin
NT:=P>1;
For i:=2 to Trunc(Sqrt(P)) do
If P mod i =0 then
Begin NT:=False; Break End;
Ngto:=NT;
End;
39
Hàm tính tổng các chữ số
Function TongCS(n: Integer): Integer;
Var s, m:Integer;
Begin
m:=n; s:=0;
While m<>0 do
Begin
s:=s+ m mod 10; m:=m div 10;
End;
TongCS:=s;
40
Một số bài tập.
Bài 1. Phân tích ra thừa số nguyên tố
Thuật toán:
If Ngto(n) then writeln(n) 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;
End;
 

41
Bài 2. Rút gọn phân số.
Đề bài: Cho phân số a/ b
(a, b nguyên, b>0). Tìm c, d nguyên (d>0)
sao cho c/ d tối giản và a/b=c/d
+ Thuật toán:
Dau:=1; If a<0 then dau:=-1 ; a:=abs(a);
c:=a div UCLN(a,b);
d:=b div UCLN(a, b);
Writeln(dau*c,’/ ‘, d);
42
Bài 3. Giai thừa.

Cho số tự nhiên n. P=n!. Hỏi:
a/ P có bao nhiêu chữ số không tận cùng.
b/ Số khác 0 tận cùng của P là chứ số nào.
43
?
44


a/ Số chữ số 0 cuối cùng chính là số ước bằng 10 của P! mà p!=a.10k=a.2k.5k.

Do số ước 2 nhiều hơn ước 5, nên số 0 tận cùng là số ước 5 của P. Vậy ta cần tính số lượng ước 5 của P !

45
Gọi S5 là số lượng ước 5 của P. S5 ?
?
?
46
47
Thuật toán a)
Goi S5 là số ước 5 của P
s5:=0;
For m:=5 to n do
Begin
K:=m;
While k mod 5 = 0 do
Begin Inc(s5); k:=k div 5 End;
End;
In ra kết quả : S5.
b) Câu này dễ mắc sai lầm vừa nhân vừa xóa 0 cuối và chỉ giữ lại chữ số khác 0 cuối cùng.
+ Thuật toán:
- Xóa hết ước 2 (số lượng S2) và ước 5 (số lượng S5). Gọi k=S2-S5
- Nhân các số còn lại được số p (các phép toán chỉ giữ chữ số cuối)
Tính a=2k . a*p là đáp số
48
S2:=0; S5:=0; P:=1;
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 P*2 mod 10
49
Bài 4. Tính tổng chữ số.
(Đề thi HSG thành phố Hà nội)

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ữ số xuất hiện bao nhiêu lần.

50
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:
+ Khởi tạo
Nhập n;
Sum:=0; fillchar(a, sizeof(a),0);
51
For m:=1 to n do
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]
52
Anh / Chị hãy phát biểu một bài toán có cùng các giải.
53

Bài 5. Số siêu nguyên tố.


Đề bài :Số P gọi lầ số siêu nguyên tố, nếu
nó nguyên tố và khi ta lần lượt bỏ các chữ
số ở hàng đơn vị từ tái qua phải thì số mới
nhận được vẫn là một số nguyên tố.
Ví dụ: 239 là số siêu nguyên tố vì 239 là số nguyên tố và 23, 2 cũng là các số nguyên tố , còn 431 không phải là số siêu nguyên tố. Cho một số n (054
???
55
Phương án 1: Duyệt toàn bộ:
+ Tìm số nhỏ nhất lớn nhất có n chữ số
Chẳng hạn với n=3 thì số nhỏ nhất và lớn nhất có 3 chữ số là: n1=100 và n2=999
+ Dùng một biến chạy p:
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
56
Suy nghĩ thêm về ví dụ:
+ Khi n=1 thì các số 2, 3 , 5, 7 là số nguyên tố => có 4 số siêu nguyên tố có 1 chữ số
+ Khi n=2 thì có các số siêu nguyên tố có 2 chữ số: 23, 29, 31, 37, 53, 59, 71, 73, 79
Do đó xuất phát từ số siêu nguyên tố có 1 chữ số (2, 3, 5, 7) ta ghép với các số 1, 3, 7, 9 để tìm ra các số siêu NT có 2 cs (23,29, 31, 37, 53, 59, 71,73, 79).
Lại xuất phát từ các số siêu NT có 2 cs rồi ghép với 1,3, 7 9 ta tính được số siêu NT có 3 chữ số…
57
58
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}
59
Anh/Chị hãy phát biểu một bài toán mà có thể áp dụng thuật toán vừa trình bày.
60
Ta có thể nêu các bài toán tương tự sau:
Số n gọi là số SNT phải nếu n là NT và khi ta lần lượt bỏ đi các chữ số bên trái thì số còn lại vẫn là một số nguyên tố.
Vd: n=317 là SNT phải vì 317 , 17 , 7 là các số NT
Yêu cầu cho N đếm số lượng SNT phải có N chữ số.
Gọi số SNT như trong bài 5 là số SNT trái, còn N gọi là SNT nếu nó vừa siêu NT trái vừa SNT phải. Tính số lượng các SNT có n cs.
61
2. Nhóm các bài toán mảng.
Trong phần này gv cần cung cấp cho học sinh một số kỹ năng cơ bản khi thao tác trên mảng như:
Tìm phần tử MAX, MIN.
Sắp xếp dãy.
Kiểm tra tinh đơn điệu của dãy.
Tìm kiếm trên dãy…
62
Bài 1. Tìm tổng max


Đề bài: Cho dãy n số nguyên dương a1, a2,…an. Hãy tìm 2 số ai, aj, sao cho i≠j và ai+aj đạt max.
63
???
64
Thuật toán 1: Duyệt toàn bộ:
+ Max:=a1+a2;// Khởi tạo giá trị ban đầu
+ For i:=1 to n-1 do
For j:=i+1 to n do
If Max
Thuật toán này có độ phức tạp O(n2)
Khi n=10000, thuật toán không hiệu quả
65
Thuật toán 2 : Sắp xếp
+ Sắp xếp giảm dần a1, a2, a3,….
+Max:=a1+a2.
Độ phức tạp của TT này là O(n2). Tuy nhiên học sinh biết PP sắp xếp nhanh thì tốc độ xử lý tốt hơn (O(nlogn))
66
Tốt hơn được không?
???
67

Thuật toán 3. Tìm số lớn thứ nhất thứ nhì
+ maxi:=1; for I:=2 to n do if maxi+maxj:=1;
for I:=2 to n do if maxjĐáp số : m+a[maxj]
68
?
69
Thuật toán 4. (Xử lý luôn khi đọc dữ liệu)
+Readl(f,n) {n >1}; Read (f, a,b);
{gọi max1, max2 là số lớn và bé trong a,b}
+If a>b then Begin max1:=a; max2:=b End
Else Begin max1:=b; max2:=a End
+ 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
70

Anh /Chị hãy phát biểu bài toán tương tự …và trình bày thuật toán giải nó.
.
71

Bài toán cho tổng 3 số.
Tìm tổng max của ai+ aj + ak (I, j, k khác nhau).
Cho hs trình bày các thuật toán tương tự và đánh giá hiệu quả các thuật toán.
72
Bài 2. Dãy đối xứng
Đề bài.
Dãy a1, a2, …,an gọi là dãy đối xứng nếu a1=an, a2= an-1,….
Cho dãy a1, a2, …,an . Hãy tìm các ghi tiếp vào dãy một số ít nhất câc phần tử để dãy nhận được là đối xứng.
Ví dụ: Dãy 1 2 1 2 2 thì cần thêm 1 2 1
73
?
74
Phân tích:
Số phần tử thêm vào ít nhất nếu đoạn sau cùng tạo thành đoạn đối xứng là lớn nhất.
Thuật toán:
+ Tìm I nhỏ nhất sao cho ai, ai+1,…, an đx
+ Thêm tiếp vào phía sau: ai-1. ai-2,…a1.
75
Cài đặt:
+Lập hàm DX(l, r:integer): boolean;
DX:=True; g:=(l+r) div 2;
For i:=l to g do if a[i] <> a[l*r-i] then
DX:=Fase;
+ Tìm h nhỏ nhất mà DX(h, n)
for h:=1 to n do if DX( h, n) then Break;
+ Số phần tử cần thêm h-1;
For i:=h-1 to 1 do write(a[i],’ ‘);

76
Bài 3. Bao nhiêu điểm
Đề bài: .
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


77
?
78
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]
79
Có thuật toán tốt hơn ?.

+ Tìm max1 (O(n))
+ Tìm max2< max1 (O(n))
+ Tìm max3< max2 (O(n))

80

Hãy phát biểu mở
rộng bài toán!
81
Bài toán tổng quát:
Cho dãy n các số nguyên dương. Biết rằng trong dãy tồn tại k giá trị khác nhau.
Hỏi khi sắp theo thứ tự giảm dần thì phần tử lớn thứ k bằng bao nhiêu? (k=3 là trường hợp bài toán trên)
82
Bài 4. Dãy số Fibonacci
Đề bài . Cho dãy sô Fibonacci 1, 1, 2, 3, 5….Ta thành lập dãy số mới bằng cách lần lượt thay mỗi số hạng bằng số dư của số hạng đó khi chia cho 100.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
Dãy số mới nhận được sau khi thay là:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, 33
Số hạng thứ n trong dãy mới là số nào?
Có bao nhiêu giá trị khác nhau trong dãy số mới?
83
???
84
Thuật toán (lùa bò vào chuồng)
+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);
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]}

85
5. Dãy tăng
Cho một dãy các số nguyên a1, a2, …an.
Yêu cầu: Hãy cho biết:
a) Dãy có tăng hay giảm?
b) Tìm một đoạn dài nhất các phần tử liên tục tăng.
c) Tìm một đoạn dài nhất các phần tử liên tục giống nhau.
86
6. Tìm UCLN, BCNN của dãy
Đề bài: Cho dãy số nguyên dương a1, a2, .., an. Hãy tìm UCLN, BCNN của dãy
87
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()…
88
Bài 1. Tìm số
(Đề thi HSG Hà nội 2011)
Đề bài:
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.
Ví dụ S = ‘tesst1234#password5426’. Số cần tìm là 23.
 
89
???
90
Thuật toán 1: Giả sử xâu đã cho là S,
+ Tạo mảng so[1], so[2],,,lần lượt copy được từ các cụm số trong S
+Với mỗi s[i] dùng 2 biến chạy l, r để tách ra một xâu con của so[i] từ vị trí l đến vị trí j và lưu lại số NT max trong so[i] rồi số sánh với các số nguyên tố trong so[j] khác.
91
Ví dụ S = ‘tesst1234#password5426’.
So[1]=234; So[2]=5426;
Số nguyên tố lớn nhất trong So[1] là 23.
Số nguyên tố lớn nhất trong So[2] là 5
Vậy đáp số là 23.
92
Thuật toán 2. (không lưu mảng các số)
Khởi tạo: S:= ‘ ‘+S+ ‘ ‘; SoNgtmax:=-1
For i:=2 to length(s) do if (S[i] in [0..9]) and
S[i-1] not in [0..9] then begin j:=I; repeat
inc(j) until not S[j] in [0..9] or (j> length(s));
so:=copy(S, I, j-i)
If SoNgtmax< max(so) then
SoNgtmax:=max(so);
End;
{ Function max(so: string[9]): integer, cho số NT max trong xâu so}
93
Có bài toán tương tự nào không?

94
Bài 2. Sắp xếp số
Cho xâu S chỉ gồm các chữ cái tiếng anh thường và chữ số. Các chữ số kế tiếp nhau trong S tạo thành một số tự nhiên .
Yêu cầu: Sắp xếp tăng dần các số trong xâu. 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.
Ví dụ: Input: t994a0046ui00t148x
Output:t0a46ui148t994x

 
Thuật toán: S= t994a0046ui00t148x
+ 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
96
?Anh / chi hãy phát biểu vài bài toán có cùng các giải.
97
3. Mật khẩu
Cho trước một xâu S bao gồm chữ cái hoa, chữ cái thường và chữ số.
Yêu cầu:
Chọn một xâu con (gồm các ký tự liên tục) của S có độ dài ngắn nhất sao cho xâu con vừa chọn có thể dùng làm một mật khẩu an toàn
( nghĩa là trong xâu con đó có đủ 3 loại chữ cái in, chữ cái thường , chữ số và đô dài mk ≥ 6).
Ví dụ: Input: Asdgcdh5rghvh4c
Output: Asdgcdh5
98
Thuật toán
Đây là bài toán đơn giản:
Luui:=1; luuj:=length(s)
For i:=1 to length(s)-5 do
For j:=i+5 to length(s) do
Begin x:=copy(s,I, j-i+1);
If OK(x) then if j-i+1=6 then
begin luui:=i; luuj:=j Break; End
else Capnhat( luui, luuj)
End;
99
?Anh/ Chi hãy phát biểu bài toán mới!
100
4. Vòng xuyến.
Đề bài: Một vòng xuyến có n (n<=100) hạt cườm. Mỗi hạt cườm có một trong 3 màu B (xanh) , R (đỏ), Y (vàng). Một số hạt maù trắng (W).
Yêu cầu : Hãy tô một số hạt màu trắng thành màu B, R, hoặc Y để trên vòng xuyến có số hạt cùng màu là nhiều nhất.
Ví dụ S=WRBBBWWYYRWRW. Ta tô W-> R
khi đó S=RRBBRRYYRRRR. Đ/s 6
101
Thuật toán
+ Nhân đôi S:=S+S;
+ Bước1: Tô tất hạt W thành B. Tìm đoạn dài nhất các phần tử màu B liên tục (S1)
+ Bước 2: Tô tất cả các hạt W thành R và tìm đoạn dài nhất màu R (S2)
+ Bước 3 : Tô tất cả các hạt W thành Y và tìm đoạn dài nhất màu R. (S3)
+ Bước 4: So sánh S1 ,S2, S3  kết quả.
102
Tóm tắt:
Khi bắt đầu giảng dạy môn thuật toán và lập trình cho học sinh THCS, GV cần :
Rèn luyện tư duy thuật toán tốt cho HS
Rèn luyện cách trình bày một chương trình.
Rèn luyện tính sáng tạo, chặt chẽ, tối ưu.


103
Chúc anh/chị có nhiều sáng tạo trong giảng dạy môn lập trình.

GV: VÕ VĂN SỬU
104