Tài liệu Skkn một số biện pháp rèn luyện kỹ năng giải bài toán truy hồi bằng cấu trúc lặp trong pascal trong tin học thpt

SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI: "MỘT SỐ BIỆN PHÁP RÈN LUYỆN KỸ NĂNG GIẢI BÀI TOÁN TRUY HỒI BẰNG CẤU TRÚC LẶP TRONG PASCAL" 1 A. ĐẶT VẤN ĐỀ I. Lời mở đầu : Sự phát triển mạnh mẽ của công nghệ thông tin đã làm cho xã hội có nhiều nhận thức mới về cách tổ chức các hoạt động. Nhiều quốc gia trên thế giới ý thức được rất rõ tầm quan trọng của tin học và có những đầu tư lớn cho lĩnh vực này, đặc biệt trong giáo dục nhằm nâng cao dân trí về tin học và đào tạo nguồn nhân lực có chất lượng cao. Người Việt Nam có nhiều tố chất thích hợp với ngành khoa học này, vì thế chúng ta hi vọng có thể sớm hoà nhập với khu vực và trên thế giới về tốc độ phát triển nền công nghệ thông tin. Đảng, Nhà nước ta đã nhận thấy được tầm quan trọng của ngành Tin học và đã đưa môn học này vào nhà trường phổ thông như những môn khoa học khác bắt đầu từ năm học 2006-2007. Bộ trưởng Bộ GDĐT cũng đã đưa ra chỉ thị số 55/2008/CT- BGTĐT ngày 30/9/2008 về tăng cường giảng dạy, đào tạo và ứng dụng công nghệ thông tin trong ngành giáo dục giai đoạn 2008-2011. Ngành Giáo dục và Đào tạo đang nỗ lực đổi mới phương pháp dạy học theo hướng phát huy tính tích cực chủ động của học sinh. Cốt lõi của việc đổi mới phương pháp dạy học ở trường phổ thông là giúp học sinh hướng tới việc học tập chủ động, chống lại thói quen học tập thụ động, học sinh có thể tự học, tự rèn luyện thông qua một số bài tập, dạng bài tập cụ thể. II. Thực trạng của vấn đề nghiên cứu : 1. Thực trạng : Tin học là một môn học mới ở các trường phổ thông nên học sinh còn nhiều bỡ ngỡ khi tiếp cận với môn học này. Trong đó nội dung tin học lớp 11 là một nội dung tương đối khó với đa số học sinh. Việc học ngôn ngữ lập trình Turbo Pascal là khởi đầu cho việc tiếp cận ngôn ngữ lập trình bậc cao. Học sinh được làm quen với nhiều khái niệm, thuật ngữ, cấu trúc dữ liệu qua đó giúp các em hình dung được sự ra đời, cấu trúc, hoạt động cũng như ích lợi của các chương trình hoạt động trong máy tính, các máy tự động… Và để làm được việc đó cần có một quá trình nghiên cứu, học tập về ngôn ngữ lập trình lâu dài. Cấu trúc lặp là cấu trúc thường được sử dụng để lập trình giải các bài toán, trong đó có các bài toán truy hồi. Tuy nhiên một số học sinh khi gặp các bài toán truy hồi các em khó xác định được công thức truy hồi của bài toán, đồng thời không biết nên dùng cấu trúc lặp nào để giải bài toán đó. Chính vì vậy, học sinh cảm thấy chán nản, không muốn tìm hiểu và rèn luyện kĩ năng lập trình. Mặt khác với một số đối tượng học sinh khá, giỏi, đa phần các em rất hào hứng với việc học lập trình, cụ thể là ngôn ngữ lập trình Turbo 2 Pascal. Do đó các em muốn tìm hiểu sâu hơn về một số bài toán truy hồi mà có thể áp dụng cấu trúc lặp để giải. Giáo viên nên tích cực khai thác vốn hiểu biết của học sinh để vận dụng, liên hệ một số ví dụ mở rộng, nâng cao với đối tượng học sinh này. 2. Kết quả của thực trạng trên : Trên cơ sở nhiều năm được phân công dạy khối lớp 11, trường THPT Hậu Lộc 4, tôi đã lưu lại kết quả học tập và sự tiến bộ của học sinh ở mỗi năm học ở một số lớp để có sự đối chiếu và rút kinh nghiệm. - Bảng số liệu kết quả đạt được khi sử dụng cấu trúc lặp trong Pascal để giải các bài toán truy hồi của học sinh lớp 11 năm học 2011-2012 khi chưa thực hiện đề tài: STT Lớp Sĩ số Đạt cầu yêu Không đạt yêu cầu 1 11A1 49 56% 44% 2 11A5 48 62.5% 37.5% 3 11A 50 8 12% 88% - Khi thực nghiệm qua các đối tượng học sinh đã nêu trên, đa số các em còn chưa biết cách sử dụng cấu trúc lặp trong Pascal phù hợp với từng bài toán cụ thể. - Một số không ít học sinh khi giải bài toán có dạng truy hồi chưa phân biệt được nên sử dụng cấu trúc lặp với số lần biết trước hay chưa biết trước. Xuất phát từ cơ sở trên, tôi mạnh dạn đề xuất SKKN “Rèn luyện kĩ năng sử dụng cấu trúc lặp trong Pascal để giải một số bài toán truy hồi cho học sinh lớp 11”. B. GIẢI QUYẾT VẤN ĐỀ I. Bài toán truy hồi và cấu trúc lặp : 1. Bài toán truy hồi : Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để giải một số bài toán. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Chẳng hạn với bài toán cấp số cộng là một ví dụ : 3 U0  a � với a là một số cho trước và d là hằng số cố định (công U  U  d (  n � 1) n 1 �n Cho � sai). - Nếu n là biết trước thì việc xác định số U n phải được thực hiện thông qua n bước lặp theo công thức truy hồi. - Nếu n là không được biết trước mà U n cần phải thỏa mãn một điều kiện nào đó thì việc xác định Un là quá trình lặp với số lần chưa biết trước nhưng thỏa mãn điều kiện. Nhiều bài toán truy hồi có thể phải thực hiện rất nhiều lần và các số tính toán có thể rất lớn, nếu thực hiện việc tính toán mà không sử dụng đến máy tính là vô cùng khó khăn. Một trong những đặc trưng của máy tính là có khả năng thực hiện có hiệu quả các thao tác lặp trong thời gian rất nhanh. 2. Cấu trúc lặp trong Pascal : Tất cả các ngôn ngữ lập trình đều có câu lệnh để mô tả cấu trúc lặp. Trong ngôn ngữ lập trình Pascal ta có thể sử dụng 2 loại câu lệnh mô tả cấu trúc lặp là : * Loại 1: Lặp với số lần biết trước : - Dạng lặp tiến : for := to do ; - Dạng lặp lùi : for := downto do ; * Loại 2: Lặp với số lần chưa biết trước: - Kiểm tra điều kiện trước: While <điều kiện> do ; - Kiểm tra điều kiện sau: Repeat ;... until <điều kiện>; II. Sử dụng cấu trúc lặp để giải bài toán truy hồi : 1. Sử dụng cấu trúc For … To... Do... * Cấu trúc: 4 for := to do ; * Trong đó: - for, to, do là các từ khoá. - là một biến có kiểu đếm được (nguyên, kí tự, liệt kê, logic…) - , là các biểu thức có giá trị cùng kiểu với - là một câu lệnh, có thể là câu lệnh đơn hoặc câu lệnh phức. * Hoạt động: Câu lệnh viết sau từ khóa do sẽ được thực hiện tuần tự, với biến đếm lần lượt nhận các giá trị liên tiếp tăng từ giá trị đầu đến giá trị cuối, nếu giá trị đầu lớn hơn giá trị cuối thì vòng lặp không được thực hiện. Ví dụ 1: Với a là số nguyên và a > 2, tính tổng: S 1 1 1 1    ...  a a 1 a  2 a  100 (SGK Tin học 11 – Trang 42) Phân tích: Với bài toán trên dễ thấy ta có công thức truy hồi để tính giá trị S như sau: S0  1 a S n  S n 1  1 an Với n = 1→100 Việc cộng vào tổng S được lặp lại 100 lần, giá trị n khi tham gia vòng lặp là 1 và sau mỗi lần lặp n tăng lên 1 cho đến khi n > 100 thì dừng. Như vậy số lần lặp là biết trước, biến n được sử dụng là một biến đếm từ 1 đến 100. Từ đó ta có chương trình: program vidu1; var s:real; n,a : integer; begin clrscr; 5 writeln(' Hay nhap gia tri a (a>2):'); readln(a); s := 1.0/a; for n := 1 to 100 do s := s + 1.0/(a+n); writeln('Tong s la: ',s:8:4); readln; end. Ví dụ 2: Lập trình tính giai thừa của một số nguyên n (do giới hạn lưu trữ số nguyên cho n<8). Phân tích: Giai thừa của n: n! = 1.2…n (tích các số tự nhiên từ 1 đến n). Không có công thức tổng quát để tính n! nhưng ta có công thức truy hồi sau:  0! 1   n! n.(n-1)! Đặt gn=n!, theo công thức trên ta có: g 0 =1 � � g n =g n-1.n � Như vậy ta có chương trình tính giai thừa như sau: program Vidu_2; var n, i, g : integer; begin writeln('Chuong trinh tinh n! '); write('Nhap (n<8): '); readln(n); g := 1; for i := 1 to n do g := g * i; 6 writeln('Ket qua: ',n,'! = ',g); readln; end. Ví dụ 3: Dãy số Fibônaxi được định nghĩa như sau: f1 =1, f 2 =1 � � f n =f n-1 +f n-2 (n >=3) � Viết chương trình in ra các số Fibônaxi với từ 1 đến 20. Phân tích: Ta dễ dàng tìm ra cách tính: cho i chạy từ 3 đến 20 rồi tính fi theo định nghĩa: fi = fi-1 + fi-2 . Ban đầu đặt biến f1 := 1; f2 := 1; sử dụng biến f0 để tính f i ứng với mỗi giá trị của i, do đó ta có thể viết f0:= f1+f2 theo công thức truy hồi; sau đó f1 và f2 được thay đổi giá trị để tính phần tử tiếp theo. Toàn văn chương trình: program Vidu_3; var i, f0, f1, f2 : integer; begin writeln('Chuong trinh tinh cac so Fibonaxi tu 1 den 20 '); f1 := 1; f2 := 1; writeln('F1 = 1'); writeln('F2 = 1'); for i := 3 to 20 do begin f0 := f1 + f2; writeln('F',i,' = ',f0); f1 := f2; f2 := f0; end; 7 readln; end. 2. Sử dụng cấu trúc for... downto... do ... * Cấu trúc: for := downto do ; * Trong đó: - for, downto, do là các từ khoá. - là một biến có kiểu đếm được (nguyên, kí tự, liệt kê, logic…) - , là các biểu thức có giá trị cùng kiểu với - là một câu lệnh, có thể là câu lệnh đơn hoặc phức. * Hoạt động: Câu lệnh viết sau từ khóa do sẽ được thực hiện tuần tự, với biến đếm lần lượt nhận các giá trị liên tiếp giảm từ giá trị đầu đến giá trị cuối, nếu giá trị đầu nhỏ hơn giá trị cuối thì vòng lặp không được thực hiện. Hoạt động của cấu trúc for … downto … do cũng tương tự cấu trúc for …to … do, chỉ khác là biến đếm là đếm ngược. Trong đa số trường hợp cả hai có tác dụng như nhau. Ví dụ 4: Lập trình tính tổng sau: Y = 50 n �n+1 (SGK Tin học 11 – Trang 51) n=1 8 Phân tích: Với bài toán trên có thể sử dụng cấu trúc lặp với số lần biết trước dạng tiến hay lùi đều được. Nếu sử dụng cấu trúc lặp For …downto … do ta có thể xây dựng công thức truy hồi để tính giá trị Y như sau: Yn  0 Yn 1  Yn  n n 1 Với n từ 50 giảm dần về 1 Việc cộng vào tổng Y được lặp lại 50 lần, giá trị n khi tham gia vòng lặp là 50 và sau mỗi lần lặp n giảm đi 1 cho đến khi n =1 thì dừng. Như vậy số lần lặp là biết trước, biến n được sử dụng là một biến đếm giảm từ 50 về 1, tổng cần tính là Y0 Ta viết chương trình như sau: program vidu_4; var Y: real; n : integer; begin clrscr; Y := 0; for n := 50 downto 1 do Y := Y + n/(n+1); writeln('Tong Y la: ',Y:10:4); readln; end. Tuy nhiên trong một số trường hợp thì chỉ có thể dùng một cấu trúc, đặc biệt là khi tính các công thức truy hồi. Ta xét một ví dụ dùng for … downto … do thích hợp hơn: Ví dụ 5: Tính tổng S = 2  4  ... 2n với n là một số tự nhiên nhập từ bàn phím. n dấu căn 9 Phân tích: Đặt si  2i  2(i  1)  ... 2n � s n 1  0 , s n  � � si  2i  si 1 � ta có công thức truy hồi sau: 2n Tổng cần tính là s 1. Công thức truy hồi là truy hồi ngược (vì tính si qua s i+1) nên dùng for … down … to là thích hợp nhất. Có thể viết đoạn chương trình tính như sau: s:=0; for i := n downto 1 do s := sqrt (2 * i + s); Ta có thể viết chương trình như sau: program Vidu_5; var i,n : integer; s : real; begin write('Nhap mot so tu nhien n = '); readln(n); s:=0; for i := n downto 1 do s := sqrt (2 * i + s); writeln('Ket qua can tinh: s = ',s:10:5); readln; end. 10 3. Sử dụng cấu trúc While … do… * Cấu trúc: While <điều kiện> do ; * Trong đó: - While, do là các từ khoá; - <điều kiện> là một biểu thức logic; - là một câu lệnh. Có thể là câu lệnh đơn hoặc câu lệnh phức. * Cấu trúc hoạt động như sau: - Bước 1: Tính ; - Bước 2: Nếu kết quả là đúng (true) thì thực hiện và quay lại bước 1, ngược lại thì chuyển sang câu lệnh tiếp theo trong chương trình. 1 1 1 1  ... đến khi  104 Ví dụ 6: Tính tổng S  1    ...  3 5 2n  1 2n+1 Phân tích: Ta nhận thấy: Đặt: S n  1  1 1 1 1   ...   ... và rn = (n là một số tự nhiên bắt đầu bằng 0) 2n+1 3 5 2n  1 s 0 =0 � Ta có: � và Sn ≈ S khi rn <= 10-4. s n =s n-1 +rn � Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra. Toàn bộ chương trình: program vidu_6; var s,r : real; n : integer; begin writeln('Chuong trinh tinh tong chuoi S = 1+1/3+1/5+...'); s := 0; n := 0; r:= 1/(2*n+1); 11 While r>= 1E-4 do Begin s := s + r; n := n + 1; r:= 1/(2*n+1); end; writeln('Tong can tinh voi do chinh xac 1E-4 la S = ',s :10:6); readln; end. Ví dụ 7: Tính tổng S  1  1 1 1 1   ...  2  ... đến khi 2  106 n 4 9 n Phân tích: Phương pháp tính của chúng ta như sau: Đặt: s n  1  1 1 1 1  2  ...  2  ... và rn = 2 (n là số tự nhiên bắt đầu từ 1) 2 n 2 3 n s 0 =0 � và Sn ≈ S khi rn <= 10-6. s n =s n-1 +rn � Ta có: � Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra. Toàn bộ chương trình: program vidu_7; var s,r : real; n : integer; begin writeln(' Chuong trinh tinh tong chuoi S = 1+1/4+1/9+...'); s := 0; n := 1; r:= sqr(1/n); While r>= 1E-6 do Begin s := s + r; n := n + 1; r := sqr(1/n); end; writeln('Tong can tinh voi do chinh xac 1E-6 la S = ',s :10:6); 12 readln; end. Ví dụ 8: Dân số hiện nay ở một quốc gia khoảng 75 triệu người, tỉ lệ tăng tự nhiên là 1.7%. Hỏi sau bao nhiêu năm nữa thì dân số quốc gia đó đạt xấp xỉ 100 triệu? Phân tích: đặt S0 là dân số (tính theo đơn vị triệu) thời điểm hiện tại, Sn là dân số sau n năm tính từ thời điểm hiện tại. Ta có: s 0  75 � � s n  s n-1  s n-1*0.017 � tăng tự nhiên). (dân số năm sau bằng dân số năm trước cộng thêm lượng Như vậy n là số năm cần tìm nếu n là số tự nhiên bé nhất thoả mãn Sn100. Ta thấy rằng để tính trực tiếp n thì không dễ dàng nhưng chúng ta có thể sử dụng phương pháp lặp. Nghĩa là chúng ta tăng dần n (với n bắt đầu từ 0) và tính Sn theo công thức trên cho đến khi Sn >100 thì dừng. * Toàn văn chương trình: program Vidu_8; var n : integer; s : real; Begin n := 0; s := 75; while s<=100 do begin n := n + 1; s := s + s*0.017; end writeln('Dan so hien nay la 75 trieu. Ti le tang 1.7%.'); writeln('Sau ',n,' nam thi dan so dat 100 trieu nguoi.'); readln; 13 End. 4. Sử dụng cấu trúc lặp Repeat … Until… * Cấu trúc: Repeat ;... until <điều kiện>; * Trong đó: - Repeat, until là từ khoá; - ;... là một hay nhiều câu lệnh cách nhau bởi dấu ; - <điều kiện> là một biểu thức logic. * Cấu trúc hoạt động: - Bước 1: Thực hiện các câu lệnh giữa hai từ khoá Repeat … until - Bước 2: Tính giá trị nếu kết quả là đúng (true) thì chuyển sang câu lệnh tiếp theo, ngược lại thì quay lại bước 1. Ví dụ 9: Cho số thực a. Tìm số nguyên dương n nhỏ nhất thỏa mãn 1 1 1 1   ..   a 2 3 n Phân tích: Đặt: s n  1  1 1 1 1   ...  và rn  2 3 n n Ta có: s0  0 � đến khi S > a thì dừng. � s  s  r n-1 n �n Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra. * Toàn bộ chương trình: Program vidu_9; Uses crt; Var a, S : real; 14 n: longint; Begin Clrscr; Write(‘Nhap gia tri cua a:’); Readln(a); S:=0; n:=1; Repeat S:= S+ 1/n; n:= n+1; Until S>a; Writeln(‘ So nguyen n la:’, n ); Readln; End. Ví dụ 10: Turbo Pascal đã có hàm exp để tính ex, tuy nhiên ex có thể tính theo công thức khai triển chuỗi sau: x 2 x3 xn e =1+x+ + +...+ +... 2! 3! n! x Lập trình nhập số thực x rồi tính ex với độ chính xác exp =2 *10-6. Phân tích: x 2 x3 xn xn Đặt: sn =1+x+ + +...+ +... và rn  n! 2! 3! n! s0  1 � và sn S khi rn <= 2*10-6. s n  s n-1  rn � Ta có: � xn Với rn  ta cũng có thể tính theo công thức truy hồi: n! r0 =1 � � � x với n>=1 r =r . n n-1 � � n 15 Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra. * Ta có thể viết chương trình như sau: program vidu_10; var s, r : real; n ,x : integer; begin writeln('Chuong trinh tinh gan dung ham e mu ',x); s := 1; n := 1; r:= 1; Repeat r :=r * x/n; s := s + r; n := n + 1; until r<=2*(1E-6) writeln('Tong can tinh voi do chinh xac 1E-6 la S = ',s :10:6); readln; end. 5. Bài tập tham khảo Bài tập 1: 1: Tính tổng Tn = cos1 cos1+cos2 cos1+cos2+...cosn + +...+ với số n là số nguyên sin1 sin1+sin2 sin1+sin2+...sinn nhập từ bàn phím. Bài tập 2: Tính các giá trị biểu thức sau với số n tự nhiên nhập từ bàn phím: S  1.2  2.3.4  ...n(n  1 )...( 2n) Bài tập 3: Viết chương trình nhập số thực x, tính các giá trị sau với độ chính xác của số hạng cuối cùng là 10-6 : sin x  x  x3 x5 x 2 n 1   ...  ( 1) n  ... 3! 5! (2n  1)! cos x 1  x2 x4 x 2n   ...  ( 1) n  ... 2! 4! 2n! Bài tập 4: Một người gửi tiết kiệm không kì hạn với số tiền là A đồng với lãi suất 0.3% mỗi tháng. Hỏi sau bao nhiêu tháng, người đó rút hết tiền thì sẽ nhận được số tiền ít nhất 16 là B đồng? Biết rằng việc gửi tiết kiệm không kì hạn thì lãi suất không được cộng vào vốn. III. Kết quả và kiến nghị đề xuất : 1. Kết quả nghiên cứu : Trong năm học 2012-2013 tôi đã ứng dụng đề tài nghiên cứu của mình đối với một số lớp khối 11 ở trường THPT Hậu Lộc 4 và đã tổng hợp số liệu về kết quả đạt được của học sinh về kĩ năng sử dụng cấu trúc lặp khi giải các bài toán truy hồi như sau: STT Lớp Sĩ số Đạt yêu cầu Không đạt yêu cầu 1 11A1 45 85% 15% 2 11A5 46 92% 7% 3 11A8 48 95% 5% Như vậy, việc rèn luyện cho học sinh kĩ năng sử dụng cấu trúc lặp vào dạng bài toán thường gặp là bài toán truy hồi giúp học sinh có tiến bộ rõ rệt khi viết các chương trình có sử dụng cấu trúc lặp. Đồng thời nâng cao việc yêu thích học tin học đối với một bộ phận học sinh, trong đó có một số em có khả năng tìm hiểu sâu hơn về các dạng bài toán lập trình. 2. Kiến nghị, đề xuất : Sau khi thực hiện đề tài này tôi xin mạnh dạn đưa ra một số đề xuất như sau : - Để học sinh thực sự hiểu rõ các loại cấu trúc lặp trong lập trình mà cụ thể đối với học sinh lớp 11 là ngôn ngữ lập trình Pascal thì cần tăng cường hơn nữa lượng thời gian trong phân phối chương trình để học sinh rèn luyện các dạng bài tập về cấu trúc lặp, giúp học sinh nắm chắc cú pháp, cách sử dụng cấu trúc này. - Giáo viên cần đưa ra các bài tập để phù hợp với từng đối tượng học sinh, với mỗi loại cấu trúc lặp nên đưa ra bài có tính đặc trưng để học sinh ghi nhớ được cách sử dụng và cú pháp của cấu trúc lặp. - Với đối tượng học sinh khá giỏi thì có thể khai thác sâu hơn một số bài toán khó của dạng bài toán truy hồi mà có thể áp dụng cấu trúc lặp để giải (chẳng hạn bài toán Tháp Hà Nội...). C. KẾT LUẬN: 17 Đối với đa số học sinh, việc học lập trình là tương đối khó đối với các em, đòi hỏi các em phải có kiến thức nhất định về mặt toán học, đồng thời phải biết vận dụng phù hợp với từng cấu trúc cụ thể của ngôn ngữ lập trình mới có thể lập trình giải quyết bài toán đó. Tuy nhiên, nếu như được rèn luyện kĩ năng, áp dụng từng cấu trúc cụ thể vào từng dạng bài toán, học sinh sẽ ghi nhớ, sử dụng thành thạo cấu trúc, từ đó các em thấy hứng thú với việc học lập trình để giải các bài toán. Với đối tượng học sinh khá giỏi thì việc khai thác cách để giải các bài toán truy hồi bằng cấu trúc lặp sẽ giúp học sinh hứng thú học lập trình và tìm hiểu sâu hơn các dạng bài toán khác. Giáo viên nên khuyến khích học sinh để các em học tập và nghiên cứu. Trên đây là một số kinh nghiệm của tôi qua nhiều năm liền dạy ở khối lớp 11, trường THPT Hậu Lộc 4, cũng như tham khảo qua nhiều nguồn thông tin, tư liệu khác nhau, rất mong được sự đóng góp của các đồng nghiệp nhằm giúp đề tài của tôi được hoàn thiện thêm. 18