SKKN Mốt số phương pháp thu hút học sinh học lập trình trong trường THPT

SKKN Mốt số phương pháp thu hút học sinh học lập trình trong trường THPT

Trong công tác giảng dạy Tin học ở trường phổ thông việc tiếp cận với lập trình đối với học sinh là một điều hoàn toàn mới. Khác với các bộ môn khác học sinh được tiếp cận với môn học từ ngay ở cấp tiểu học hay cấp THCS. Với tâm lý lứa tuổi đang trong giai đoạn thịch tìm hiểu, khám phá, việc các em được tiếp cận công nghệ thông tin là một điều hoàn toàn mới mẽ và đầy lý thú đối với các em. Tuy nhiên với thời lượng và phân phối chương trình cho môn tin học lập trình ở khối 11 chỉ với 1.5 tiết/tuần thì quả là ít ỏi để các em có thể tiếp cận và tìm hiểu sâu về lập trình được. Trong đó một bộ phận của học sinh có niềm say mê công tác lập trình để giải quyết các bài toán thực tiễn thì các em bị rào cản là chương trình tin học được học trên lớp thì chỉ ở mức biết và hiểu ở mức độ thấp trong khi sự phát triển của xã hội ngày nay đang cần rất nhiều nguồn nhân lực công nghệ thông tin.

doc 21 trang thuychi01 5370
Bạn đang xem 20 trang mẫu của tài liệu "SKKN Mốt số phương pháp thu hút học sinh học lập trình trong trường THPT", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT YÊN ĐỊNH 2
SÁNG KIẾN KINH NGHIỆM
TÊN ĐỀ TÀI
MỐT SỐ PHƯƠNG PHÁP THU HÚT HỌC SINH 
HỌC LẬP TRÌNH TRONG TRƯỜNG THPT
Người thực hiện: Lương Trung Dũng
Chức vụ: TTCM
SKKN thuộc lĩnh vực : Tin học
THANH HOÁ NĂM 2016
MỤC LỤC
I. MỞ ĐẦU
1. Lí do chọn đề tài.
Trong công tác giảng dạy Tin học ở trường phổ thông việc tiếp cận với lập trình đối với học sinh là một điều hoàn toàn mới. Khác với các bộ môn khác học sinh được tiếp cận với môn học từ ngay ở cấp tiểu học hay cấp THCS. Với tâm lý lứa tuổi đang trong giai đoạn thịch tìm hiểu, khám phá, việc các em được tiếp cận công nghệ thông tin là một điều hoàn toàn mới mẽ và đầy lý thú đối với các em. Tuy nhiên với thời lượng và phân phối chương trình cho môn tin học lập trình ở khối 11 chỉ với 1.5 tiết/tuần thì quả là ít ỏi để các em có thể tiếp cận và tìm hiểu sâu về lập trình được. Trong đó một bộ phận của học sinh có niềm say mê công tác lập trình để giải quyết các bài toán thực tiễn thì các em bị rào cản là chương trình tin học được học trên lớp thì chỉ ở mức biết và hiểu ở mức độ thấp trong khi sự phát triển của xã hội ngày nay đang cần rất nhiều nguồn nhân lực công nghệ thông tin. 
2. Mục đích nghiên cứu.
Giúp cho các em học sinh đam mê bộ môn lập trình có thêm kiến thức trong việc giải quyết các bài toán một các hữu ích hơn, đồng thời giúp các em có niềm đam mê và yêu thích bộ môn lập trình trong lĩnh vực công nghệ thông tin.
Giúp các em học sinh có thêm kiến thức sâu hơn về lập trình, từ đó có thể bồi dưỡng và phát hiện những nhân tố có tố chất và khả năng nhằm tạo nguồn bồi dưỡng học sinh giỏi.
3. Đối tượng nghiên cứu.
Với mục tiêu là giúp học sinh có thể lĩnh hội thêm một số phương pháp chuyên sâu trong lập trình để có thể tạo hứng thú và sự yêu thích bộ môn lập trình để giải quyết các bài toán tin học lập trình nâng cao qua ba phương pháp mở rộng đó là: Phương pháp đệ quy, phương pháp sinh và phương pháp quy hoạch động. Sau khi truyền thụ ba phương pháp này các em học sinh khá giỏi có khả năng phát triển sâu hơn về kỷ thuật lập trình và có thể trang bị hành trang cho cơ sở lập trình cao hơn và phát triển trên các ngôn ngữ lập trình khác nhau.
4. Phương pháp nghiên cứu.
Trong đề tài này tôi dựa trên 2 phương pháp chính là phương pháp nghiêm cứu xây dựng cơ sở lý thuyết và phương pháp xử lý số liệu. Với hai phương pháp này tôi kết hợp với phương pháp thuyết trình trong nghiệp vụ sự sư phạm nhằm thu hút học sinh và tạo niềm đam mê cho môn học
II. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
1. Cơ sở lí luận của sáng kiến kinh nghiệm.
Việc mở rộng phát triển tư duy trong thuật toán đối với học sinh để các em có thể nhìn ra được một cách giải trước một bài toán lớn trong tin học đem lại hiệu quả cho công việc và việc tiếp tục học tập lên cao là hết sức cần thiết. Việc giải quyết bài toán bằng phương pháp thông thường trong tư duy dùng phương thức liệt kê cá trường hợp và khả năng xảy ra của bài toán khi số lượng cấu hình của bài toán nhiều lên thì khoảng thời gian chi phí cho việc liệt kê là quá lớn đối với công sức của con người. Đặc biệt là với các bài toán trong tổ hợp, bài toán đếm thì con người không thể đủ thời gian để liệt kê ra được. việc giải quyết bài toán bằng các phương pháp thông thường trong sách giáo khoa tin học 11 thì các em không thể giải quyết được. Do vậy việc mở rộng các phương pháp để giúp các em có thể biết thêm cách thức tư duy và giải quyết các bài toán là hết sức cần thiết.
Trong thời đại bùng nổ của internet ngày nay các em dễ dàng có thể tìm thấy thấy rất nhiều tài liệu để học tập trong việc lập trình, nhưng việc học tập của em sẽ không có hiệu quả vì các em không biết mình sẽ bắt đầu từ đâu? Khi tham gia các diễn đàn lập trình đối với tin học phổ thông thì nghèo nàn chủ yếu là dừng lại ở việc giải quyết các bài toán cơ bản và đơn giản, chưa chuyên sâu. Với các trường THPT trong tỉnh hiện nay chỉ các trường ở thành phố và lân cận thì học sinh được tiếp cận công nghệ từ đó các em có thể tìm hiểu trao đổi thông tin và tìm tòi học hỏi để tìm ra các cách giải quyết bài toán một cách hiệu quả, còn đối với các trường phổ thông còn lại thì việc kích thích trí tìm tòi sáng tạo của em đối với bộ môn tin học nói chung và bộ môn lập trình nói riêng thì hầu như đều chưa được đề cập đến. Việc tham gia các kỳ thi học sinh giỏi cấp tỉnh thì các bài toán thường có cấu hình lớn và học sinh phải vận dụng được nhiều phương pháp cao kết hợp với tư duy toán học logic và có khả năng về chiều sâu trong lập trình thì mới có thể giải quyết được.
2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.
Trước khi áp dụng sáng kiến kinh nghiệm vào trong giảng dạy thì tôi thấy rằng. Việc học lập trình tin học ở trường phổ thông nói chung các em chỉ học chủ yếu là đối phó. Việc nắm bắt được giải quyết các bài toán và lập trình nhìn chung có thể nói là các em biết lập trình chỉ đếm trên đầu ngón tay, ngoại trừ các em ở khối chuyên trường chuyên. Nếu cứ vẫn giữ phương pháp như đơn điệu truyền thụ nội dung sách giáo khoa cho các em, hết chương trình theo quy định của bộ thì liệu trong số các em có được bao nhiêu học sinh sẽ đi theo lĩnh vực công nghệ thông tin, trong khi công nghệ thông tin bây giờ vẫn đang là một ngành nghề “hot”. Các nhà tỉ phú trong lĩnh vực công nghệ thông tin vẫn đang chiếm lĩnh trong các lĩnh vực kinh tế trên thế giới, vậy những chủ nhân tương lai của đất nước không yêu thích và bắt kịp thì sau này có thể thúc đẩy sự phát triển được nên kinh tế của đất nước hay không. Và hầu hết câu trả lời ở đây các em đều không nhận thức được điều đó. Các em chỉ thích chạy bám theo công nghệ mà không biết tạo ra công nghệ, hay nói cách khác chỉ có nhu cầu sử dụng mà không hề có vốn kiến thức để tạo ra nó.
Quá trình học tập và tìm hiểu lập trình chỉ bám theo nội dung chương trình sách giáo khoa đối với một bộ phận học sinh khá giỏi sau khi đã có kiến thức cơ bản về lập trình thì các em cũng cảm thấy nhàm chán đơn điệu và chỉ dừng lại ở việc học tập đối phó, không mở rộng tư duy, điều này dẫn tới việc các em có tiếp tục đi sâu vào lập trình nữa hay không thì có lẽ các em sẽ không tiếp tục nữa, điều này đã minh chứng bởi rất nhiều trường phổ thông có thầy cô giảng dạy tốt về chuyên môn nhưng chỉ áp dụng truyền thụ kiến thức sách giáo khoa cho nên vẫn không thể có nguồn học sinh đam mê lập trình, đến khi thi chọn học sinh giỏi thì không có nhân tố và dẫn đến bế tắc.
Vấn đề lập trình trước khi áp dụng các em học sinh hầu như chỉ đơn thuần dựa theo các bài tập thực hành sách giáo khoa, một số có tìm tòi ở sách bài tập nhưng còn rất hạn chế vì bài tập không mang tính hiệu quả, số tiết để giải bài tập cho các em theo sách bài tập thì không có, do vậy: Các em muốn biết để kiểm chứng thuật toán thì làm thế nào để có thể tạo ra dữ liệu? Có phương pháp nào để lấy ra kết quả bài toán bằng tư duy theo kiểu toán học hay không? Có cách nào để giải những bài toán với công thức tổng quát dãy số như truy hồi hay không? Có phương pháp nào tối ưu để giải bài toán một lớn cho ra kết quả thực hiện một cách nhanh chóng không? Đó là những câu hỏi mà các em học sinh đã có vốn kiến thức căn bản có thể đặt ra. Tuy nhiên còn rất nhiều câu hỏi mà các em có thể đặt ra nữa nhưng ở đây vẫn nổi lên là 3 vấn đề chính
* Thứ nhất: Tạo nguồn dữ liệu cho bài toán
Việc sau khi lập trình các em chưa biết cách tạo ra dữ liệu để kiểm tra và kiểm nghiệm bài toán. Đôi khi việc kiểm nghiệm bài toán muốn tạo ra dữ liệu đầu vào thì các em mất một khoảng thời gian lớn. Việc sinh dữ liệu ngẫu nhiên nhằm tạo ra bộ dữ liệu mẫu một cách nhanh chóng và thuận tiện. Có thể vận dụng phương pháp sinh một cách linh hoạt để tạo ra được các bộ dữ liệu khách nhau phù hợp với yêu cầu bài toán.
Hầu hết các bài toán đều đỏi hỏi việc dữ liệu vào ra. Người lập trình dùng ba phương pháp cơ bản sau đây:
1. Nạp dữ liệu trực tiếp từ bàn phím. Phương pháp này được dùng khi dữ liệu không nhiều.
2. Sinh dữ liệu nhờ hàm Random. Phương pháp này nhanh chóng và tiện lợi. Nếu khéo léo tổ chức có thể sinh ngẫu nhiên được các dữ liệu đáp ứng được một số điều kiện định trước.
3. Đọc dữ liệu từ tệp văn bản. Phương pháp này khá tiện lợi khi phải chuẩn bị trước những dữ liệu phức tạp.
Kết quả thực hiện chương trình thường được thông báo trực tiếp trên màn hình hoặc ghi vào một tệp văn bản.
Một số bài toán sinh dữ liệu tiêu biểu.
Bài 1: Sinh ngẫu nhiên theo khoảng
Sinh ngẫu nhiên n phần tử nằm trong khoảng -M..M; M>0 cho mảng nguyên a
Bài 2: Sinh ngẫu nhiên tăng
Sinh ngẫu nhiên n phần tử được sắp xếp không giảm cho mảng nguyên a.
Bài 3: Sinh hoán vị ngẫu nhiên
Sinh ngẫu nhiên cho mảng nguyên a một hoán vị của 1..n
Bài 4: Sinh ngẫu nhiên tỉ lệ.
Sinh ngẫu nhiên cho mảng nguyên a có n phần tử tạo thành hai đoạn liên tiếp có tổng các phần tử trong một đoạn gấp k lần tổng các phần tử của đoạn kia.
Bài 5: Sinh ngẫu nhiên đầu: Sinh ngẫu nhiên n phần tử cho mảng nguyên a thỏa mãn điều kiện n phần tử tạo thành k đoạn liên tiếp có tổng các phần tử trong mỗi đoạn bằng giá trị t cho trước.
Bài 6: Sinh ngẫu nhiên tệp tăng.
Sinh ngẫu nhiên n số tự nhiên được sắp tăng ghi vào tệp văn bản có tên cho trước.
Bài 7: Sinh ngẫu nhiên cấp số cộng.
Sinh ngẫu nhiên cấp số cộng có n số hạng và ghi vào tệp văn bản có tên cho trước.
Bài 8: Sinh số độ cao h
Độ cao của một số tự nhiên là tổng các chữ số của số đó. Sinh toàn bộ các số tự nhiên có tối đa ba chữ số và có độ cao h cho trước. Ghi kết quả vào một tệp văn bản có tên cho trước.
Bài 9: Tệp hoán vị
Với mỗi số n cho trước trong khoảng 1..9, ghi vào một tệp văn bản có tên cho trước toàn bộ các hoán vị của 1..n. Hoán vị được sắp xếp tăng theo thứ tự từ điển, thí dụ 21345<21354
Và nhiều bài toán khác có thể vận dụng phương pháp sinh dữ liệu một cách linh hoạt.
Đối với phương pháp sinh ta thay vì phải tìm duyệt các đối tượng trong tất cả các phương án thì ta hãy sinh ra chúng. Phương pháp này làm tăng lên tốc độ thực hiện cho chương trình, nhiều bài toán ta có thể tìm trực tiếp ra nghiệm của nó.
Đối với những bài toán dạng này học sinh phải biết vận dụng tư duy toán học một cách linh hoạt trong xử lý thuật toán. Ta có thể xét một số bài toán tiêu biểu như sau:
Bài 10: Cấp số cộng
Tìm các số tự nhiên lẻ có ba chữ số. Ba chữ số này theo trật tự từ trái qua phải tạo thành cấp số cộng.
Bài 11. Cấp số nhân.
Tìm các số tự nhiên có ba chữ số. Ba chữ số này theo trật tự từ trái qua phải tạo thành một cấp số nhân.
Bài 12: mảng ngẫu nhiên
Sinh ngẫu nhiên n số nguyên không âm cho mảng a.
* Thứ hai: Liết kê các trường hợp ra để tìm phương án
- Phương pháp đệ quy và quay lui:
Về phương pháp đệ quy và quay lui thì đã có rất nhiều tài liệu lập trình đề cập tới, nhưng trong giới hạn chương trình tin học phổ thông thì đệ quy và quay lui chương được đề cập tới mà chỉ dừng lại ở chương trình con hàm và thủ tục. Do vậy học sinh chỉ hiểu chương trình con chỉ dơn thuần là tổ chức giải quyết một công việc nhỏ nào đó qua một số thao tác nhất định và lấy ra một vài kết quả đơn giản. Đối với việc diễn tả thuật toán trong toán học là cơ sở thì công thức truy hồi thì các em đã được bắt gặp trong các dãy số, do vậy để thể hiện các công thức truy hồi như vậy thì trong lập trình có thể thể hiện được các công thức truy hội đó hay không. Mộ số bài toán dạng này.
Bài 13: Lũy thừa
Tính lũy thừa an với a là số thực, n là số nguyên dương 
Bài 14: Tìm n! với n là số tự nhiên
Bài 15: Dãy Fibonaci:
Tìm phần tử thứ n của dãy Fibonaci biết f(n)=f(n-1)+f(n-2) với f(0)=0; f(1) = 1
- Phương pháp quay lui:
Quay lui là một phương pháp mở rộng trong đệ quy. Đệ quy quay lui có thể vét cạn các trường hợp từ đó có thể tìm ra nghiệm của bài toán. Đối với bài toán cần tìm ra nghiệm thì ta có thể sử dụng đệ quy để tìm ra nghiệm một cách đơn giản. Tuy nhiên khi dạy vấn đề đệ quy chúng ta cần chỉ ra cho học sinh thấy được nhược điểm của phương pháp này là sử dụng phương pháp vét cạn nên tốc độ chậm, bị hạn chế bởi ngăn xếp và một công việc có thể thực hiện lặp đi lặp lại nhiều lần nên có thể tràn bộ nhớ stack.
Đối với phương pháp này ta hoàn toàn có thể tìm ra nghiệm cho bài toán ở một số nghiệm nhỏ. Điều này đã có nhiều cuộc thi học sinh giỏi nếu gặp bài toán khó mà học sinh chưa tìm ra được tất cả các nghiệm của bài toán bằng những phương pháp khác các em hoàn toàn có thể sử dụng phương pháp này để tìm ra một số nghiệm nhỏ với tốc độ trong giới hạn cho phép.
Một số bài toán ta có thể kể tới:
Bài 16: dãy nhị phân
Liệt kê các dãy nhị phân có độ dài n cho trước.
Bài 17: Biểu thức Zero
Điền các dấu +, - vào giữa các số tự nhiên từ 1..n sao cho biểu thức có tổng bằng không
Bài 18: Cân vật
Có n quả cân có các khối lượng c1, c2...cn và vật có khối lượng m. Hãy tìm các cách để có thể cân được vật nặng m. biết vật và cân có thể đặt bên cân trái hoặc cân phải.
* Thứ ba: bài toán giải quyết nhanh chánh vét cạn hay không?
Phương pháp quy hoạch động
Các bài toán dần tìm đến nghiệm tối ưu và cần thời gian thực hiện ra kết quả mang tính khả thi cao. Các bài toán quy hoạch động chiếm một vị trí khá quan trọng trong tổ chức hoạt động sản xuất. Chính vì lẽ đó mà việc gây hứng thú cho học sinh trong việc tìm tòi để phát triển khả năng tư duy và tạo ra hứng thú học tập cho học sinh khá giỏi là rất cần thiết. Khi học sinh đã có kiến thức căn bản thì những bài toán thông thường không có gì là khó khăn gây cản trỏ các em dẫn tói học sinh sẽ cảm thấy nhàm chán đối với việc giải quyết các bài toán, từ đó các em không còn hứng thú đối với việc lập trình nữa. 
Thông thường những em dùng phương pháp quay lui vét cạn cho các bài toán quy hoạch đổng thì chỉ có thể vét được các tập dữ liệu nhỏ, kích thước chừng vài chục byte. Nếu tìm được đúng hệ thức thể hiện bản chất quy hoạch động cảu bài toán và khéo léo tổ chức dữ liệu thì chúng ta xử lý đực những tập dữ liệu khá lớn.
Quy hoạch động là tập các bài toán mà quyết định ở bước thứ I phụ thuộc vào quyết định ở các bước đã xử lý trước đó.
3. Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết vấn đề.
Phương pháp giải quyết vấn đề ở đây tôi sẽ đưa ra một cách giải quyết một số bài toán cơ bản, từ đó chúng ta có thể vận dụng tư duy một cách linh hoạt để có thể giải quyết những bài toán khác.
* Thứ nhất: Đối với phương pháp sinh:
Xét bài toán 1: Sinh ngẫu nhiên theo khoảng
Đặc tả: Ta viết thủ tục tổng quát Gen(n,d,c) - sinh ngẫu nhiên n số nguyễn trong khoảng từ d đến c (d<c)
Để ý rằng random(c-d+1) biến thiên trong khoảng từ 0 đến c-d, do đó d + random(c-d+1) sẽ biến thiên trong khoảng từ d đến d+c-d=c.
(*-----------------------------------------------------------------------------
Sinh ngẫu nhiên n số nguyên trong khoảng d đến c
------------------------------------------------------------------------------*)
Procedure Gen(n,d,c:integer);
Var i,len:integer;
Begin
Randomize;
Len=c-d+1;
For i:=1 to n do a[i]:=d+random(len);
End;
Từ đó ta có chương trình
Program Sinh_khoang;
Uses crt;
Var a:array[1..1000] of integer;
(*--------------------------------------------*)
Procedure Gen(n,d,c:integer);
Var I,len:integer;
Begin
Randomize;
Len=c-d+1;
For i:=1 to n do a[i]:=d+random(len);
End;
(*--------------------------------------------*)
Procedure Xem(n:integer);
Var i:integer;
Begin
Writeln;
For i:=1 to n do write(a[i]:4);
Writeln;
End;
Procedure test;
Var n:integer;
Begin
N:=20;
Gen(n.-8,8);
Xem(n);
Readln;
End;
Begin
Test;
End.
Như vậy các em phải linh hoạt ở điểm d+random(c-d+1) để lấy được khoảng biến thiên từ d đến c. Từ đó các em có thể linh hoạt để vận dụng giải các bài toán tiếp theo.
- Xét bài toán 10
Tìm các số tự nhiên lẻ có ba chữ số. Ba chữ số này theo trật tự từ trái qua phải tạo thành cấp số cộng.
Đặc tả:
1. x là số tự nhiên có ba chữ số: x=100a+10b+c
2. x là số lẽ nên chữ số hàng đơn vị c phải là số lẻ: c=1,3,5,7,9.
3, Chữ số hàng trăm của x phải khác 0: a = 1..9
4. Nếu a,b,c lập thành cấp số cộng thì số đứng giữa b là trung bình cộng của hai số đầu và cuối: b=(a+c)/2
Từ (4) suy ra (a+c) là số chẵn. Do c là số lẻ nên a cũng là số lẻ.
Nếu biết được a và c ta tính được x	=100a+10((a+c) div 2) +c
	=100a+5(a+c)+c = 105a+6c
