SKKN Kinh nghiệm rèn luyện kỹ năng sử dụng cấu trúc lặp trong lập trình Pascal cho đội tuyển học sinh giỏi môn tin học lớp 11

I. MÔ TẢ SÁNG KIẾN:
1. Tình trạng các giải pháp đã biết:
Thực trạng bộ môn Tin học ở trường THPT Cảm Nhân thường ít được học sinh quan tâm và yêu thích. Nhất là chương trình tin học lớp 11 vì đây là một nội dung kiến thức đòi hỏi sự tư duy sâu và khả năng sáng tạo. Khác hẳn với chương trình tin học 10, 12 là các chương trình ứng dụng, dễ hiểu, dễ vận dụng, dễ hình dung. Do vậy mà đại đa số các em khi học về nội dung này đều cảm thấy khó tiếp cận và vẫn gặp phải một số khó khăn trong lập trình, chưa biết cách tối ưu hóa thuật toán, thậm chí còn mắc sai lầm khi lập trình giải các bài toán có sử dụng đến cấu trúc lặp.
Mặt khác. Một trong những yếu tố quan trọng và không thể thiếu của một chương trình là “việc điều khiển”, cụ thể là các cấu trúc điều khiển, cũng là thành tố kết hợp đồng thời giữa dữ liệu và tác vụ. Cấu trúc điều khiển là một trong các đặc trưng cơ bản của phương pháp lập trình cấu trúc. Trong đó người ta sử dụng ba cấu trúc điều khiển để tạo nên logic của chương trình. Mọi vấn đề về logic đều được giải quyết bằng cách sử dụng linh hoạt ba cấu trúc điều khiển đó là:   * Cấu trúc tuần tự; Cấu trúc rẽ nhánh; Cấu trúc lặp.
Điều này dẫn đến ý thức tự học và rèn luyện của học sinh chưa cao, đặc biệt là các em học để thi học sinh giỏi môn Tin lại càng khó. Trên cơ sở thực tế đó tôi đã viết ra Sáng kiến: “Giải pháp kĩ năng sử dụng cấu trúc lặp trong lập trình pascal cho đội tuyển học sinh giỏi lớp 11” nhằm cung cấp cho học sinh những kiến thức khái quát hơn về cấu trúc lặp và rèn luyện kỹ năng lập trình cho đội tuyển học sinh giỏi nhà trường thông qua một số bài toán cụ thể và đã áp dụng trong năm học trước và học kì 1 năm học này tại trường THPT Cảm Nhân.
2. Nội dung các giải pháp đề nghị công nhận sáng kiến:
2.1. Mục đích của Sáng kiến:
Góp phần đổi mới phương pháp dạy học sinh giỏi môn Tin học theo hướng phát huy tính tích cực, chủ động và sáng tạo của học sinh giúp học sinh tiếp thu tri thức một cách có hiệu quả.
Góp phần gây hứng thú học tập môn Tin học cho học sinh tham gia thi chọn học sinh giỏi, tránh việc học thụ động, học vẹt. Giúp học sinh lĩnh hội tri thức một cách khoa học, củng cố và khắc sâu kiến thức.
Qua đề tài này tôi mong muốn cung cấp cho học sinh một những vấn đề mà các em đang gặp phải về kĩ năng sử dụng cấu trúc lặp trong khi lập trình giúp các em chủ động hơn trong học tập, tích luỹ kiến thức, kỹ năng lập trình.
2.2. Nội dung của Sáng kiến:
Tất cả các nội dung, các ví dụ, bài tập trong đề tài này được xây dựng trên ngôn ngữ lập trình Pascal.
2.3. Tìm hiểu về Lặp
Đưa ra 2 bài toán đơn giản:
Bài toán 1: Tính và đưa kết quả ra màn hình tổng
S = 1+2+3+…+100
Bài toán 2: Tính và đưa kết quả ra màn hình tổng
S = 1+2+3+..+n+… cho đến khi S > 105
Với cả 2 bài toán trên, dễ thấy cách để tính tổng S có nhiều điểm tương tự:
• Xuất phát, S được gán giá trị 0;
• Tiếp theo công vào tổng S một giá trị i với i = 1,2,3,4,5,….
Việc cộng này được lặp lại một số lần.
Đối với bài toán 1, số lần lặp là 100 và việc cộng vào tổng S sẽ kết thúc khi thực hiện công việc 100 lần.
Đối với bài toán 2, số lần lặp chưa biết trước nhưng việc cộng vào tổng S sẽ kết thúc khi điều kiện S > 105 được thỏa mãn.
Nói chung, ta thấy trong một số thuật toán có những thao tác phải lặp đi lặp lại nhiều lần. Cấu trúc lặp mô tả thao tác lặp được phân biệt 2 loại là lặp với số lần biết trước và lặp với số lần chưa biết trước.
Các ngôn ngữ lập trình đều có các câu lệnh để mô tả cấu trúc lặp.
2.3.1. Lặp với số lần biết trước và câu lệnh FOR – DO
a. Ví dụ 1:
Viết chương trình in ra các số lẻ nhỏ hơn hoặc bằng n (0<=n<=106).
* Ý tưởng
– Sử dụng vòng lặp tiến với biến đếm i chạy từ đến n để duyệt lần lượt các số từ 1 đến n;
– Nếu i lẻ ( i mod 2 <> 0) thì in ra số i. * Code tham khảo
Program In_So_le; Uses crt;
var i,n: longint;
Begin
Clrscr;
Write(‘Nhap so n =’); readln(n);      For i:=1 to n do
if i mod 2 <>0 then Write(i,’, ‘);      readln end.
b. Ví dụ 2:
Viết chương trình đếm xem có bao nhiêu số lẻ trong đoạn từ 20 đến 100.
* Ý tưởng
– Dùng 1 biến đếm kiểu nguyên (dem) để đếm số lượng số lẻ. Ban đầu khởi tạo dem:=0;
– Sử dụng vòng lặp for tiến với biến đếm i chạy từ 20 đến 100 ( vì xét trong đoạn từ 20 đến 100 ( KH:[20,100] nên ta phải xét cả 2 đầu mút:  i=20 và i=100)
– Nếu i lẻ ( i mod 2 <> 0) thì tăng biến đếm dem lên 1 đơn vị.
* Code tham khảo
Program dem_So_le; Uses crt;
var i, dem: integer;
Begin
Clrscr;      dem:=0;
For i:=20 to 100 do
if i mod 2 <>0 then inc(dem);      write(‘Co ‘,dem,’ so le trong doan tu 20 den 100’);
readln end.
c. Ví dụ 3:
Viết chương trình đếm xem có bao nhiêu số chẵn, bao nhiêu số lẻ trong khoảng từ n đến m (0<n<m<=1019).
* Ý tưởng
– Dùng 2 biến đếm kiểu nguyên (d_chan, d_le) để đếm số lượng số chẵn và
số lượng số lẻ. Ban đầu khởi tạo d_chan:=0;     d_le:=0;
– Sử dụng vòng lặp for tiến hoặc lùi với biến đếm  i chạy từ n+1 đến m-1
– Nếu i chẵn ( i mod 2 = 0) thì tăng biến d_chan lên 1 đơn vị. Nếu i lẻ ( i mod 2 <> 0) thì tăng biến d_le lên 1 đơn vị. * Code tham khảo
Program dem_So_chan_le_2; Uses crt;
var i,n,m, d_chan, d_le: qword;
Begin
Clrscr;
Write(‘Nhap so n =’); readln(n);      Write(‘Nhap so m =’); readln(m);      d_chan:=0;      d_le:=0;
For i:=n+1 to m-1 do
if i mod 2 <>0 then inc(d_le)                                else inc(d_chan);
Writeln(‘Co ‘,d_chan,’ so chan trong khoang tu ‘,n,’ den ‘,m);     Writeln(‘Co ‘,d_le,’ so le trong khoang tu ‘,n,’ den ‘,m);      readln end.
d. Ví dụ 4:
Một số có tổng các ước  thực sự (là các ước không kể chính nó) bằng chính nó được gọi là số hoàn chỉnh.
Ví dụ: Số nguyên 6 có các ước thực sự là 1, 2, 3. Tổng là 1 + 2 + 3 = 6.
Viết chương trình xét xem một số n (n<1018) được nhập từ bàn phím có phải là số hoàn chỉnh không.
* Ý tưởng
– Dùng biến n lưu số cần xét.
– Biến S lưu trữ tổng các ước thực sự, khởi tạo s:= 0;
– Sử dụng vòng lặp for với biến đếm i chạy từ 1 đến n-1. nếu i là ước của n thì cộng thêm i vào S.
– Nếu S = n thì đưa ra thông báo n là số hoàn chỉnh, ngược lại đưa ra thông báo n không là số hoàn chỉnh .
* Code tham khảo
Program So_Hoan_Chinh;
uses crt; var n, i, s: int64; begin
write(‘nhap so n: ‘);readln(n);                s:=0;
for i:= 1 to n -1 do
if n mod i = 0 then s:=s+i;
if s = n then write(n, ‘ la so hoan chinh’)                  else writeln(n, ‘ khong phai la so hoan chinh’);            readln end.
* Nhận xét
Ước lớn nhất của số nguyên N không kể chính nó luôn <= N div 2. Vì vậy, thay vì duyệt i từ 1 đến n-1 ta chỉ cần duyệt i từ 1 đến n div 2, việc làm này sẽ làm giảm đáng kể số lần lặp do đó có thể tiết kiệm time chạy chương trình (nhất là với n lớn). Chương trình giải bài toán trên có thể được cài đặt lại như sau:
Program So_Hoan_Chinh;
uses crt; var n, i, s: int64;
begin
write(‘nhap so n: ‘);readln(n);                  s:=0;
for i:= 1 to n div 2 do                                 if n mod i = 0 then s:=s+i;
if s = n then write(n, ‘ la so hoan chinh’)                   else writeln(n, ‘ khong phai la so hoan chinh’);            readln end.
e. Ví dụ 5:
Viết chương trình tìm các số hoàn chỉnh nhỏ hơn n (n<1015).
* Ý tưởng
– Sử dụng 2 vòng lặp for lồng nhau để kiểm tra tính hoàn hảo của các số từ 1 đến n-1.
* Code tham khảo
Program Tim_uoc_2;
uses crt;
Var S, n, i, j: longint; Begin
clrscr;
Write(‘Nhap so n =’); readln(n);
For i:=1 to n-1 do
Begin
S:=0;
For j:=1 to i div 2 do                                               if i mod j = 0 then S:=S+j;                                        if S = i then write(i,’,  ‘);                           end;
readln end.
g. Ví dụ 6:
Viết chương trình xét xem một số n có phải là số nguyên tố không (0<n<=105)?
Số nguyên tố là số chỉ có 2 ước là 1 và chính nó
* Ý tưởng
– Nếu n không chia hết mọi số i trong đoạn từ 2 đến n – 1  thì n là số nguyên tố.
– Sử dụng biến ok có kiểu boolean và có giá trị ban đầu là true.
– Cho biến i chạy từ 2 đến n – 1. Xét n mod i = 0 thì gán ok = false.
– Nếu ok = true thì n là số nguyên tố, ngược lại thì n không phải là số nguyên tố
* Code tham khảo
Program Nguyen_to_1;
uses crt; var n, i: integer;      ok: boolean;
begin
ok:=true;
write(‘Nhap n: ‘);readln(n);                       for i:= 2 to n-1 do
if n mod i = 0 then    ok :=false;                       if ok then write(n,’ la so nguyen to’)              else write(n, ‘ khong la so nguyen to’);          readln end.
* Nhận xét  + Ở đây ta sử dụng biến có kiểu logic (Đúng, sai). Chỉ cần một lần n mod i = 0 thì sau khi thực hiện xong vòng lặp ok có giá trị là false.
+ Mọi số nguyên N nếu có ước khác 1 và chính nó thì chắc chắn có ước trong đoạn từ 2 đến phần nguyên căn bậc 2 của N. Vì vậy thay vì kiểm tra n có chia hết cho số nào trong đoạn từ 2 đến n -1 hay không, ta chỉ cần kiểm tra n có chia hết cho số nào trong đoạn từ 2 đến trunc(sqrt(n)) hay không, việc làm này sẽ giúp giảm đáng kể số lần lặp, giúp tiết kiệm thời gian thực hiện chương trình.
Giá trị của N Các ước của N ( Khác 1 và N) Trunc(sqrt(n))
2 1
3 1
4 2 2
5 2
6 2,  3 2
7 2
8 2,  4 2
9 3 3
10 2,  5 3
11 3
12 2,3,  4,6 3
13 3
14 2,  7 3
15 3,  5 3
16 2,4,  8 4
17 4
18 2,  6,9 4
Chương trình trên có thể được viết lại như sau: