SKKN năm học 2016-2017

PHƯƠNG PHÁP GIẢNG DẠY NGÔN NGỮ LẬP TRÌNH PASCAL
CHƯƠNG TRÌNH TIN HỌC 8 CHO HỌC SINH GIỎI
PHẦN I. ĐẶT VẤN ĐỀ
1. Lý do chọn đề tài:
– Sở Giáo dục và đào tạo Đăk Nông đã và đang đẩy mạnh “Ứng dụng công nghệ thông tin và đổi mới phương pháp dạy học” trong đó đặc biệt coi trọng việc phát huy vai trò tích cực, chủ động của học sinh, gắn việc học tập với công tác thực hành.
– Căn cứ vào nhu cầu học hỏi, tìm hiểu nội dung, phương pháp bồi dưỡng học sinh giỏi của các giáo viên bộ môn Tin học trên địa bàn tỉnh Đăk Nông.
– Căn cứ vào nhu cầu học tập nâng cao trình độ lập trình của học sinh nói chung và đáp ứng yêu cầu thi học sinh giỏi các cấp nói riêng.
– Căn cứ vào thực tế tình hình dạy học môn Tin học, học sinh vẫn chưa tìm thấy sự đam mê và còn gặp khó khăn khi bắt đầu tiếp cận với môn Tin học lập trình.
– Qua kinh nghiệm hơn 10 năm giảng dạy Tin học. Tôi đã rút ra kinh nghiệm rất quý báu là: Khi tiếp cận với kiến thức lập trình của bộ môn tin học, vấn đề đầu tiên và quan trọng nhất là giáo viên phải truyền cho học sinh được niềm đam mê và dạy cho học sinh được cách tư duy thật logic. Những bài học đầu tiên về cách lập trình có thể nói nó quyết định được phần lớn thành công của mỗi học sinh trong con đường của mình. Yêu hay không yêu môn học này? biết cách tư duy về lập trình hay không? Tất cả những thành công của giáo viên và học sinh đều được quyết định từ cách tiếp cận ban đầu này. Chính vì thế trong đề tài này tôi muốn trình bày từ những cách tiếp cận đầu tiên thật hiệu quả, đó là nền tảng vững chắc cho sự say mê, những viên gạch đầu tiên cho và thành công của mỗi học sinh và giáo viên.
Với những lý do đó tôi đã quyết định nghiên cứu đề tài: “Phương pháp giảng dạy ngôn ngữ lập trình Pascal chương trình tin học 8 cho học sinh giỏi”.
2. Mục đích nghiên cứu:
Việc dạy cho học sinh niềm đam mê và khả năng tư duy lập trình là điều không thể thiếu đối với việc đào tạo học sinh giỏi. Sau nhiều năm giảng dạy và nghiên cứu tôi đã có được những kết quả ban đầu. Tôi viết về đề tài này với mục đích:
– Cùng trao đổi với các bạn đồng nghiệp về cách dạy học sinh bước vào học lập trình môn Tin học.
– Học sinh có thêm một tài liệu để tham khảo trong quá trình học lập trình.
– Giúp anh chị em đồng nghiệp ở các trường THCS có thêm một tài liệu để ôn tập thi giáo viên giỏi và phục vụ công tác bồi dưỡng học sinh giỏi.

3. Đối tượng nghiên cứu:
– Học sinh giỏi Tin học ở các trường THCS bước vào học môn Tin học lập trình, từ đó phát triển làm tốt các bài toán trong các kỳ thi học sinh giỏi Tin học ở bậc trung học cơ sở.
4. Giới hạn phạm vi nghiên cứu của đề tài:
– Căn cứ vào thời gian làm đề tài và điều kiện áp dụng cho học sinh giỏi Tin học nên giới hạn đề tài chỉ nghiên cứu quy trình phát triển kiến thức từ những cái cơ bản nhất từ đó phát triển và vận dụng nó để giải quyết các bài toán trong phạm vi bồi dưỡng học sinh giỏi thị xã (huyện), Tỉnh, học sinh giỏi Quốc gia, …
– Khả năng áp dụng đề tài vào giảng dạy, bồi dưỡng học sinh giỏi Tin học cho giáo viên và học sinh THCS trên địa bàn toàn tỉnh Đăk Nông.
5. Nhiệm vụ nghiên cứu:
– Phát huy niềm say mê cho học sinh ngay từ những bài học đầu tiên về lập trình.
– Giúp độc giả tiếp cận cách dạy, cách học một cách có hệ thống.
– Giúp độc giả thấy được sự gần gũi giữa Toán học với Tin học lập trình, từ đó thấy được sự yêu thích cách tư duy logic của bộ môn này .
6. Phương pháp nghiên cứu:
– Điều tra khả năng tiếp cận môn Tin học lập trình của giáo viên THCS.
– Điều tra khả năng tiếp cận môn Tin học lập trình của học sinh chuyên Tin.
– Tham khảo tài liệu, nghiên cứu các đề thi, các bài toán thiên về tư duy toán học cơ bản chuyển về bài toán lập trình,…
– Phương pháp thực nghiệm trên đối tượng là học sinh giỏi Tin trong các trường THCS.