Vì chỉ có 5 chữ số lẻ là 1, 3, 5, 7, 9 nên tổ hợp của a và c sẽ cho ta 25 số.
Tổ chức dữ liệu
Ta tạo sẵn mảng nguyên 5 phần tử chusole[1..5] và gán trước các giá trị 1, 3, 5, 7, 9 cho mảng này. 
Const chusole[1..5]:array[1..5] of integer =1,3,5,7,9);
Sau đó, mỗi khi cần ta chỉ cần duyệt mảng chỉ số lẽ từ 1 đến 5 là thu được toàn bộ các chữ số lẽ theo trật tự đã khai báo trước.
Chương trình.
Program capcong;
Uses crt;
Const chusole[1..5]:array[1..5] of integer =1,3,5,7,9);
Var s:array[1..25] of integer;
N: integer;
(*-------------------------------------------------------------------------
Sinh các số dạng 105a+6c)
--------------------------------------------------------------------------*)
Function tim:tinteger;
Var a,c,d:integer;
Begin
d:=0;
For a:=1 to 5 do
For c:=1 to 5 do 
Begin
Inc(d)
S[d]:=105*chusole[a]+6*chusole[c];
End;
Tim:=d;
End;
Procedure xem(n:integer);
Var i:integer;
Begin
Writeln;
For i:1 to n do write(s[i]:4);
Writeln;
End;
Procedure test;
Var n:integer;
Begin
Clrscr;
N:=tim;
Xem(n);
Writeln;
Writeln(‘tong cong co ‘,n,’ so’);
Readln;
End.
Chú ý
Dựa vào nhận xét dãy ba số a,b,c tạo thành cấp số cộng khi và chỉ khi b là trung bình cộng của a và c tức là 2b=a+c ta có thể giải bài toán trên bằng phương pháp vét cạn dùng ba vòng for như sau
For a:=1 to 9 do
	For b:=0 to 9 do
	For c:=1 to 9 do
	If odd(c) and (2*b=a+c) then ghi nhận số 100a+10b+c
Phương pháp vét cạn này đòi hỏi khoảng 10*10*10= 1000 lần duyệt trong khi chỉ có 25 số, tức là 1/40 các số thỏa mãn điều kiện đầu bài. Phương pháp sinh mô tả trpng chương trình là phương pháp sinh ra đúng 25 số cần tìm.
Thứ hai: Phương pháp đệ quy:
Trong chương trình tin học phổ thông học sinh chỉ được tìm hiểu về hàm và thủ tục ở mức độ đơn giản, có thể biết về chương trình con. Đề giải quyết bài toán thông thường thì ta xây dựng hàm và thủ tục. Thủ tục là nhằm giải quyết một số các thao tác nhất định nào đó mà không trả về kết quả thông qua tên, còn hàm là chương trình con thực hiện một số thao tác nhất định nào đó những kết quả cuối cùng được trả về thông qua tên, kết quả đó là kế quả đơn, không thể là cấu trúc như mảng.
Vấn đề đặt ra là chương trình con có thể hiện được công thức truy hồi hay không? Việc vét cạn thông qua chương trình con còn được thể hiện như thế nào?
Ta giải quyết vấn đề này như sau:
- Vấn đề công thức truy hồi:
Ta xét bài toán 14 tính n! bằng đệ quy như sau;
Function giaithua(n:word):longint;
Begin
If n=0 then giaithua:=1 
Else giaithua:= n*giaithua(n-1);
End;
Từ bài toán này ta phân tích cách giải quyết theo đệ quy cần xét đến 2 yếu tố
Thứ nhất là trường hợp suy biến của đệ quy. Ở đây ta xét trường hợp suy biến là khi n = 0 thì đó chính là trường hợp suy biến mà ta gọi là điểm Neo. Mọi trường hợp đệ quy ta cần xét đến trường hợp suy biến để tìm điểm Neo là gốc để tính đệ quy.
Thứ hai là công thức truy hồi. ở đây ta dựa vào công thức 
	N! = N*(N-1)!