PHẦN II. NỘI DUNG ĐỀ TÀI
I. NHỮNG VẤN ĐỀ LÝ LUẬN:
Khi tiếp cận với kiến thức lập trình của bộ môn tin học, vấn đề đầu tiên và quan trọng nhất là giáo viên phải truyền cho học sinh được niềm đam mê và dạy cho học sinh được cách tư duy logic. Những bài học đầu tiên về cách lập trình có thể nói nó quyết định được phần lớn thành công của mỗi học sinh trong con đường của mình. Yêu hay không yêu môn học này? biết cách tư duy về lập trình hay không? Tất cả từ cách tiếp cận ban đầu này. Chính vì thế trong đề tài này tôi muốn trình bày từ những cách tiếp cận đầu tiên, từ đó phát triển cách dạy và học cao hơn.
Đề tài này tôi trình bày toàn bộ cách tiếp cận lập trình trong chương trình tin học lập trình bậc THCS, tôi nghĩ nó thật sự cần thiết cho học sinh và giáo viên bồi dưỡng học sinh giỏi vì chưa có một tài liệu nào viết một cách hệ thống và đầy đủ mọi kiến thức tin học lập trình bậc phổ thông nào.
II. NỘI DUNG:
1. Các bài toán cơ bản không dùng dữ liệu có cấu trúc
Trước tiên cho học sinh thấy được cái hay trong phép gán của tin học, qua một số bài tập này chắc chắn ta sẽ phát huy được tính kích thích, hăng say của các học sinh mà chưa từng được học về tin lập trình:
Bài toán 1. Viết chương trình tráo đổi giá trị giữa hai biến a và b.
Phương pháp giải:
Cách 1: Dùng biến trung gian tg:
tg := a;
a := b;
b := tg;
Đoạn chương trình không dùng biến trung gian sau là sai vì giá trị ban đầu của biến a bị mất, khi đó a = b và nhận giá trị ban đầu của b:
a := b;
b := a;
Cách 2: Không dùng biến trung gian:
a := a + b;
b := a – b;
a := a – b;
Bài toán 2. Cho a, viết chương trình tính a10 và a3 với yêu cầu không được dùng quá bốn phép toán.
Phương pháp giải:
Dùng thêm biến b để nhận giá trị:
b := a*a;
a := a*b; writeln( ‘a mu 3= ’, a);
a := a*b;
a := a*a; writeln(‘a mu 10= ’, a)
Bài toán 3. Cho a, viết chương trình tính a5 và a13 với yêu cầu không được dùng quá năm phép toán.
Phương pháp giải:
Dùng thêm biến b:
b := a;
a := a*a; { ta có a2 }
a := a*a; { ta có a4 }
b := b*a; { ta có a5 }
writeln(‘a mu 5= ’, b);
a := a*a*b; { ta có a13 }
writeln(‘a mu 13= ’, a);
Bài toán 4. Cho a, viết chương trình tính a4 , a12 và a28 với yêu cầu không được dùng quá sáu phép toán.
Phương pháp giải:
Dùng thêm biến b:
a := a*a; { ta có a2 }
a := a*a; writeln( ‘a mu 4= ’, a);
b:=a;
a := a*a*a; writeln( ‘a mu 12= ’, a);
a := a*a; { ta có a24 }
a := a*b; writeln(‘a mu 28= ’, a)
Sau khi học sinh hiểu ý nghĩa và vận dụng thành thạo lệnh gán ta hình thành cho học sinh biết cách tư duy để giải và tối ưu các bài toán chỉ sử dụng hai cấu trúc cơ bản là: Cấu trúc rẽ nhánh và lặp.
Bài toán 5. Các số tự nhiên từ 10 đến 99 được xếp thành một hàng 101112131415…99.
Cho trước một số tự nhiên k (1<= k<= 100). Tính xem chữ số thứ k của hàng trên tính từ trái sang phải là chữ số nào?
Phương pháp giải:
Chữ số thứ k( kí hiệu ch(k)) trong hàng
+ K lẻ: Khi K tăng 20 đơn vị thì chữ số tăng 1 đơn vị
1< K <= 19 thì ch(K) = 1
21<= K <= 39 thì ch(K) = 2
Vậy quy luật: ch(K) = (k div 20) + 1
+ K chẵn: Khi K tăng 20 đơn vị thì chữ số sẽ lặp lại suy ra
ch(K) = ch(K mod 20)
Trong 20 số đầu tiên ta có:
ch(2) = 0; ch(4) = 1; ch(6)=2; ch(8)=3
Như vậy ch(K) = ( K div 2) -1
Đoạn chương trình:
P:= K div 2;
If K mod 2= 1 then Write((11+P) div 10) else write( (9+p) mod 10);
Bài toán 6. Viết chương trình tính an. Kết quả cần được lưu trong biến b. Chương trình không được làm thay đổi giá trị của biến a và biến n.
Phương pháp giải:
Cách 1: Dùng thêm một biến k chạy từ 0 đến n và duy trì tính chất b luôn bằng ak.
k := 0; b := 1;
{b = ak}
while k <> n do
begin
k := k + 1;
b := b * a;
end;
Cách 2: k := n; b := 1;
{an = b * ak}
while k <> 0 do
begin
k := k – 1;
b := b * a;
end;
Cách 3: Ta có thể cải tiến cách giải thứ hai để đạt được độ phức tạp tối ưu nhất: O(logn)
k := n; b := 1; c:=a;
{an = b * ck}
while k <> 0 do
begin
if k mod 2 = 0 then
begin
k:= k div 2;
c:= c*c;
end else begin
k := k – 1;
b := b * c;
end;
end;
Sau ít nhất là 2 bước (nếu k là số lẻ, ta mất một bước trừ k đi 1), giá trị của k sẽ giảm đi một nửa (hoặc nhiều hơn).
Bài toán 7. Cho số nguyên không âm a và một số nguyên dương d. Viết chương trình tính thương q và số dư r khi chia a cho d mà không sử dụng phép toán div và mod.
Phương pháp giải:
Theo định nghĩa, a = q * d + r, với 0 <= r < d.{a >= 0; d > 0}
r := a; q := 0;
while not (r < d) do begin r := r – d; {r >= 0}
q := q + 1;
end;
Tiếp theo ta sẽ cho học sinh tiếp cận với các bài toán mà tư tưởng giải của nó chính là tư tưởng quy hoạch động, một trong những thuật toán tối ưu mà hầu hết các bài thi học sinh giỏi tin học từ cấp Quốc gia đến cấp Quốc tế đều bắt gặp. Khi ta dạy cho học sinh cách tiếp cận một cách đơn giản như thế này thì khi tiếp cận với quy hoạch động sẽ thấy dễ dàng hơn rất nhiều.
Bài toán 8. Dãy số Fibonaci được định nghĩa như sau:
F(0)= 1, F(1) = 1, F(n) = F(n-1) + F(n-2) với n >= 2.
Cho n, viết chương trình tính F(n).
Phương pháp giải:
Cách 1: Dùng ba biến a, b, c để lưu các giá trị của dãy số Fibonaci. Kết quả F(n) cần tìm được trong biến C:
a := 1;
b := 1;
for i:= 2 to N do
begin
c := a+b;
a :=b;
b := c;
end;
writeln(‘ F(‘, n,’)= ‘, c);
Cách 2: Ta có thể giải bài toán với độ phức tạp O(logn)
Ta nhận thấy một cặp 2 số Fibonaci liên tiếp được tính từ cặp liền trước qua phép nhân với ma trận: 1 0
1 1
Do đó vấn đề là cần tính luỹ thừa bậc n của ma trận này. Luỹ thừa này có thể được tính trong thời gian O(logn) với phương pháp tương tự như phép luỹ thừa với số thực ở bài toán 6 ở trên.
Bài toán 9. Đường viền trang trí ở nền nhà có kích thước 2xN được lát bằng hai loại gạch: loại kích thước 1×2 và loại kích thước 2×2. Hãy xác định số cách lát khác nhau có thể thực hiện được. Cho N( 1<= N <= 20). Tìm số cách lát có thể thực hiện được? Ví dụ: N=2 kết quả = 3 N=3 kết quả = 5 Phương pháp giải: Gọi số cách lát đường viền độ dài k là SA, số cách lát đường viền độ dài k-1 là SB, số cách lát đường viền độ dài k-2 là SC, ta có: Khởi tạo: SA- Số cách lát đường viền độ dài 1, SA- Số cách lát đường viền độ dài 0. SA:= 1; SB =0; Ta có công thức lặp: Khi độ dài đường viền tăng thêm một giá trị SA sẽ được tính lại như sau: SC:= SB; SB:=SA; SA = SB + 2*SC với k>=3 và số lần lặp là n-1 lần.
Như vậy bài toán chỉ cần dùng 3 biến để tính như sau:
Var a, b, c: longint; n, i:integer;
Begin
Readln(n);
if n=2 then c:=3;
a := 1;
b := 3;
for i:= 3 to N do
begin
c := 2*a+b;
a :=b;
b := c;
end;
writeln(‘ so cach lat la: ’, c);
End.
Các thuật toán về ước chung lớn nhất đối với học sinh giỏi tin học là một kiến thức không thể thiếu, học sinh phải hiểu, biết và vận dụng thuật toán này dưới nhiều biến thể khác nhau. Ta sẽ đi vào các thuật toán tìm ước chung lớn nhất của hai số nguyên.
Bài toán 10. Cho hai số nguyên a và b không đồng thời bằng 0. Viết chương trình tính ước số chung lớn nhất của a và b.
Phương pháp giải:
Cách 1:
if a > b then k := a else k := b;
{k = max (a,b)}
{bất biến: các số lớn hơn k sẽ không phải là ước chung của a và b}
while not (((a mod k)=0) and ((b mod k)=0)) do k := k – 1;
{k là ước chung lớn nhất của a và b}
Cách 2: (thuật toán Euclid).
Ta quy ước UCLN(0,0) = 0 và dùng các tính chất:
UCLN(a, b) = UCLN(a-b, b) = UCLN(a, b-a);
UCLN(a, 0) = UCLN(0, a) = a với a, b >= 0
m := a; n := b;
{bất biến: UCLN (a, b) = UCLN (m, n); m, n >= 0 }
while not ((m=0) or (n=0)) do
if m >= n then m := m – n else n := n – m;
if m = 0 then k := n else k := m;
Bài toán 11. Cho hai số nguyên a và b không đồng thời bằng 0. Viết chương trình tính ước số chung lớn nhất của a và b là d=(a,b) và hai số nguyên x, y sao cho d=ax+by.
Phương pháp giải:
Thêm vào thuật toán Euclid trong bài trên các biến p, q, r, s và sử dụng các bất biến m = p*a + q*b; n=r*a + s*b
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
{bất biến: UCLN (a,b) = UCLN (m,n); m,n >= 0
m = p*a + q*b; n = r*a + s*b.}
while not ((m=0) or (n=0)) do
if m >= n then begin
m := m – n; p := p – r; q := q – s;
end else begin
n := n – m; r := r – p; s := s – q;
end;
end;
if m = 0 then begin
k :=n; x := r; y := s;
end else begin
k := m; x := p; y := q;
end;
Bài toán 12. Viết một phiên bản của thuật toán Euclid sử dụng các tính chất:
UCLN(2*a, 2*b) = 2*UCLN(a,b) nếu b chẵn
UCLN(2*a, b) = UCLN(a,b) nếu b lẻ
Thuật toán chỉ sử dụng phép chia cho 2 và phép kiểm tra tính chẵn lẻ.
Thuật toán phải có độ phức tạp là O(logk) với a, b <= k. Phương pháp giải: m:= a; n:=b; d:=1; {UCLN(a,b) = d * UCLN(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d*2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then m:= m div 2 else if (m mod 2 = 1) and (n mod 2 = 0) then n:= n div 2 else if (m mod 2=1) and (n mod 2=1) and (m >= n) then m:= m-n;
else if (m mod 2=1) and (n mod 2=1) and (m<=n) then n:= n-m; end; end; {m=0 => Kết quả=d*n; n=0 => Kết quả=d*m}
Đánh giá số bước thực hiện: cứ mỗi hai bước m và n lại giảm đi một nửa.
Sau khi học sinh nắm vững các thuật toán về ước chung lớn nhất ta lại tiếp tục cho học sinh làm quen với các thuật toán về số nguyên tố dưới góc độ lập trình.Các thuật toán về số nguyên tố cũng là những thuật toán không thể thiếu của một người lập trình. Đầu tiên ta xét bài toán: Kiểm tra một số tự nhiên có phải là số nguyên tố hay không? Đây là bài toán mà mọi người khi học lập trình đều phải biết thành thạo.
Bài toán 13. Kiểm tra một số tự nhiên có phải là số nguyên tố hay không?
Phương pháp giải:
Nhận xét: Bài toán này học sinh đã được tìm hiểu thuật toán từ lớp 10, nếu học sinh quên giáo viên có thể nêu lại thuật toán để học sinh nhớ lại. Ở đây ta chưa cần hướng dẫn cho học sinh thuật toán tốt để kiểm tra số nguyên tố.
Dùng biến nt kiểu boolean để kiểm tra N nguyên tố hay không? Khởi tạo nt nhận giá trị true, cho vòng lặp chạy từ 2 đến phần nguyên của căn bậc hai N, nếu tồn tại ước của N trong khoảng này thì nt nhận giá trị false đồng thời thoát khỏi vòng lặp để tiết kiệm thời gian thực hiện thuật toán.
Chương trình có thể như sau:
Var i,n: integer;
nt: boolean;
Begin
write(‘N = ‘);readln(n);
nt:=true;{Giả sử N là số nguyên tố, gán nt bằng true}
if n<=1 then nt:=false else for i:=2 to trunc(sqrt(n)) do if n mod i=0 then{Nếu n chia hết cho i thì} begin nt:=false;{Gán nt=false} break;{thoát vòng lặp bằng lệnh Break} end; if nt then writeln(N,’ So nguyen to’) else write(N, ‘Khong la so nguyen to’); End. Bài toán 14. Viết chương trình nhập vào từ bàn phím số nguyên N (N>10), in ra màn hình các số nguyên tố trong khoảng từ 1 đến N.
Phương pháp giải:
Nhận xét: Học sinh sẽ áp dụng thuật toán của bài 9 để giải quyết bài toán. Ta chỉ cần dùng thêm một vòng lặp chạy từ 2 đến N đặt ngoài vòng lặp của chương trình bài trên.
Var i, k, n: integer;
nt: boolean;
begin
write(‘N = ‘);readln(n);
For k:=1 to N do
begin
nt:=true;
if K<=1 then nt:=false else for i:=2 to trunc(sqrt(K)) do if k mod i=0 then begin nt:=false; break; end; if nt then write(k:5); end; end. Bài toán 15. Phân tích số Cho một số nguyên N chẵn. Viết chương trình phân tích N thành tổng 2 số nguyên tố. Nếu có in ra các cách phân tích.Ví dụ: 6 = 3+ 3 Phương pháp giải: Nhận xét: Học sinh sẽ vận dụng thuật toán của bài 1.13 và 1.14 để giải quyết bài toán này var n, i , j, k, m, d: longint; nt1, nt2: boolean; begin writeln(‘Nhap N = ‘); readln(N); for i := 2 to N-1 do {vong lap 1} begin {kiem tra xem so i co phai la so nguyen to hay khong} nt1 := true; for k := 2 to trunc(sqrt( i )) do {vong lap 2} if i mod k =0 then begin nt1 := false;{do i chia het cho k nen i khong nguyen to} break; end; if nt1 then {neu so i la so nguyen to thi tim so j la so nguyen to ma i+j=N} for j := i to N-1 do {vong lap 3} begin {kiem tra xem so j co phai la so nguyen to hay khong} nt2 := true; for m := 2 to trunc(sqrt( j )) do if j mod m = 0 then begin nt2 := false;{Gan nt2 = false, tuc la j khong la so nto} break; end; if nt2 then if i + j = N then begin writeln(N ,’ = ‘, i, ‘ + ‘, j); d := d+1; end; end; end; end. Bài toán 16. Viết chương trình phân tích một số tự nhiên n > 0 ra thừa số nguyên tố. Chỉ cần in ra các thừa số nguyên tố của n. Nếu n=1 thì không cần in ra thừa số nào.
Phương pháp giải:
Nhận xét: Bài này ta có thể có nhiều cách giải, tôi đưa ra hai cách phổ biến, trong đó nếu dùng cách 2 thì khi cần cải tiến ta dễ dàng thực hiện hơn.
Cách 1:
k := n;
{bất biến: tích của các số đã in và k bằng n, chỉ in ra các số nguyên tố}
while not (k = 1) do
begin
l := 2;
{bất biến: k không có ước số nào trong khoảng (1,l)}
while k mod l <> 0 do l := l + 1;
{l – ước số nhỏ nhất lớn hơn 1 của k, do đó cũng là số nguyên tố}
writeln (l);
k:=k div l;
end;
Cách 2:
k := n; l := 2;
{Tích của k và các số in ra bằng n; các số in ra là số nguyên tố;
k không có ước số nhỏ hơn l}
while not (k = 1) do
begin
if k mod l = 0 then
begin
{k chia hết cho l và không có ước số nào nhỏ hơn l}
k := k div l;
writeln (l);
end else l := l + 1;
{k không chia hết cho l}
end;
Bài toán 17. Số nguyên tố mersen
Số nguyên tố mersen là các số nguyên tố có dạng 2P -1 trong đó P cũng là số nguyên tố. In ra các số nguyên tố mersen<=N theo thứ tự tăng dần.s (N<=1000000)
MERSEN.INP MERSEN.OUT
40 3 7 31
Ví dụ:

Phương pháp giải:
– Đọc N; M:=2; P:=2;
– Trong khi M + Kiểm tra P có nguyên tố không?
+ Nếu P nguyên tố thì: M:=1;
Cho i:=1 to P làm M:=M*2;
M:=M-1;
Kiểm tra M có nguyên tố không?
Nếu M nguyên tố và (M<= N) thì in M
{Nếu không kiểm tra M<=N thì kết quả in ra số Mersen M có thể vượt quá N}
+ Tăng P:=P+1;
Chương trình chi tiết như sau:
const fi=’mersen.inp’;
fo=’ mersen.out’;
var n,i,p,m:longint; nt:boolean; f:text;
begin
assign(f, fi); reset(f);
read(f, n); close(f);
assign(f, fo); rewrite(f);
m:=2; p:=2;
while M<=n do begin
nt:=true;
for i:=2 to trunc(sqrt(p)) do if p mod i =0 then nt:=false;
if nt then begin
m:=1;
for i:=1 to p do m:=m*2;
m:=m-1;
for i:=2 to trunc(sqrt(m)) do
if m mod i = 0 then nt:=false;
if nt and( M<= n) then write(f,m,’ ‘); end; p:=p+1; end; close(f); end. Cuối cùng cho các em làm quen với một số thuật toán liên quan đến một số số có tính chất đặc biệt như số chính phương, số hoàn thiện, số Amstrong,hai số anh em, … Bài toán 18. Số hoàn hảo Số N được gọi là số hoàn hảo nếu tổng các ước thực sự của N bằng chính nó. Viết chương trình nhập từ bàn phím số nguyên dương N, thông báo ra màn hình SO HOAN HAO nếu N là số hoàn hảo, ngược lại thì thông báo KHONG. Phương pháp giải: Học sinh dễ dàng nhận thấy cách làm bài này rất đơn giản: Dùng vòng for cho i duyệt từ 2 đến N div 2, nếu N chia hết cho i thì tăng tổng ước là: TU:= TU+i. Kiểm tra xem tổng các ước đó có bằng N hay không? Chương trình như sau: Var i, TU, N: word; Begin Write(‘Nhap N=’); Readln(N); TU:=0; For i:=1 to N div 2 do If n mod i =0 then TU:= TU + i; If TU =N then Writeln(’SO HOAN HAO’) else writeln(‘KHONG’); End. Bài toán 19. Nguyên tố tương đương 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ố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên N, M. 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. Dữ liệu: Vào từ file NTTD.INP Chứa hai số nguyên dương N và M ( 1 ≤ N, M ≤ 10000). Kết quả: Ghi ra file văn bản NTTD.OUT là số 1 nếu hai số đó là nguyên tố tương đương và ghi 0 nếu hai số đó không phải là nguyên tố tương đương. Ví dụ: NTTD.INP NTTD.OUT 15 75 1 9 21 0 Phương pháp giải: Gọi dm là số các ước nguyên tố của m, dn là số các ước nguyên tố của n. Khởi tạo: dm:=0; dn:=0; Cho i chạy từ 2 đến m + Với mỗi i là ước của m kiểm tra xem i có nguyên tố ko? + Nếu i là nguyên tố thì dm:= dm+1; + Nếu i cũng là ước của n thì: + Chia N cho i đến khi không chia được + dn:=dn+1 + Nếu (n=1) và (dn=dm) thì m và n là nguyên tố cùng nhau. 2. Một số thuật toán cơ bản trên mảng Khi chuyển từ các bài toán chỉ sử dụng các kiểu dữ liệu cơ bản sang kiểu dữ liệu có cấu trúc chắc chắn các em học sinh sẽ thấy bỡ ngỡ, khó khăn ban đầu. Chính vì thế chúng ta cần phải giới thiệu cho các em hiểu bản chất của mảng, các kiến thức cơ bản và đặc trưng trọng của mảng, từ đó học sinh sẽ hiểu và muốn khám phá nó để giải quyết các bài toán mà về thuật toán đã biết rõ nhưng về tổ chắc chức dữ liệu chưa thể thực hiện được khi thiếu cấu trúc mảng. 2.1. Kiến thức cơ bản: Mảng là kiểu dữ liệu có cấu trúc, được xây dựng trên dãy các phần tử có cùng kiểu dữ liệu. Khi nói đến mảng ta cần xác định được: – Số phần tử của mảng – Chỉ số của mảng – Kiểu của các phần tử mảng Mảng là kiểu dữ liệu truy cập một cách trực tiếp, tức là thời gian chỉ định đến phần tử A[i] cũng giống như thời gian chỉ định đến phần tử A[j] với i khác j. 2.2. Một số thuật toán cơ bản trên mảng: Dạng 1: Duyệt để tìm kiếm trên mảng trên mảng Cho mảng một chiều A[1..N] gồm các phần tử nguyên, ta xét một số thuật toán cơ bản quan trọng về mảng: Có hai thuật toán tìm kiếm trên mảng được ứng dụng rộng rãi đó là: Tìm kiếm tuần tự và tìm kiếm nhị phân. Thuật toán 1: Tìm kiếm tuần tự Cho mảng A và phần tử X. Tìm kiếm xem phần tử X có xuất hiện trong mảng A hay không? Nếu có thì xuất hiện ở những vị trí nào? Ý tưởng thuật toán: Duyệt mảng từ vị trí đầu đến hết mảng, nếu gặp phần tử nào của mảng bằng X thì in ra vị trí, nếu duyệt hết mảng mà không tìm thấy thì thông báo không tìm thấy. Thể hiện thuật toán: Tim thay:=false; For i:=1 to N do if X= A[i] then begin writeln(‘ xuất hiện ở vị trí:’, i); timthay:=true; end; if not (tim thay) then writeln(‘ Khong tim thay’); Trong trường hợp chỉ cần xuất ra vị trí của một phần tử ta cải tiến lại chương trình để chương trình thực hiện nhanh hơn. timthay:=false; For i:=1 to N do if X= A[i] then begin writeln(‘ xuất hiện ở vị trí: ‘, i); timthay := true; break; end; if not (timthay) then writeln(‘ Khong tim thay’); Thuật toán 2: Tìm kiếm nhị phân Với mảng A đã được sắp xếp tăng dần, độ phức tạp của tìm kiếm tuần tự không đổi. Tận dụng thông tin của mảng đã được sắp xếp để giới hạn vị trí của giá trị cần tìm trong mảng.Thuật toán tìm kiếm nhị phân đã được trình bày chi tết trong phần thuật toán của sách giáo khoa lớp 10. Giải thuật: So sánh x với phần tử chính giữa của mảng A. Nếu x là phần tử giữa thì dừng Nếu không, xác định xem x có thể thuộc nửa trái hay nửa phải của A. Lặp lại 2 bước trên với nửa đã xác định. Bài toán 20. Tìm phần tử Min, Max của mảng A gồm N phần tử. Phương pháp giải: Ý tưởng thuật toán: Gán Min:= A[1] ( Max:= A[1] ). Ta duyệt từ phần tử thứ 2 đến cuối mảng, gặp phần tử A[i] nào bé hơn Min( lớn hơn Max) gán lại Min := A[i] ( Max := A[i]). Thể hiện thuật toán: Min:= A[1]; Max:=A[1]; For i:=2 to N do Begin if Min > A[i] then Min := A[i];
if Max < A[i] then Max := A[i];
end;
writeln(‘ Min = ‘, Min, ‘ Max = ‘, Max);
Bài toán 21. Viết chương trình nhập vào từ bàn phím số nguyên N và mảng A gồm N phần tử. Thông báo ra màn hình các số chẵn có trong mảng đã nhập và số lượng của chúng.
Phương pháp giải:
Ta duyệt từ đầu đến cuối mảng, tìm đồng thời in ra màn hình và đếm các số chẵn của mảng, có thể dễ dàng hoàn thành chương trình như sau:
Const Nmax=100;
Var A : array[1..Nmax] of integer;
I, dem, N: integer;
Begin
Writeln(‘Nhap n=’); Readln(N);
For i:=1 to N do
begin
writeln(‘nhap phan tu thu ‘,i); read(A[i]);
end;
Dem := 0;
{khoi tao bien dem=0 (chua dem duoc so nao thoa man)}
For i:=1 to N do
if A[i] mod 2 =0 then {Xu li luon cac phan tu cua mang}
begin
write(A[i],’ ‘); {in phan tu thoa man ra man hinh}
inc(dem); {tang bien dem len mot don vi}
end;
writeln;
writeln(dem); {in so luong ra man hinh}
end.
Bài toán 22. Cho mảng A gồm N số nguyên A[i] với A[1] <= A[2] <= … <= A[n]. Tìm số lượng số khác nhau trong mảng A.
Phương pháp giải:
Ta có thể giải bài toán bằng hai phương pháp khác nhau:
Cách 1:
i := 1; k := 1;
{ta bất biến: k – số lượng số khác nhau trong số các giá trị A[1]..A[i]}
while i <> n do begin
i := i + 1;
if A[i] <> A[i-1] then begin
k := k + 1;
end;
end;
Cách 2:
Kết quả bằng 1 cộng với số lượng chỉ số i từ 1 đến n-1 thoả mãn A[i]<>A[i+1].
k := 1;
for i := 1 to n-1 do begin
if A[i]<> A[i+1] then begin
k := k + 1;
end;
end;
Bài toán 23: Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, …. Dãy này cho bởi công thức đệ qui sau:
F1 = 1, F2 =1, Fn = Fn-1 + Fn-2 với n > 2
1. Chứng minh khẳng định sau:
Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong dãy số Fibonaci.
N = akFk + ak-1Fk-1 + …. a1F1
Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là akak-1…a2a1.
2. Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.
const
Inp = ‘P11.INP’;
Out = ‘P11.OUT’;
Ind = 46;
var
n: LongInt;
Fibo: array[1..Ind] of LongInt;
procedure Init;
var
i: Integer;
begin
Fibo[1] := 1; Fibo[2] := 1;
for i := 3 to Ind do Fibo[i] := Fibo[i – 1] + Fibo[i – 2];
end;
procedure Solution;
var
i: LongInt;
hfi, hfo: Text;
begin
Assign(hfi, Inp);
Reset(hfi);
Assign(hfo, Out);
Rewrite(hfo);
while not Eof(hfi) do
begin
Readln(hfi, n);
Write(hfo, n, ‘ = ‘);
i := Ind; while Fibo[i] > n do Dec(i);
Write(hfo, Fibo[i]);
Dec(n, Fibo[i]);
while n > 0 do
begin
Dec(i);
if n >= Fibo[i] then
begin
Write(hfo, ‘ + ‘, Fibo[i]);
Dec(n, Fibo[i]);
end;
end;
Writeln(hfo);
end;
Close(hfo);
Close(hfi);
end;
begin
Init;
Solution;
end.
Bài toán 24. ( Đề thi chọn HSG đồng bằng Duyên Hải 2010)
Tìm người quen
Có N người đứng xếp hàng thẳng trước rạp đợi để vào xem một buổi hòa nhạc. Trong thời gian chờ đến giờ vào xem, mọi người tranh thủ tìm ngư¬ời quen trong hàng. Hai ngư¬ời A và B đứng trong hàng có thể nhìn thấy nhau nếu hai người đó đứng ngay sát nhau hoặc giữa hai người không có người nào có chiều cao cao hơn hẳn chiều cao của người A và người B. Viết chư¬ơng trình xác định số những cặp hai người có thể nhìn thấy nhau khi đứng trong hàng.
Dữ liệu vào: đọc từ file QUEN.INP
– Dòng đầu chứa một số nguyên N ( 1≤ N ≤ 10000), số ngư¬ời đứng trong hàng.
– N dòng sau mỗi dòng ghi 1 số nguyên là chiều cao của mỗi ng¬ười với đơn vị chiều cao là nanomét. Chiều cao của mỗi ng¬ười nhỏ hơn 2 nanomét. Những chiều cao đã cho theo thứ tự tương ứng với những người đứng trong hàng.
Kết quả ghi ra file: QUEN.OUT gồm 1 số là số những cặp hai người có thể nhìn thấy nhau trong hàng.
Ràng buộc: 60% số Tests ứng với 60% số điểm của bài có (1 ≤ N ≤ 200)
Ví dụ:
QUEN.INP QUEN.OUT
7
2
4
1
2
2
5
1 10

Phương pháp giải:
Để giải bài này ta chỉ cần dùng vòng for duyệt lùi từ N-1 downto 1 để tìm kiếm trong mảng các phần tử thõa mãn yêu cầu đề bài. Chương trình ngắn gọn và đơn giản như sau:
const fi=’quen.inp’;
fo=’quen.out’;
var f:text;
a:array[1..10000] of longint;
i,j,n,dem,max:longint;
procedure docf;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do readln(f,a[i]);
close(f);
end;
procedure xd;
begin
max:=0;
for j:=i-1 downto 1 do
begin
if a[j]>a[i] then
begin
inc(dem); exit;
end;
if a[j]>max then max:=a[j];
if a[j]>=max then inc(dem);
end;
end;
begin
docf;
assign(f,fo);
rewrite(f);
dem:=0;
for i:=1 to n do xd;
writeln(f,dem);
close(f);
end.
Bài toán 25. Tìm kiếm vị trí xuất hiện của x trên mảng A. Thay thế những giá trị x thành y.
Ví dụ: A: 1 5 6 7 4 1 5 5 1 1
X=5 Y=15
Kết quả thay thế: 1 15 6 7 4 1 15 15 1 1
Phương pháp giải:
Xây dựng hàm tìm kiếm giá trị X trong mảng A, N phần tử. Sử dụng vòng lặp từ 0 đến N-1 để kiểm tra tất cả các giá trị Ai, nếu bằng x thì trả về vị trí i tìm thấy. Nếu thoát vòng lặp mà không tìm thấy thì trả về là –1.
Xây dựng hàm thay thế giá trị x bằng y tại vị trí tìm thấy đầu tiên. Tương tự như tìm kiếm, nhưng khi tìm thấy thì tiến hành gán giá trị mới cho Ai là y.
Xây dựng hàm thay thế tất cả các giá trị x bằng y tại mỗi vị trí tìm thấy. Sử dụng vòng lặp duyệt qua tất cả các giá trị của Ai, nếu Ai bằng x thì tiến hành gán thành y.
Sau đây ta xét bài toán tìm kiếm trên mảng hai chiều:
Bài toán 26. Điểm yên ngựa
Một phần tử được gọi là điểm yên ngựa nếu nó là bé nhất của hàng chứa nó nhưng lớn nhất của cột chứa nó. Cho N, M( N, M <= 100) và ma trận cấp NxM, tìm các điểm yên ngựa của ma trận. Nếu không có in ra số 0, nếu có dòng đầu tiên in ra số phần tử yên ngựa, dòng thứ 2 in ra tọa độ các điểm yên ngựa theo thứ tự dòng từu bé đến lớn và cột từ bé đến lớn. Ví dụ: YENNGUA.INP YENNGUA.OUT 4 4 7 9 8 10 5 1 2 1 7 9 9 10 4 6 9 10 2 1 1 3 1 Phương pháp giải: Với mỗi dòng: Ta duyệt từ phần tử đầu tiên của mỗi dòng đến phần tử cuối của dòng để tìm phần tử bé nhất, gọi là MIN Với mỗi cột, duyệt từ đầu cột đến cuối cột: nếu phần tử A[h, j] nào đó mà lớn hơn MIN thì: Không có yên ngựa, break. Ngược lại thì đó chính là điểm yên ngựa Dạng 2: Sắp xếp mảng Cho mảng A, ta sắp xếp mảng theo thứ tự tăng hoặc giảm, ta lấy ví dụ cho việc sắp tăng dần. Có nhiều thuật toán sắp xếp như: Sắp xếp đơn giản, sắp xếp nổi bọt, sắp xếp chèn, sắp xếp nhanh. Ta đi vào hai thuật toán được ứng dụng nhiều nhất. Thuật toán 1: Sắp xếp mảng bằng thuật toán đơn giản (Selection Sort) Ý tưởng thuật toán: Chia mảng A thành hai mảng: Mảng chưa sắp (CS) và mảng đã sắp (DS). – Khởi tạo: CS chính là mảng A, DS bằng rỗng. – Lấy phần tử đầu tiên của tập chưa sắp (CS), so sánh với mọi phần tử đứng sau nó, nếu thấy phần tử nào không thõa mãn điều kiện thì tráo đổi hai phần tử đó cho nhau. Đưa phần tử đầu tiên của mảng CS này vào mảng DS. – Lặp lại cho đến phần tử cuối cùng của mảng CS. Cuối cùng ta được mảng đã sắp xếp chính là mảng DS. Thể hiện thuật toán: For i:=1 to N-1 do For j := i+1 to N do if A[i] > A[j] then begin
tg:= A[i];
A[i]:= A[j];
A[j]:=tg;
end;
For i:=1 to N do write(A[i], ‘ ‘);
Thuật toán 2: Sắp xếp mảng bằng thuật toán nhanh( Quick sort)
Ý tưởng thuật toán:
Nội dung của phương pháp này là chọn phần tử x ở giữa của dãy làm chuẩn để so sánh. Ta phân hoạch dãy này thành 3 dãy con liên tiếp nhau:
– Dãy con thứ nhất gồm phần tử có khoá nhỏ hơn x.key.
– Dãy con thứ hai gồm các phần tử có khoá bằng x.key.
– Dãy con thứ ba gồm các phần tử có khoá lớn hơn x.key.
Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất nhất và dãy con thứ ba, nếu các dãy con có nhiều hơn một phần tử (Đệ qui).
Cụ thể là xét một doạn của dãy từ thành phần L đến thành phần thứ R.
– Lấy giá trị của thành phần thứ (L+R) Div 2 gán vào biến X.
– Cho i ban đầu là L.
– Cho j ban đầu là R.
– Lặp lại.
Chừng nào còn A[i] < X thì tăng i. Chừng nào còn A[j] > X thì giảm j.
i<=j thì + Hoán vị A[i] và A[j] + Tăng i + Giảm j Cho đến khi i>j
+ Sắp xếp đoạn từ A[L] đến A[j]
+ Sắp xếp đoạn từ A[i] đến A[R]
Ví dụ:
Sắp xếp dãy số:
39 50 7 37 89 13 1 62
X = 37
Sau 2 lần đổi chổ ta được dãy:
1 13 7 37 89 50 39 62
Xử lý dãy con:
1 13 7
Ta được:
1 7 13
Xử lý dãy con:
89 50 39 62
Ta được:
39 50 89 62
39 50 62 89
Vậy dãy đã sắp xếp là:
1 7 13 39 50 62 89
Thể hiện thuật toán:
Procedure Quick_Sort(Var A : Array[1..n] of Integer);
Procedure Sort(L,R : Integer);
Var i, j, Tg, X : Integer;
Begin
X := A[(L+R) Div 2];
i := L;
j := R;
Repeat
While (A[i] < X) do Inc(i); While (A[j] > X) do Dec(j);
If i <= j Then Begin Tg := A[i]; A[i] := A[j]; A[j] := Tg; Inc(i); Dec(j); End; Until i>j;
If L < j Then Sort(L,j);
If i < R Then Sort(i,R);
End;
Begin
Sort(1,n);
End;
Thuật toán 3: Sắp xếp bằng phép đếm phân phối ( Distribution Counting ).
Yêu cầu bài toán là cho một dãy khóa k1, k2,. . . , kn (nguyên không âm) và đưa ra dãy đã sắp tăng (hoặc giảm tùy ý).
Giả sử ta đã xây dựng được dãy c1, c2, …,cn+1) với ý nghĩa ci là số lần xuất hiện của giá trị i trong dãy số ban đầu. Dựa vào dãy biến đếm trên ta hoàn toàn có thể suy ra giá trị kj sẽ thuộc vào đoạn nào trong dãy sau khi sắp xếp. Cụ thể sau khi có dãy c ta xây dựng lại nó như sau:
c0= 0
c1= c0 + c1
c2 = c0 + c1 + c2
…
cn = c0 + c1 + c2 +..+ cn
Khi đó giá trị i trong dãy ban đầu khi được sắp tăng thì nó sẽ nằm ở đoạn ci-1 + 1 tới ci và ta dễ dàng suy ra dãy khóa sau khi sắp tăng dựa vào dãy c này.
Ta có cách cài đặt của thuật toán như sau:
Procedure DistributionCounting;
begin
fillchar(c, sizeof(c), 0);
for i := 1 to n do inc(c[k[i]]);
for i := 2 to n do c[i] := c[i-1] + c[i];
for i := n downto 1 do
begin
x[c[k[i]] := k[i];
{x là dãy khóa phụ chứa các giá trị của dãy k sau khi sắp}
dec(c[k[i]]);
end;
end;
Nhận xét: Thuật toán có độ phức tạp O(Max(M, n)) trong đó M là giá trị lớn nhất trong dãy số ban đầu, hơn hẳn thuật toán sắp xếp chèn và nổi bọt có độ phức tạp O(n2).
Bài toán 27. Cho mảng số nguyên A[1..n], hãy đảo ngược mảng mà không sử dụng thêm mảng phụ.
Phương pháp giải:
Số A[i] và A[n+1-i] cần phải được đổi chỗ với mọi i thoả i < n + 1 – i, <=> 2*i < n + 1 <=> 2*i <= n <=> i <= n div 2:
for i := 1 to n div 2 do
begin
… đổi chỗ A[i] và A[n+1-i];
end;
Bài toán 28. Cho mảng số nguyên X[1]..X[m+n] được nối từ hai phần: phần đầu X[1]..X[m] có độ dài m và phần cuối X[m+1]..X[m+n] có độ dài n. Không dùng thêm mảng phụ hãy tráo đổi phần đầu và phần cuối (độ phức tạp thuật toán là O(m+n)).
Phương pháp giải:
Cách 1: Ta sẽ lật ngược phần đầu và phân cuối một cách riêng biệt, sau đó ta sẽ lật ngược toàn bộ mảng một lần nữa.
Cách 2: Ta xét bài toán tổng quát hơn: tráo đổi hai đoạn của mảng X[p+1]..X[q] và X[q+1]..X[s]. Ta giả sử độ dài của đoạn bên trái (ký hiệu là A) không vượt quá độ dài của đoạn bên phải (ký hiệu là B). Ta xét đoạn đầu của B mà có độ dài bằng A và ký hiệu là đoạn B1, đoạn còn lại ký hiệu là B2. (Do đó B=B1 + B2 nếu dấu + biểu thị phép nối hai mảng). Ta phải biến đổi A + B1 + B2 thành B1 + B2 + A. Tráo đổi vị trí của A và B1 vì chúng có cùng độ dài, ta nhận được B1 + A + B2. Do đó ta cần tiếp tục tráo đổi vị trí của A và B2. Vậy ta đã giảm được kích thước của hai đoạn cần tráo đổi để giải bài toán tương tự với kích thước nhỏ hơn. Ta có chương trình:
p: = 0; q: = m; r: = m + n;
{bất biến: cần phải tráo đổi hai đoạn X[p+1]. X[q], X[q+1]. X[s]}
while (p <> q) and (q <> s) do begin
{cả hai đoạn đều không rỗng}
if (q – p) <= (s – q) then begin
Tráo đổi X[p+1]… X[q] và X[q+1]… X[q + (q-p)]
pnew: = q; qnew: = q + (q – p);
p: = pnew; q: = qnew;
end else begin
{Tráo đổi X[q – (r-q) +1].. X[q] và X[q+1].. x [r] }
qnew: = q – (r – q); rnew: = q;
q: = qnew; r: = rnew;
end;
end;
Đánh giá thời gian thực hiện: sau mỗi bước độ dài của mảng giảm đi nhỏ hơn độ dài A. Do đó số bước thực hiện tỉ lệ với độ dài A.
Bài toán 29. Băng nhạc
Tại một quầy băng đĩa người ta ghi các bài hát theo băng. Khi khách hµng chọn bài hát thứ I trong băng thì phải quay băng để bỏ qua i-1 bài hát trước đó. Thời gian quay băng bỏ qua mỗi bài hát và thời gian phát bài hát đó được tính là như nhau. Trung bình mỗi lượt khách đến các bài hát trong băng được họ lựa chọn là như nhau. Giả sử băng của chủ quán có dung lượng ghi vừa đủ N bài hát, với mỗi bài hát họ biết đựợc số phút phát ra.
Yêu cầu: Tìm cách ghi các bài hát vào băng của chủ quán để cho tổng thời gian quay băng trong mỗi lần khách đến là ít nhất?
Dữ liệu: Từ File CASSETTE.INP như sau:
– Dòng đầu tien là số N (1<=N<=1000) thể hiện số lượng bài hát,
– Dòng thứ hai là N số nguyên N, mỗi số là thời gian phát mỗi bài hát.
Yêu cầu: Ghi vào File CASSETTE.OUT như sau:
– N dòng sau mỗi dòng ghi hai số nguyên là thứ tự bài hát và thời gian tìm và phát bài hát đó.
– Dòng cuối ghi tổng thời gian phát băng đó nếu mỗi bài hát được phát một lần.
Ví dụ:
CASSETTE.INP CASSETTE.OUT
5
3 2 6 10 1 5 1
2 3
1 6
3 12
4 22
44
Phương pháp giải:
Dùng mảng A gồm N phần tử để lưu thời gian ghi và phát của mỗi bài hát, mảng B lưu vị trí của các bài hát được sắp xếp trong đĩa.
Ta sắp xếp mảng A theo thứ tự tăng dần, trong khi sắp xếp mảng A đồng thời sắp xếp mảng B để khi xuất sẽ xuất được vị trí bài hát tương ứng.
Khởi tạo biến S:=0; với S là tổng thời gian ghi và phát của mỗi bài. Biến T:=0, với T là tổng gian ghi và phát của đĩa.Khi đó ta chỉ việc duyệt từ đầu mảng A đến cuối mảng và tính tổng S, tổng T. Xuất mảng B theo mỗi dòng đông thời xuất giá trị S tương ứng.
Chương trình như sau:
Const Fi = ‘CASSETTE.INP’;
Fo = ‘CASSETTE.OUT’;
var a, b : array[1..100] of longint;
begin
assign(F, Fi);
reset(F);
readln(F, N);
for i:=1 to N do read(F, A[I]);
close(f);
asign(F, Fo); rewrite(F);
for i:=1 to n do
begin
B[i]:=i;
end;
S:=0;T:=0;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[j]<a[i] then
begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;

tg:=b[i];
b[i]:=b[j];
b[j]:=tg;
end;
for i:=1 to n do
begin
s:=s+a[i]; T:=T+S;
writeln(F,b[i],’ ‘,s);
end;
writeln(F,T);
close(F);
end.
Bài toán 30. Phần tử chung
Cho k dãy số nguyên, các số trong dãy thuộc đoạn [-109 .. 109]. Hãy viết chương trình tìm số xuất hiện trong cả k dãy. Nếu không có số nào xuất hiện trong cả k dãy thì ghi ký tự ‘x’, còn nếu có nhiều số cùng xuất hiện trong k dãy thì ghi số nhỏ nhất tìm được.
Dữ liệu: vào từ file PTC.INP:
– Dòng 1: chứa số nguyên dương;
– Dòng 2: gồm số lần lượt là độ dài từng dãy; dòng sau, mỗi dòng mô tả một dãy số, biết rằng tổng số lượng số trong dãy không vượt quá 500000 số.
Kết quả: Ghi ra file PTC.OUT: Ghi số tìm được hoặc ký tự ‘x’
PTC.INP PTC.OUT
2
3 4
1 2 3
4 3 2 -1
3
5 6 7
2 1 3 4 3
4 5 -1 0 0 3
11 4 7 8 9 0 3
2
3
Phương pháp giải:
Gọi là tổng số phần tử. Từ mỗi phần tử trong mỗi dãy tạo ra bộ gồm 2 thành phần: giá trị phần tử và chỉ số dãy, nhận được bộ. Sắp xếp các bộ tăng dần theo giá trị phần tử, nếu giá trị phần tử bằng nhau thì sắp xếp theo chỉ số dãy (chi phí O(nlogn)). Duyệt dãy đã sắp xếp, trong mỗi vùng giá trị bằng nhau kiểm soát xem có đủ k chỉ số khác nhau không, nếu có thì đó là giá trị cần tìm (chi phí O(n)). Độ phức tạp thuật toán: O(nlogn).
Với ví dụ 1:
Dãy 1 gồm 3 số 1 2 3, tạo ra 3 bộ (1,1), (2,1), (3,1)
Dãy 2 gồm 4 số 4 3 2 -1, tạo ra 4 bộ (4,2), (3,2), (2,2), (-1,2)
Sắp xếp các bộ: (-1,2), (1,1), (2,1), (2,2), (3,1), (3,2), (4,2)
Duyệt dãy đã sắp xếp, vùng giá trị 2 có đủ hai chỉ số khác nhau, giá trị cần tìm là 2.
Bài toán 31. Cho mảng a[1..n] và số b. Sắp xếp lại các số trong mảng sao cho các số bên trái của đường biên nhỏ hơn hoặc bằng b và các số bên phải của đường biên lớn hơn hoặc bằng b.
Phương pháp giải:
l:=0; r:=n;
{bất biến: a[1]..a[l]<=b; a[r+1]..a[n]>=b}
while l <> r do begin
if a[l+1] <= b then begin l:=l+1; end else if a[r] >=b then begin
r:=r-1;
end else begin {a[l+1]>b; a[r]<b} thay đổi a[l+1] và a[r] l:=l+1; r:=r-1; end; end; Bài toán 32. Hình chữ nhật lớn nhất. Cho một hình chữ nhật C kích thước m x n . Có k điểm nằm trong hình chữ nhật. Hãy tìm hình chữ nhật có diện tích lớn nhất nằm trong, có các cạnh song song các cạnh hình chữ nhật C, và không chứa bất kì điểm nào trong số các điểm đã cho. Dữ liệu: Dòng đầu ghi m, n, k K dòng tiếp theo ghi toạ độ của các điểm. Hệ trục toạ độ lấy một đỉnh C làm gốc, Ox, Oy song song với hai cạnh của C, sao cho toàn bộ C nằm trong góc phần tư thứ nhất của trục toạ độ. Kết quả: Một dòng ghi 5 số : diện tích, 4 số ghi toạ độ đỉnh trái trên, phải dưới của hình chứ nhật tìm được. Phương pháp giải: Ta sẽ xây dựng một thuật giải với độ phức tạp cỡ O(k2). Trước hết, ta sắp xếp các điểm theo thứ tự tăng dần của hoành độ. Ta xét từng điểm i . Với mỗi i, ta duyệt danh sách các điểm j có hoành độ lớn hơn i, theo chiều tăng của hoành dộ, với mỗi điểm j mới được duyệt, ta xác định dải lớn nhất hình chữ nhật song song với các trục toạ độ, kéo dài từ xi đến xj . Hình chữ nhật lớn nhất là một trong các dạng đó. Sau khi đã sắp xếp danh sách các điểm thì chương trình đơn giản, ta mô tả đoạn chương trình xét một điểm i như sau: Min = 0; Max = n; For j = i+1 to k Begin Kiểm tra hình chữ nhật (xi, min, xj, max) so với kết quả tối ưu hiện tại If (ỵj >= yi ) and (max > yj) max = yj;
If (ỵj <= yi ) and (min < yj) min = yj;
End;
Bài toán 33. Phần tử nhỏ hơn
Cho 1 dãy gồm n phần tử nguyên dương, n <= 105, các phần tử <= 109. Với mỗi vị trí i cần xác định f[i] = j thỏa mãn:
– j < i.
– a[j] < a[i]. – j nhỏ nhất có thể. – Nếu không có vị trí j thỏa mãn thì f[i] = 0. Dữ liệu: Đọc từ file nhohon.inp – Dòng đầu tiên ghi số n. – N dòng tiếp theo ghi n số là phần tử của dãy. Kết quả: Ghi ra file nhohon.out gồm N dòng, dòng thứ i là f[i]. nhohon.inp nhohon.out 4 1 2 3 1 0 1 1 0 Phương pháp giải: Ta sử dụng mảng V[i] với V[i]=i để ghi lại vị trí của các phần tử ban đầu. Sắp xếp không giảm mảng A, nếu có 2 phần tử A[i] = A[j] thì phần tử nào có vị trí ban đầu lớn hơn sẽ được xếp trước, đồng thời lúc đó ta cũng sắp xếp mảng V theo mảng A sau khi đã được sắp xếp. Lúc này ta chỉ cần làm việc trên mảng V. Cho 1 biến i chạy từ 1..N và 1 giá trị Min ban đầu = N+1. Nếu như tại vị trí i có V[i]>Min thì ta sẽ cập nhật cho mảng Kq[i]=min còn nếu không thì ta cập nhật Min=V[i]. Cuối cùng ta write ra mảng Kq.
Chương trình như sau:
Program bai33;
const fi = ‘nhohon.inp’;
fo = ‘nhohon.out’;
maxn = 100001;
var f, g :text;
n, m, i, j, k, l : longint;
a, v, kq : array[0..maxn] of longint;
procedure mofile;
begin
assign(f, fi); reset(f);
assign(g, fo); rewrite(g);
end;
procedure dongfile;
begin
close(f); close(g);
end;
procedure doc;
begin
readln(f, n);
for i:= 1 to n do
begin
readln(f, a[i]);
v[i] := i;
end;
end;
procedure swap(var x, y: longint);
var tg:longint;
begin
tg := x; x := y; y := tg;
end;
procedure sort(l, r: longint);
var i, j, x, y, k:longint;
begin
i := l; j := r; k := (l + r) div 2;
x := a[k]; y := v[k];
repeat
while (a[i] < x) or ((a[i] = x) and (v[i] > y)) do inc(i);
while (a[j] > x) or ((a[j] = x) and (v[j] < y)) do dec(j);
if i <= j then begin swap(a[i], a[j]); swap(v[i], v[j]); inc(i); dec(j); end; until i > j;
if i < r then sort(i, r);
if l < j then sort(l, j);
end;
procedure lam;
var min:longint;
begin
min := n + 1;
for i:= 1 to n do
begin
if min < v[i] then kq[v[i]] := min
else kq[v[i]] := 0;
if v[i] < min then min := v[i];
end;
for i:= 1 to n do writeln(g, kq[i]);
end;
begin
mofile;
doc;
sort(1, n);
lam;
dongfile;
end.
Dạng 3: Cắt mảng thành K đoạn thõa mãn điều kiện cho trước.
Một mảng gồm N phần tử, bài toán đặt ra là cắt mảng thành k đoạn thõa mãn một số điều kiện nào đó là bài toán được dùng nhiều trong xử lý mảng. Sau đây ta xét một số bài toán dạng cắt mảng và các bài toán ứng dụng của nó:
Bài toán 34. Cho mảng số nguyên A gồm N phần tử số nguyên, hãy cắt A thành 2 đoạn có tổng các phần tử trong đoạn này gấp K (K nguyên dương) lần tổng các phần tử trong đoạn kia.
Ví dụ: Mảng A gồm 3 phần tử: 5, 9, 1 và K= 2, khi đó t cắt được 2 đoạn là:
5 và 9, 1.
Phương pháp giải:
– Gọi S= A[1] + A[2] + …+ A[N]. Để chia A[1..N] thành 2 đoạn A[1..i] và A[i+1.. N] có tổng gấp K lần nhau ta phải có:
+ S chia hết K+1, đặt S1 := S div (K+1) và S2 := S- S1;
+ A[1] + A[2] + …+ A[i] = S1 hoặc A[1] + A[2] + …+ A[i] =S2.
– Khi đó điểm i là điểm cần chia.
Thể hiện thuật toán:
Begin
{ Nhập N, nhập A, Tính S = A[1] + A[2] + …+ A[N]}
If S mod (k+1) = 0 then begin
S1:=S div (K+1);
Chiahet:=false;
S2:=0;
for i:=1 to N do begin
S2:= S2+ A[i];
j:=i;
if (S2 = S1) or (S2 = S- S1) then begin
chiahet:= true; break; end;
end;
if chiahet then begin
for i:= 1 to j do write(A[i],’ ‘);
writeln;
for i:= j+1 to N do write(A[i],’ ‘);
end; end
else writeln(‘ khong chi duoc’);
end.
Bài toán 35. Tìm cách cắt dãy A gồm N ( N<=1000 ) các số nguyên dương thành k đoạn có tổng các phần tử trong mỗi đoạn bằng nhau, k nguyên dương
Dữ liệu: Vào từ file văn bản K_DOAN.INP dòng đầu gồm 2 số N và K, dòng sau gồm N số Integer.
Kết quả: Ghi ra file K_DOAN.OUT: Nếu không cắt được ghi -1, nếu được dòng i ghi đoạn thứ i tính từ trái sang.
Ví dụ:
K_DOAN.INP K_DOAN.OUT
7 4
3 1 2 2 4 1 3 0 3 1
2 2
4
1 3 0
Phương pháp giải:
Bài toán này hoàn toàn giống bài trên, chỉ thay điều kiện “cắt thành hai đoạn” bởi “cắt thành k đoạn” vì thế phương pháp giải cũng hoàn toàn giống bài toán mà chúng ta vừa xét chính vì thế tôi chỉ đưa ra chương trình để các bạn cùng tham khảo.
Program bai35;
const fi=’k_doan.inp’;
fo=’k_doan.out’;
var inp, oup: text;
a: array[0..1001] of longint;
sum: int64;
n, k: longint;
procedure openf;
begin
assign(inp,fi);reset(inp);
assign(oup,fo);rewrite(oup);
end;
procedure closef;
begin
close(inp);
close(oup);
end;
procedure input;
var i:longint;
begin
readln(inp,n,k);
sum:=0;
for i:=1 to n do
begin
read(inp,a[i]);
sum:=sum+a[i];
end;
end;
procedure solve;
var i,s:longint;
ok:boolean;
begin
if sum mod k<>0 then
begin
write(oup,-1);
exit;
end
else s:=sum div k;
sum:=0;
for i:=1 to n do
begin
sum:=sum+a[i];
if sum=s then sum:=0;
if sum>s then
begin
write(oup,-1);
exit;
end;
end;
sum:=0;
for i:=1 to n do
begin
if (sum=s)and(a[i]<>0) then
begin
writeln(oup);
sum:=0;
end;
sum:=sum+a[i];
write(oup,a[i],’ ‘);
end;
end;

procedure process;
begin
input;
solve;
end;
BEGIN
openf;
process;
closef;
END.
Không những trên mảng một chiều mà trên mảng hai chiều ta cũng có những thuật toán chia mảng rất thú vị, ta xét bài toán điển hình về chia mảng như sau:
Bài toán 36. Chia lưới
Cho lưới M x N (M, N <=20) ô vuông, trong mỗi ô cho trước một số tự nhiên. Hãy tìm cách chia lưới trên làm hai phần (chia theo cạnh lưới) sao cho giá trị tuyệt đối hiệu số của tổng các số trong mỗi phần có giá trị nhỏ nhất (như hình dưới đây).
0 0 0 0 7 0
0 1 3 5 0 0
0 12 2 5 0 0
0 9 2 10 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Dữ liệu vào: Từ file CHIALUOI.INP được cho như sau:
– Dòng đầu tiên gồm 2 số M, N là kích thước ô lưới.
– M dòng tiếp theo, mỗi dòng gồm N số cách nhau bởi dấu cách trống, ô nào không có giá trị được cho bằng 0.
Kết quả: ghi ra file CHIALUOI.OUT miêu tả lưới sau khi thành hai phần, là một ma trận kích thước M x N gồm các số 0 và 1 (số 0 ký hiệu cho các ô tương ứng với phần thứ nhất, số 1 ký hiệu cho các ô tương ứng với phần thứ hai).
Ví dụ:
CHIALUOI.INP CHIALUOI.OUT
5 6
0 0 0 0 7 0
0 1 3 5 0 0
0 12 2 5 0 0
0 9 2 10 0 0
0 0 0 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Phương pháp giải:
Ta dùng mảng hai chiều A kích thước MxN để lưu các giá trị của lưới, dùng thêm mảng hai chiều S để tính tổng các phần tử của mảng A trong mỗi thời điểm. Sử dụng tương tự thuật toán cắt mảng một chiều để chia mảng hai chiều với điều kiện độ chênh lệch của tổng các số trong mỗi phần có giá trị nhỏ nhất. Chương trình:
Program bai36;
const fi=’chialuoi.inp’;
fo=’chialuoi.out’;
var f:text;
a,s:array[0..100,0..100] of longint;
i,j,n,m,u,v,min,k:longint;
procedure docf;
begin
assign(f,fi);
reset(f);
readln(f,n,m);
for i:=1 to n do
for j:=1 to m do read(f,a[i,j]);
close(f);
end;
procedure xd1(i,j:longint);
begin
if i begin
write(f,1,’ ‘);
exit;
end;
if (i=u) and (j<=v) then
begin
write(f,1,’ ‘);
exit;
end;
write(f,0,’ ‘);
end;
procedure xd;
begin
min:=2000000;
for i:=1 to n do
for j:=1 to m do s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
for i:=1 to n do
for j:=1 to n do
begin
k:=(s[i,j]+s[i-1,m]-s[i-1,j]);
if abs((s[n,m]-k)-k) begin
min:=abs((s[n,m]-k)-k);
u:=i;
v:=j;
end;
end;
for i:=1 to n do
begin
for j:=1 to m do xd1(i,j);
writeln(f);
end;
end;
begin
docf;
assign(f,fo);
rewrite(f);
xd;
close(f);
end.
Dạng 4: Tìm đoạn con dài nhất của mảng thõa mãn điều kiện cho trước.
Bài toán 37. Cho dãy A gồm n số thực, một đoạn con của dãy A là một dãy con gồm các phần tử liên tiếp của dãy A. Hãy tìm đoạn con dài nhất của dãy số gồm các phần tử không giảm.
Ví dụ: cho dãy 12 số: 8 8 9 9 5 1 2 4 6 6 5 7
Đoạn con không giảm dài nhất là: 1 2 3 6 6
Phương pháp giải:
Ý tưởng giải bài toán :
Cho dãy: A1, A2,….., An.
Tìm đoạn con Ai , Ai+1 ,…..,Ai+k thỏa mãn: Ai+j <Ai+j+1 với 0 < j < k với k lớn nhất có thể. Cách 1. Ta giải quyết các bài toán con sau: – Tìm tất cả mọi đoạn con của dãy đã cho: Sử dụng 2 vòng For For i :=1 to n do For j:=i to n do { đoạn con bắt đầu từ chỉ số i đến chỉ số j} – Kiểm tra một đoạn con (từ i đến j) có là đoạn không giảm không? – Nếu đoạn con đúng là đoạn không giảm thì so sánh độ dài đoạn con vừa tìm được (độ dài=j-i+1) với những đoạn trước nếu lớn hơn thì lưu lại. Từ đây ta sẽ thấy việc giải quyết bài toán đã được chuyển thành việc giải quyết các bài toán con đơn giản hơn và quen thuộc hơn, điều đó sẽ giúp học sinh biết hướng giải quyết vấn đề từ đó thích thú và tích cực hơn với việc học. Đoạn chương trình như sau: Function Khonggiam(i, j:integer):boolean; Var k: integer; Begin Khonggiam:=true; For k:=i to j-1 do If A[k]>A[k+1] then begin khonggiam:=false; exit; end;
End;
{đoạn chương trình xét mọi đoạn con}
Procedure xuly;
Var i,j: integer;
Begin
For i:=1 to n do
For j:=i to n do
If khonggiam(i,j) then
{So sánh để tìm đoạn con tốt hơn và lưu lại}
If j-i+1> max then
Begin max:=j-i+1; luu:=i; end;
End;
Nhận xét: Ta thấy rằng việc xét tất cả mọi đoạn con như trên là không cần thiết do đó để tăng tốc chương trình ta cải tiến thuật toán như sau:
Cách 2: Từ việc phân tích bài toán với gợi ý là với mỗi i (1< i < n) tìm đoạn con không giảm(các phần tử liên tiếp) dài nhất bắt đầu từ Aj . So sánh các đoạn con tìm được để được đoạn con dài nhất.
Đoạn chương trình:
For i:=1 to n do {Xét mọi giá trị i}
Begin
{Tìm đoạn con không giảm dài nhất bắt đầu từ Aj}
j:=i;
While A[j]<A[j+1] do inc(j); if j-i+1 > max then {so sánh và luu}
begin
max:= j-i+1;
luu:=i;
end;
end;
Phân tích và gợi ý để học sinh cải tiến thuật giải tốt hơn: So với cách 1 thì cách 2 giảm bớt việc xét một số đoạn con không cần thiết vì với mỗi mốc i sẽ tìm ngay đoạn con dài nhất bắt đầu từ Ai chứ không xét mọi đoạn con bắt đầu từ Ai. Tuy nhiên ta thấy việc xét mọi giá trị i từ 1 đến n vẫn là không cần thiết vì khi tìm được một đoạn con là đoạn không giảm thì không cần quan tâm đến những đoạn con của nó vì chúng có độ dài bé hơn. Từ đó ta cải tiến thuật toán tốt hơn nữa như sau:
Cách 3: Bắt đầu từ i:=1, nếu từ chỉ số i đến j là đoạn không giảm thì đoạn tiếp theo được xét sẽ bắt đầu với i:=j+1 như vậy những đoạn con trong khoảng từ i đến j sẽ không bị xét lại.
Ví dụ với đoạn số: 2 2 5 1 2 3 7 7 4 9 thì sẽ chỉ xét so sánh 3 đoạn con:
2 2 5; 1 2 3 7 7; và 4 9.
Đoạn chương trình:
I:=1;
Repeat
J:=i;
While (A[j]<A[j+1]) and (j<n) do inc(j); {tìm đoạn con tăng bắt đầu từ i} If j-i+1>max then begin max:=j-i+1; luu:=i; end;
I:=j+1; {bắt đầu xét đoạn mới từ chỉ số j+1}
Until i>n;
Cách 3: đã giảm bớt việc xét nhiều đoạn con không cần thiết tuy nhiên vẫn phải xét các đoạn con và so sánh để tìm được đoạn con dài nhất, sẽ phức tạp nếu chúng ta giải bài toán mở rộng sau:
Bài toán mở rộng có thể được phát biểu như sau:
Thay vì chỉ đưa ra một đoạn con, bài toán yêu cầu đưa ra mọi đoạn con có cùng độ dài lớn nhất.
Nếu áp dụng thuật toán ở cách 3 với bài toán mở rộng thì phải thực hiện việc tìm kiếm 2 lần, lần đầu để tìm độ dài lớn nhất, lần 2 để đưa ra mọi đoạn con có cùng độ dài, hoặc phải dùng thêm mảng vừa tìm kiếm vừa lưu. Các cách giải quyết đó khà là rườm rà, phức tạp.
Gợi ý để học sinh tìm giải thuật tốt hơn đó là hãy xét các đoạn con có độ dài k giảm dần từ n về 1 khi đó đoạn con không giảm đầu tiên tìm được sẽ là đoạn dài nhất cần tìm vì nếu xét tiếp thì đoạn không giảm tiếp theo tìm được cũng không dài hơn. Và khi tìm được đoạn con không giảm nếu muốn đưa ra mọi đoạn thỏa mãn thì chỉ cần xét tiếp với các đoạn con cùng độ dài với đoạn đó.
Cách 4. Cho k :=n giảm dần về 1, với mỗi k xét các đoạn con có độ dài k, những dãy con đó sẽ có phần tử đầu chỉ nhận phần tử từ chỉ số 1 đến n-k+1, kiểm tra xem nó có là đoạn con không giảm hay không, nếu đúng thì đưa ra kết quả.
Chương trình đầy đủ cho bài toán theo cách 4 (tìm và đưa ra tất cả mọi đoạn con thỏa mãn) được viết như sau:
Program bai37;
Const fi = ’seq.inp’;
Fo=’seq.out’;
maxn=1000;
Var a: Array[1..maxn] of real;
n, i, k: integer;
f: text;
Procedure docfile; {đọc dữ liệu vào từ tệp}
Var i:integer;
Begin
Assign(f,fi);
Reset(f);
Readln(f,n);
For i:=1 to n do read(f,a[i]);
Close(f);
End;
function khonggiam(i,k:integer):boolean;
{Kiểm tra đoạn con bắt đầu từ chỉ số i và có độ dài k là đoạn không giảm?}
Var j: integer;
Begin
Khonggiam:=true;
For j:=i to i+k-2 do
if a[j]>a[j+1] then begin khonggiam:=false; exit; end;
end;
Procedure Xuat;
Var j:integer;
Begin
Assign(f,fo);
Rewrite(f);
For j:=i to i+k-1 do write(f, A[j],’ ’) { đoạn con không giảm}
Writeln(f);
End;
Procedure xuly;
Var ok:boolean;
Begin
Ok:=false;
For k:= n downto 1 do {k là độ dài đoạn con}
Begin
For i:=1 to n-k+1 do { đoạn con bắt đầu từ i}
If khonggiam(i, k) then begin Xuat; ok:=true; end;
If ok then exit;
End;
End;
Begin
Docfile;
Xuly;
Close(f);
End.
Thông thường, chương trình được lập có cấu trúc càng rõ ràng và hợp lý thì càng dễ thích nghi để giải bài toán hơi khác một chút, vì ta có thể dễ dàng tách các phần cần sửa đổi. Với dạng bài toán tìm đoạn con (các phần từ liên tiếp) dài nhất thỏa mãn một điều kiện nào đó, thì có thể dữ cấu trúc như ví dụ trên và chỉ cần thay điều kiện kiểm tra trong chương trình con kiểm tra đoạn con ở chương trình trên. Ví dụ bài toán sau đây ta thay điều kiện kiểm tra là: ‘đoạn con không giảm’ thành đoạn con có “ tổng các phần tử bằng giá trị K cho trước”.
Cũng như trong thuật toán về cắt đoạn trên mảng, thuật toán tìm đoạn con dài nhất trên mảng không những được thực hiện trên mảng một chiều mà trên mảng hai chiều ta cũng có những thuật toán tìm đoạn dài nhất, ta xét bài toán điển hình về tìm đoạn con dài nhất trên mảng hai chiều như sau:
Bµi toán 38. Có một chuỗi hạt gồm N hạt, mỗi hạt có màu ký hiệu bởi các số tự nhiên với số hạt tối đa là 256 hạt, sẽ được gọi là 1 đoạn nếu trong đoạn đó có cùng màu. Lập trình làm các việc:
– Vòng tròn đó có mấy màu?
– Nên cắt tại vị trí nào để khi duỗi thành hàng thẳng tống số hạt của đoạn đầu hàng và cuối hàng là lớn nhất. (Nếu có nhiều vị trí thõa mãn chỉ ra vị trí đàu tiên thõa mãn tính từ trái sang phải)
Dữ liệu: Tõ File văn bản CHUOIHAT.INP như sau:
– Dòng đầu tiên là số N (1<=N<=1000) số hạt của chuỗi hạt, – Dòng thứ hai là N số nguyên không âm bé hơn 365 là các hạt Kết quả: Ghi vào File CHUOIHAT.INP như sau: – Dòng đầu tiên là số đoạn của chuỗi hạt, – Dòng thứ hai là vị trí cần cắt Ví dụ: CHUOIHAT.INP CHUOIHAT.OUT 12 1 2 1 2 2 2 2 1 1 1 2 2 6 7 Phương pháp giải: Thực chất bài toán gồm hai ý: Ý thứ nhất: Vòng tròn đó có mấy màu? Chính là đếm xem trong mảng một chiều có mấy đoạn mà các phần tử của mỗi đoạn giống nhau. Thuật toán này ta đã thấy rõ trong dạng 3. Ý thứ hai: Nên cắt tại vị trí nào để khi duỗi thành hàng thẳng tống số hạt của đoạn đầu hàng và cuối hàng là lớn nhất? Chính là xét xem trong mảng (vị trí đầu mảng được xem là vị trí n+1) có hai đoạn nào thõa mãn tổng số phần tử của hai đoạn này là lớn nhất trong số các đoạn của mảng đã chỉ ra. Chương trình như sau: Program bài38; const fi = ‘chuoihat.inp’; fo = ‘chuoihat.out’; var f : text; A, B, C : array [1..257] of integer; tg, n, i, j, d, t, k, vt : integer; begin assign(f, fi); reset(f); readln(f, n); for i:=1 to n do read(f, A[i]); close(f); assign(f, fo); rewrite(f); c:=a; for i:=1 to n-1 do for j:=i+1 to n do if C[i]>C[j] then begin tg:= c[i]; c[i]:=c[j]; c[j]:=tg; end;
d:=1;
for i:=2 to n do if c[i]<>c[i-1] then inc(d);
writeln(f, d);
i:=1;k:=0;
while i<=N do begin t:=1; while a[i] = a[i+1] do begin t:=t+1; inc(i); end; inc(i); inc(k); B[k]:= t; end; t:=B[1] + b[2]; for i:=3 to k do if b[i] + b[i-1]> t then
begin
t := B[i] + B[i-1];
j := i-1;
end;
for i := 1 to j do vt := vt + B[i];
if (d = 1) then writeln(f, n)
else
if (B[1] + B[k] + B[2] > t) and (A[1] = A[n]) then writeln(f, B[1])
else if (B[1] + B[k] + B[k-1] > t) and (A[1] = A[n]) then writeln(f, B[k-1])
else if (B[1] + B[k] > t) and (A[1] <> A[n]) then writeln(f, n)
else writeln(f, vt);
close(f);
end.
Dạng 5: Một số số đặc biệt xử lý trên mảng
Trong Tin học có những số có tính chất tương đối đặc biệt, người lập trình cần biết cách xử lý các số này để ứng dụng trong những trường hợp cần thiết.
Bài toán 39. Số đẹp
Một số được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.
Ví dụ, 12 là một số đẹp vì 12+S22 = 5 là số nguyên tố.
Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1 trở đi.
Yêu cầu: Cho số nguyên n (1 ≤ n ≤ 1000000). Hãy tìm số đẹp thứ n.
Dữ liệu: Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên n.
Kết quả: Kết quả mỗi test đưa ra trên một dòng.
Ví dụ:
Beauty.inp Beauty.out
1
6 11
23
Phương pháp giải:
Thuật toán giải bài toán như sau:
– Duyệt từng số nguyên bắt đầu từ 1, tính tổng bình phương các chữ số và kiểm tra nếu tổng đó là số nguyên tố thì tăng biến đếm lên 1. Thực hiện cho đến khi biến đếm bằng n.
– Để tăng tốc chương trình có thể cải tiến khâu kiểm tra tổng bình phương các chữ số có nguyên tố hay không bằng cách chuẩn bị trước một mảng isPrime[0..9*9*10] of boolean, trong đó isPrime[x]=true nếu x là số nguyên tố. Như vậy việc kiểm tra tổng bình phương các chữ số có nguyên tố hay không chỉ mất O(1).
– Có thể áp dụng thuật toán quy hoạch động để giải bài toán với kích thước lớn hơn (n ≤ 1015).
Chương trình đầy đủ:
Program bài39;
const fi=’beauty.inp’;
fo=’beauty.out’;
var f:text;
a,b:array[1..2000000] of longint;
c:array[1..810] of boolean;
i,j,n,s,max:longint;
procedure docf;
begin
assign(f,fi);
reset(f);
n:=0;
while not eof(f) do
begin
inc(n);
readln(f,a[n]);
end;
close(f);
end;
function ktr1:boolean;
var j:longint;
begin
ktr1:=false;
for j:=2 to trunc(sqrt(i)) do if i mod j=0 then exit;
ktr1:=true;
end;
function ktr(i:longint):boolean;
var j:longint;
begin
s:=0;
while i<>0 do
begin
s:=s+sqr(i mod 10);
i:=i div 10;
end;
if c[s] then ktr:=true else ktr:=false;
end;
begin
docf;
max:=0;
j:=0;
for i:=2 to 810 do if ktr1 then c[i]:=true;
for i:=1 to n do if max<a[i] then max:=a[i];
j:=1;
i:=11;
b[1]:=11;
while j<=max do
begin
inc(i);
if ktr(i) then
begin
inc(j);
b[j]:=i;
end;
end;
assign(f,fo);
rewrite(f);
for i:=1 to n do writeln(f,b[a[i]]);
close(f);
end.
Bài toán 40. Số siêu nguyên tố
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 tạo thành một số nguyên tố.
Ví dụ 37337 là một số siêu nguyên tố có 5 chữ số vì 3733, 373, 37,3 cũng là các số nguyên tố.
Hãy viết chương trình đọc dữ liệu vào là một số nguyên N (0< N <10) từ bàn phím và đưa ra kết quả ra màn hình là các số siêu nguyên tố có N chữ số cùng số lượng của chúng.
Ví dụ:
Dữ liệu vào Dữ liệu ra
5 23333 23339 23399 23993 29399 31193 31379 37337 37339 37397 59393 59399 71933 73331 73939
Co 15 so sieu nguyen to co 5 chu so
Phương pháp giải:
– Viết hàm kiểm tra số nguyên tố (ngto(n)).
Ta có nhận xét: Từ định nghĩa về số siêu nguyên tố ta thấy các số siêu nguyên tố có N chữ số được xây dựng từ các số nguyên tố có một chữ số là 2, 3, 5, 7. Từ các số nguyên tố có một chữ số ta sẽ ghép chúng với các chữ số từ 0 đến 9 để được số có 2 chữ số và chỉ lấy các số có 2 chữ số là số nguyên tố vd 23, 29, 31…. Và cứ tiếp tục xây dựng các số nguyên tố như vậy cho đến khi đủ N chữ số.
– Dùng mảng A để tính và lưu các số siêu nguyên tố có 1, 2, …,n chữ số (lần lượt xây dựng từng số một)
– Dùng mảng B để lưu lại mảng A trươc đó có i chữ số để xây dựng các số siêu nguyên tố có i+1 chữ số.
Chương trình cụ thể như sau:
Program Bai40;
var a,b: array [1..100] of longint;
N,i,k,ka,kb,cs,t: byte;
kt:boolean;
m,j:longint;
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
begin
m:=a[k]*10+cs; {kiem tra xem m co la so nguyen to khong}
kt:=true;
If (m<=1) then kt:=false Else Begin for j:= 2 to trunc(Sqrt(m)) do If (m mod j =0) then begin kt:=false; break; end; End; {het doan lenh kiem tra so nguyen to} If kt then {neu la so nguyen to thi} Begin Inc(kb); b[kb]:=a[k]*10+cs; end; end; ka:=kb; For t:=1 to ka do a[t]:=b[t]; {luu lai cac gia tri cua mang b vao mang a} end; For k:=1 to ka do Write(a[k]:10); Writeln; Writeln(‘Co tat ca ‘,ka,’ so sieu nguyen to co ‘,N,’ chu so.’); Readln; end. Bài toán 41. Số hoàn hảo Trong một buổi học toán Bờm được học khái niệm về số có tính chất đặc biệt. Số hoàn hảo là số có tổng các ước trừ nó ra thì bằng chính nó. Ví dụ: Số 6 là là số hoàn hảo vì nó có tổng các ước 1 + 2 + 3 = 6, số 8 không phải là số hoàn hảo vì 1 + 2 + 4 = 7 ≠ 8. Yêu cầu: Cho dãy số a1, a2,… an. Hãy giúp Bờm đếm xem trong dãy có bao nhiêu số có tổng các chữ số là số hoàn hảo. Dữ liệu vào: Từ file SOHHAO.INP gồm: – Dòng đầu tiên là số nguyên dương n (n ≤ 100). – n dòng tiếp theo ghi n số nguyên a1, a2,… an (0 ≤ ai ≤ 109). Kết quả: Ghi ra file SOHHAO.OUT gồm: Một dòng duy nhất là kết quả của bài toán. Ví dụ: SOHHAO.INP SOHHAO.OUT 3 6 123 28 2 Phương pháp giải: Ở phần các dạng bài toán không dùng các cấu trúc dữ liệu ta đã biết cách kiểm tra một số tự nhiêu có hoàn hảo hay không. Ở bài toán này ta chỉ việc duyêt từ đầu đến cuối để kiểm tra xem có thõa mãn tổng các chữ số là số hoàn hảo hay không và đếm nó. Chương trình bài toán: const fi=’sohhao.inp’; fo=’ sohhao.out’; var i, x, dem, n:longint; f : text; d : array[0..81]of boolean; procedure taomang; var i, j, t:longint; begin for i:=2 to 81 do begin t:=0; for j:=1 to i-1 do if i mod j=0 then t:=t+j; if t=i then d[i]:=true; end; end; function cs(a:longint):byte; var t:longint; begin t:=0; while a>0 do
begin t:=t+a mod 10;
a:=a div 10;
end;
cs:=t;
end;
begin taomang;
assign(f,fi);reset(f);
readln(f,n);
dem:=0;
for i:=1 to n do
begin
read(f,x);
if d[cs(x)] then inc(dem);
end;
close(f);
assign(f,fo);rewrite(f);writeln(f,dem);
close(f);end.
3 Các thuật toán trên xâu
Để xử lý trên văn bản, Pascal cho phép dùng kiểu dữ liệu xâu ký tự. Xâu ký tự là dữ liệu bao gồm một dãy các ký tự trong bảng mã ASSCII.
Bài toán 42:Các số nguyên dương 3748, 58, 859, 32435465768 được gọi là các số đơn điệu do nếu quan sát các chữ số của số này ta thấy chúng luân phiên tăng giảm hoặc giảm tăng.
Ví dụ: Số 3748 ta thấy: 3 < 7 > 4 < 8 Số 32435465768 ta thấy: 3 > 2 < 4 > 3 < 5> 4 < 6 > 5 < 7 > 6 < 8 Số chỉ có một chữ số là số đơn điệu độ dài 1. Yêu cầu: Viết chương trình xác định số chữ số lớn nhất tạo thành số đơn điệu của một số cho trước. Dữ liệu: Vào từ file văn bản SDD.INP gồm một dòng duy nhất chứa số N nguyên dương có không quá 75 chữ số. Kết quả: Ghi ra file văn bản SDD.OUT chứa một số nguyên duy nhất là số chữ số lớn nhất tạo thành đoạn số đơn điệu của số N. Ví dụ: SDD.INP SDD.OUT 3748 4 Phương pháp giải: const fi = ‘sdd.inp’; fo = ‘sdd.out’; var f, g:text; n, max, dem:longint; d, a:array[1..1000] of byte; procedure mo; begin assign(f,fith); reset(f); assign(g,foth); rewrite(g); n:=0; readln(f,a); n:=length(a); end; procedure dong; begin close(f); close(g); end; procedure xuly; var i:byte; begin max:=0; dem:=0; fillchar(d,sizeof(d),0); for i:=2 to n-1 do if ((a[i]>a[i+1]) and(a[i]>a[i-1]))or ((a[i]<a[i+1]) and(a[i]<a[i-1]) ) then d[i]:=1; for i:=1 to n do if d[i]+d[i+1]=2 then begin inc(dem); if dem>max then max:=dem;
end
else
if (d[i]=1) and(d[i+1]=0) then dem:=0;
write(g,max+3);
end;
begin
mo;
xuly;
dong;
end.
Bài toán 43: Chèn Xâu
Cho một xâu S = ’123456789’ hãy tìm cách chèn vào S các dấu ‘+’ hoặc ‘-‘ để thu được số M cho trước (nếu có thể). Số M nguyên được nhập từ bàn phím. Trong file Output Chenxau.Out ghi tất cả các phương án chèn (nếu có) và ghi “Khong co” nếu như không thể thu được M từ cách làm trên.
Ví dụ: Nhập M = 8, một trong các phương án đó là: ‘-1+2-3+4+5-6+7’;
M = -28, một trong các phương án đó là: ‘-1+2-34+5’;
Do sơ xuất khi ra đề nên trong số các lời giải của bạn đọc gửi đến toà soạn, có thể các bạn đã hiểu đề bài theo 2 cách sau đây, ta coi như hai bài toán:
1. Nếu theo ví dụ, thì ta cần chèn dấu vào xâu (không cần đủ 9 số như trong xâu S, có thể bớt một số số cuối của xâu, nhưng phải theo thứ tự) để phép tính nhận được bằng M cho trước.
2. Ta không để ý đến ví dụ của đề ra, yêu cầu cần chèn dấu vào giữa các số trong xâu ‘123456789’ để nhận được kết quả M cho trước.
Program Bai43;
Uses crt;
Const fo = ‘chenxau.out’;
dau: array[1..3] of String[1]= (”, ‘-‘, ‘+’);
s:array[1..9] of char=(‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’);
Var d:array[1..9] of String[1];
m:longInt;
f:text;
k:integer;
found:boolean;
Procedure Init;
Begin
Write(‘Cho M=’); Readln(m);
found:=false;
end;
Function tinh(s:string):longint;
Var i,t:longint;
code:integer;
Begin
i:=length(s);
While not(s[i] in [‘-‘,’+’]) and (i>0) do dec(i);
val(copy(s,i+1,length(s)-i),t,code);
If i=0 then begin tinh:=t; exit; end
else
begin
delete(s,i,length(s)-i+1);
If s[i]=’+’ then tinh:=t+tinh(s);
If s[i]=’-‘ then tinh:=tinh(s)-t;
end;
end;
Procedure Test(i:integer);
Var st:string; j:integer;
Begin
st:=”;
For j:=1 to i do st:=st+d[j]+s[j];
If Tinh(st) = m then begin writeln(f,st); found:=true; end;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
for j:=1 to 3 do
begin
d[i]:=dau[j]; Test(i);
If i end;
End;
Begin
Clrscr;
Init;
Assign(f,fo);Rewrite(f);
for k:=1 to 2 do
begin
d[1]:=dau[k];
Try(2);
end;
If not found then write(f,’khong co ngiem’);
Close(f);
End.
PHẦN III. KẾT LUẬN:

Đối với các học sinh khá, giỏi việc tạo cho các em niềm say mê và biết cách suy nghĩ để lập trình một cách có phong cách ngay từ khi tiếp cận với bộ môn Tin học lập trình là việc làm quan trọng nhất của mỗi giáo viên. Có say mê và khả năng lập trình tốt giúp các em học tập hiệu quả, tạo cho các em một trình độ và đẳng cấp riêng không những giúp các em đạt kết quả cao trong các kỳ thi học sinh giỏi Tỉnh, học sinh giỏi Quốc gia, … mà còn giúp các em là những nhà kỹ sư tương lai có lòng say nghề và có phong cách làm việc chuyên nghiệp, hiệu quả. Những vấn đề của Tin học lập lập trình chính là cách tư duy trong cuộc sống, do đó việc tạo cho các em các khả năng này chính là tạo cho các em lòng yêu cuộc sống, có cách nhìn cuộc sống một cách tư duy lôgic khoa học và tràn đầy nhiệt huyết.
Đề tài này được áp dụng cho những học sinh khá giỏi môn Tin học, những học sinh có trí tuệ cao nhưng chưa bao giờ được tiếp xúc với bộ môn Tin học lập trình đã thu được nhiều kết quả tốt. Các em say sưa học tập, biết cách lập trình một cách có tư duy logic, giải quyết vấn đề một cách hiệu quả.
Trên đây là một số kinh nghiệm của bản thân sau một thời gian giảng dạy bộ môn tin học, đặc biệt là ngôn ngữ lập trình Pascal dành cho học sinh trung học cơ qua các năm. Trong khuôn khổ bài viết, với kinh nghiệm và vốn kiến thức có hạn tôi rất mong được sự góp ý, trao đổi từ các đồng nghiệp.
Tôi xin chân thành cảm ơn!
Đăk Nia, ngày 31 tháng 03 năm 2017
Người viết