Từ đó ta có thể xây dựng hàm đệ quy.
Tương tự như vậy học sinh có thể xây dựng hàm đệ quy cho dãy fibonaci như sau
Function fibo(n:word):longint;
Begin
If n<2 then fibo:=1
Else fibo:=fibo(n-2)+fibo(n-1);
End;
Đã có rất nhiều tài liệu phân tích và cho thấy việc sử dụng đệ quy này ta phải thực hiện sử dụng ngăn xếp stack để lưu trữ, do đó nó chỉ thực hiện được ở một giới hạn dữ liệu nhỏ. Và cùng một công thức đó ta có thể phải thực hiện tính toán lại nhiều lần làm tốn không gian lưu trữ.
Ta có thể xét thêm cho học sinh bởi lẽ học sinh đặt ra câu hỏi: có hàm đệ quy vậy có thủ đệ quy hay không.
Câu trả lời là chúng ta có thể sử dụng thủ tục đệ quy để giải quyết bài toán một cách linh hoạt và ta có thể vét cạn các trường hợp để tìm ra nghiệm của bài toán.
Trước hết giáo viên phải nêu ra được vấn đề của giải thuật đệ quy quay lui. Ta có hai giải thuật quay lui cơ bản là tìm 1 nghiệm 
Cơ sở đệ quy quay lui:
Giả sử phải tìm trong một tập dữ liệu D 

Tài liệu đính kèm:

  • docskkn_mot_so_phuong_phap_thu_hut_hoc_sinh_hoc_lap_trinh_trong.doc