Sáng kiến kinh nghiệm THPT: Định hướng giảng dạy giải thuật và lập trình về quay lui và quy hoạch động cơ bản

Chia sẻ: _ _ | Ngày: | Loại File: DOCX | Số trang:58

Thêm vào BST

Báo xấu

5
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Sáng kiến kinh nghiệm "Định hướng giảng dạy giải thuật và lập trình về quay lui và quy hoạch động cơ bản" được thực hiện với mục tiêu giúp cho học sinh tiếp cận dễ dàng hiểu về quay lui và quy hoạch động cơ bản thì sáng kiến còn xây dựng hệ thống các dạng bài tập thường gặp để ôn luyện cho học sinh dự thi các kỳ thi học sinh giỏi môn tin học.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Định hướng giảng dạy giải thuật và lập trình về quay lui và quy hoạch động cơ bản

SỞ GIÁO DỤC VÀ ĐÀO TẠO NINH BÌNH ………… TÊN SÁNG KIẾN: ĐỊNH HƯỚNG GIẢNG DẠY GIẢI THUẬT VÀ LẬP TRÌNH VỀ QUAY LUI VÀ QUY HOẠCH ĐỘNG CƠ BẢN Lĩnh vực : Tin học Nhóm thực hiện : Nguyễn Ngọc Thành Nguyễn Trung Quyết Nguyễn Mạnh Cường Vũ Thị Phương Đơn vị công tác: Trường THPT Gia Viễn B Gia Viễn, tháng 5 năm 2022
MỤC LỤC
3 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN Kính gửi: Hội đồng sáng kiến cấp ngành Chúng tôi ghi tên dưới đây: Tỷ lệ (%) Trình đóng Ngày Nơi độ góp tháng STT Họ và tên công Chức vụ chuyê vào năm tác n việc sinh môn tạo ra sáng kiến THPT Tổ phó Nguyễn Ngọc 10/6/198 Đại 1 Gia Viễn chuyên 25% Thành 2 học B môn THPT Nguyễn Mạnh 17/7/198 2 Gia Viễn Giáo viên Thạc sĩ 25% Cường 4 B THPT Nguyễn Trung 22/8/198 Đại 3 Gia Viễn Giáo viên 25% Quyết 7 học B THPT 12/2/198 Đại 4 Vũ Thị Phương Gia Viễn Giáo viên 25% 9 học B I. TÊN SÁNG KIẾN, LĨNH VỰC ÁP DỤNG - Tên sáng kiến: “Định hướng giảng dạy giải thuật và lập trình về quay lui và quy hoạch động cơ bản” - Lĩnh vực áp dụng: Giảng dạy HSG bộ môn tin học THPT II. NỘI DUNG 1. Giải pháp cũ thường làm Khi dạy HSG giáo viên thường sẽ phát triển kiến thức, kỹ năng của học sinh thông qua các bước như: - Xác định mức độ kiến thức của HS - Củng cố, rèn luyện lại kiến thức, kỹ năng cơ bản xác định bài toán cho học sinh - Giải các bài toán cơ bản làm nền tảng, xây dựng kỹ năng làm bài cho
4 học sinh Trong quá trình giảng dạy có những bước giáo viên mất rất ít thời gian, nhưng cũng có những bước mà thời gian là rất nhiều. Đặc biệt là bước tiến hành dạy nâng cao để tăng tính tư duy, vận dụng các kiến thức cơ bản để làm các bài toán khó thì đây là bước vô cùng quan trọng và chiếm nhiều thời gian nhất. Có thể khẳng đinh đây chính là bước để xác định việc học sinh có thể tiếp thu và đạt được kết quả cao trong kì thi chọn HSG hay không? Tuy nhiên trong quá trình giảng dạy nâng cao đại đa số giáo viên chú trọng đến việc giảng dạy kiến thức nền tảng giải thuật rất ít, giáo viên chỉ dạy lướt qua rồi cho học sinh làm bài để rèn luyện kĩ năng và vận dụng những kiến thức có bản để giải quyết bài toán, mà thường ít chú ý rằng những bài toán đó có cách giải dễ dàng hơn rất nhiều bằng các thuật toán cơ bản thay vì chỉ tư duy đơn giản để làm bài. Vì vậy sau nhiều năm dạy HSG bằng thực nghiệm tại trường thpt gia viễn b chúng tôi nhận thây các bước dạy HSG có một số điểm chưa đạt được yêu cầu của BHG, tổ, nhóm chuyên môn đề ra như: Thứ nhất: Việc dạy HSG thường theo kinh nghiệm nhiều năm dạy HSG của những giáo viên lâu năm, hoặc là vừa dạy vừa tìm hiểu đối với những giáo viên mới dạy hoặc còn ít kinh nghiệm. Thứ hai: Việc dạy HSG như thế làm giáo viên “lười” tìm hiểu kiến thức, kỹ năng rèn luyện bản thân, trau dồi kiến thức cho minh. Thứ ba: Học sinh không hiểu sâu rộng về lập trình, gặp bài toán là giải ngay mà ít chịu tư duy suy nghĩ. Tìm phương án tối ưu để giải quyết bài toán. Thứ tư: Kết quả dạy HSG sẽ không đạt được kết quả cao. Không tạo được động lực để hs lớp sau yêu thích, say mệ môn tin cũng như yêu thích và say mê lập trình. Từ đó tạo cảm giác “sợ hãi” với những học sinh khác. Thứ năm: Không có một phương án thống nhất, một hệ thống kiến thức, bài tập xuyên suốt để giáo viên dạy HSG. 2. Giải pháp mới cải tiến Sau nhiều năm cùng nhau giảng dạy HSG chúng tôi nhận thấy rằng để giải quyết được vấn đề trên thì cần phải có được hệ thống kiến thức và bài tập cơ bản về dạy học nâng cao cho HSG. Trong hệ thống kiến thức và bài tập cơ bản đó thì có 2 phần vô cùng quan trọng mà tất cả các đề thi HSG môn tin của huyện, của tỉnh về thi HSG, thi tin học trẻ đề có đó là 2 giải thuật và lập trình về quay lui và quy hoạch động Do đó chúng tôi làm sáng kiến kinh nghiệm có tên: “Giải thuật lập trình về quay lui và quy hoạch động cơ bản”. III. HIỆU QUẢ KINH TẾ VÀ XÃ HỘI 1. Hiệu quả kinh tế Thứ nhất, xét về mặt thời gian: Để biên soạn một chủ đề hoặc một
5 chuyên đề dạy học thì giáo viên sẽ phải mất rất nhiều thời gian tìm kiếm, biên tập lại từ các tài liệu trên internet và các sách tham khảo. Học sinh có nhu cầu tìm kiếm bài tập để luyện thì cũng phải tìm kiếm trong nhiều tài liệu rồi hệ thống lại. Điều này cũng sẽ mất rất nhiều thời gian. Trong khi đó, giáo viên và học sinh có thể sử dụng ngay tài liệu này để học cũng như sử dụng trong việc ôn thi học sinh giỏi. Nếu cần thì giáo viên chỉ cần bổ sung hàng năm để có được tài liệu phong phú về bài tập cho riêng mình. Thứ hai, xét về tài chính: Để viết nên tài liệu này, không kể tài liệu sách giáo khoa (học sinh và giáo viên nào cũng có), giáo viên sẽ mất rất nhiều giờ truy cập internet, và nhiều giờ để nghĩ ra các bài toán. Trong khi với tài liệu này, giáo viên chỉ cần phô tô hoặc in tài liệu này với giá không quá 10.000 đồng. Nếu tính về hiệu quả kinh tế sẽ tiết kiệm rất nhiều, vì với tài liệu này ta sẽ còn duy trì trong nhiều năm tiếp theo nữa. 2. Hiệu quả xã hội Sáng kiến không chỉ giúp giải quyết cho vấn đề đổi mới phương pháp dạy học sinh giỏi theo hướng tích cực chủ động mà còn trang bị cho giáo viên cũng như các em hs một nền tảng kiến thức tốt về các dạng bài tập quay lui, quy hoạch động thường gặp. Từ đó nâng cao kiến thức, kỹ năng cho giáo viên, nâng cao chất lượng đội tuyển HSG hàng năm. Đặc biệt tạo một môi trường tốt để có những đội tuyển HSG kế tiếp cho môn tin và cho nhà trường. Bên cạnh đó sáng kiến còn có thể dùng làm tài liệu tham khảo tốt cho giáo viên, học sinh yêu thích với môn học lập trình, sử dụng cho quá trình ôn thi học sinh giỏi. IV. ĐIỀU KIỆN VÀ KHẢ NĂNG ÁP DỤNG Để áp dụng được sáng kiến này thì mỗi nhà trường cần xây dựng một kế hoạch dạy học hợp lý, phù hợp với đối tượng học sinh của trường mình. Qua thực nghiệm và tiến hành áp dụng trong các năm học đã qua, tài liệu rất hữu ích trong công tác giảng dạy của giáo viên. Đồng thời, nâng cao chất lượng giảng dạy và học tập bộ môn tin học 11, tạo được hứng thú học tập và góp phần bồi dưỡng năng lực tự học cho học sinh. Vì vậy, sáng kiến có thể áp dụng rộng rãi trong nhà trường nói riêng và toàn tỉnh nói chung. Chúng tôi xin cam đoan mọi thông tin nêu trong đơn là trung thực, đúng sự thật và hoàn toàn chịu trách nhiệm trước pháp luật. Gia Viễn, ngày 11 tháng 05 năm 2022 XÁC NHẬN CỦA LÃNH ĐẠO Người nộp đơn ĐƠN VỊ CƠ SỞ (Ký và ghi rõ họ tên) Nguyễn Mạnh Cường
6
7 PHỤ LỤC PHẦN I – ĐẶT VẤN ĐỀ 1. Lí do chọn sáng kiến Trong những năm gần đây vấn đề đổi mới căn bản và toàn diện nền giáo dục đã trở thành một vấn đề không chỉ riêng ngành giáo dục mà toàn xã hội quan tâm, đổi mới để đáp ứng với nhu cầu thực tiễn xã hội ngày nay. Một trong những sự thay đổi đó là thay đổi phương pháp dạy học từ phương pháp dạy học truyền thống sang phương pháp dạy học tích cực, từ người giáo viên là trung tâm của mọi hoạt động thì giờ đây với phương pháp dạy học tích cực học sinh trở thành trung tâm của các hoạt động, từ tiếp thu thụ động sang chủ động, tư duy, sáng tạo; giáo viên chỉ là người định hướng và hỗ trợ. Đây là một phương pháp đã được áp dụng rất thành công ở rất nhiều nước tiên tiến trên thế giới. Để làm được điều này người thầy cần phải thiết kế những bài giảng, những chuyên đề cho phù hợp với nội dung kiến thức; phương pháp, phương tiện dạy học phù hợp với từng đối tượng học sinh là một điều hết sức cấp thiết. Để qua mỗi phần học, tiết học học sinh thích thú với kiến thức mới, qua đó hiểu được kiến thức đã học trên lớp, đồng thời học sinh thấy được tầm quan trọng của vấn đề và việc ứng dụng của kiến thức trước hết để đáp ứng những yêu cầu của môn học, sau đó là việc ứng dụng của nó vào các công việc thực tiễn trong đời sống xã hội. Bồi dưỡng học sinh giỏi là công việc khó khăn, đòi hỏi nhiều công sức của giáo viên và học sinh. Đây là nhiệm vụ nặng nề nhưng cũng rất vinh dự cho giáo viên tham gia bồi dưỡng, việc phát triển bồi dưỡng học sinh giỏi góp phần đào tạo nhân tài cho đất nước được xem là nhiệm vụ cần thiết và quan trọng. Trường THPT Gia Viễn B thi học sinh giỏi môn tin từ năm 2008 đến nay cũng có được một số kinh nghiệm trong việc bồi dưỡng HSG. Tuy nhiên, các tài liệu nghiên cứu và bàn sâu về bồi dưỡng học sinh giỏi môn tin học hiện nay đã có nhiều sách vở và trên mạng, nhưng chưa phù hợp với đa số giáo viên, hệ thống bài tập không phong phú đa dạng. Mặt khác môn tin học thường bị xem là môn phụ. Vì vậy, khi chọn đội tuyển học sinh giỏi còn gặp nhiều khó khăn (cả về chất lượng và số lượng học sinh tham gia), tài liệu ôn luyện đều do giáo viên tự mày mò, nghiên cứu. Trong suốt những năm tham gia bồi dưỡng học sinh giỏi, chúng tôi cũng đã có được một số thành công nhưng cũng có nhiều thất bại. Chúng tôi luôn trăn trở: Làm thế nào để các em lĩnh hội tốt các kiến thức ôn luyện? Làm thế nào để kết quả đạt được tốt nhất? Làm thế nào để mang lại thành tích cho các em và mang lại vinh dự cho nhà trường? Vì vậy trong quá trình bồi dưỡng, chúng tôi luôn cố gắng tìm hiểu nội dung cơ bản và nâng cao, tìm ra phương pháp tối ưu để cho công tác bồi dưỡng có hiệu quả nhất phù hợp với đầu vào của học sinh. Bằng tất cả nỗ lực của từng cá nhân, của nhóm, qua tìm tòi, trao đổi và thảo luận với các đồng nghiệp trong và ngoài nhà trường, chúng tôi xin
8 mạnh dạn chia sẻ với các đồng nghiệp về đề tài “Giải thuật lập trình về quay lui và quy hoạch động cơ bản” để làm tài liệu cho chính chúng tôi giảng dạy trong nhà trường và cũng mong muốn góp một phần nhỏ vào công tác bồi dưỡng học sinh giỏi của nhà trường, để đội ngũ học sinh giỏi của trường ngày càng đạt kết quả cao hơn. Mặt khác làm tài liệu để các đồng nghiệp khác có thể tham khảo, cùng nhau góp ý, chia sẻ, áp dụng để công tác gia bồi dưỡng học sinh giỏi ngày càng có chất lượng tốt hơn 2. Mục đích của sáng kiến Ngoài việc giúp cho học sinh tiếp cận dễ dàng hiểu về quay lui và quy hoạch động cơ bản thì sáng kiến còn xây dựng hệ thống các dạng bài tập thường gặp để ôn luyện cho học sinh dự thi các kỳ thi học sinh giỏi môn tin học. 3. Phạm vi nghiên cứu Sáng kiến tập trung nghiên cứu nội dung quay lui và quy hoạch động cơ bản theo yêu cầu chuẩn của đề thi học sinh giỏi môn tin của trường THPT Gia Viễn B và của tỉnh Ninh Bình. 4. Phương pháp nghiên cứu a) Nghiên cứu lý luận: Tìm hiểu về các tài liệu đề cập đến quay lui , quy hoạch động cơ bản b) Nghiên cứu thực tiễn: Tìm hiểu về cách giảng dạy nội dung quay lui , quy hoạch động. c) Thực nghiệm sư phạm: Tiến hành thực nghiệm nhằm đánh giá tính khả thi, tính hiệu quả và tính phổ dụng của sáng kiến. Đồng thời, cũng nhằm hoàn thiện về mặt nội dung và lý luận trong sáng kiến.
9 PHẦN II - GIẢI QUYẾT VẤN ĐỀ I. CƠ SỞ LÝ LUẬN 1. Phương pháp quay lui Quay lui là một trong những kỹ thuật quan trọng vì nó cho phép giải một lớp các bài toán khá lớn có dạng tổng quát như: - Tìm một (hoặc tất cả) bộ nghiệm (x1, x2,…, xn) thỏa mãn điều kiện F nào đó, trong đó các thành phần xi được chọn từ tập hữu hạn Di với mọi i=1, 2, …, n Tư tưởng của phương pháp quay lui như sau: - Ta xây dựng bộ nghiệm từng bước, bắt đầu từ thành phần nghiệm x1 được chọn trong các giá trị có thể S1 = D1. - Giả sử đã chọn được các thành phần x 1, x2, …, xi-1, từ các điều kiện của bài toán ta sẽ xác định được tập Si gồm các giá trị được chọn cho thành phần nghiệm xi. Tập Si là tập con của Di và phụ thuộc vào các thành phần x 1, x2, …, xi-1 đã chọn. Chọn một phần tử xi thuộc Si như một thành phần của bộ nghiệm. Từ bộ (x1, x2, …, xi) lặp lại quá trình trên để tiếp tục mở rộng nghiệm cho thành phần xi+1. Nếu không chọn được thành phần nào của x i+1 (do Si+1 rỗng) thì ta quay lại chọn một phần tử khác của S i làm thành phần nghiệm xi (ý nghĩa của quay lui là ở bước này). - Trong quá trình mở rộng nghiệm ta luôn kiểm tra nghiệm thành phần có phải là nghiệm của bài toán hay không. Nếu chỉ cần một nghiệm thì ta dừng lại, nếu cần tìm tất cả các nghiệm thì quá trình tìm nghiệm chỉ dừng khi tất cả các khả năng chọn các thành phần nghiệm đã thỏa mãn. Quay lui là một trong các phương pháp trong đó các giá trị nghiệm được chọn không thực hiện được bằng cách duyệt tuyến tính. Điểm tốt của thuật toán quay lui so với tuyến tính là hạn chế bớt các nhánh phải duyệt mà theo những nhánh đó không tìm được lời giải thể hiện ở việc xây dựng các tập giá trị có thể Si khi tìm thành phần nghiệm xi và quay lui khi không mở rộng thành phần nghiệm xi+1. Tuy nhiên hạn chế của phương pháp này là phải duyệt qua nhiều khả năng nên độ phức tạp của chương trình thường ở mức giai thừa hay hàm mũ nên tốc độ tính toán khá lâu trong trường hợp kích thước của dữ liệu vào khá lớn. Để khắc phục hạn chế này người ta tìm cách hạn chế các khả năng không đưa đến kết quả bằng phương pháp nhánh cận, tuy nhiên lớp bài toán dùng được phương pháp này không nhiều. Đa số các bài toán sử dụng phương pháp duyệt đệ quy để xét hết mọi khả năng có thể có nghiệm theo nguyên tắc “thử sai” và quay lui. Về tư tưởng, các thuật toán rất đơn giản nhưng ứng dụng vào việc giải các bài toán cần có những kỹ thuật nhất định.
10 Để giải bài toán bằng thuật toán quay lui cần thực hiện các công việc quan trọng sau: - Tìm cách biểu diễn nghiệm của bài toán dưới dạng một dãy các đối tượng được chọn dần từng bước (x1, x2, …, xn). - Xác định được tập Si các khả năng được chọn làm thành phần thứ i của nghiệm. Chọn cách thích hợp để biểu diễn Si. - Tìm các điều kiện để các nghiệm đã chọn là các nghiệm của bài toán. Một số lưu ý khi xây dựng thuật toán quay lui: - Phải duyệt qua mọi phương án của bài toán có thể chứa nghiệm. - Tránh trường hợp duyệt trùng lặp các khả năng đã duyệt. Thông thường ta thường dùng thủ tục đệ quy Try(i : Integer) để chọn thành phần nghiệm xi. Có ba dạng cơ bản trong các thuật toán quay lui: Dạng 1: Tìm tất cả các nghiệm. Dạng 2: Tìm một nghiệm. Dạng 3: Tìm nghiệm tối ưu thỏa mãn điều kiện. Trong sáng kiến kinh nghiệm này ta lần lượt xét cách giải các dạng trên bằng phương pháp quay lui. 2. Phương pháp quy hoạch động Quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Ðối với một số bài toán đệ quy, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Ðể giải quyết một bài toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương án quy hoạch động, nguyên lý chia để trị càng được thể hiện rõ: Khi không biết phải giải quyết những bài toán con nào, ta sẽ đi giải quyết toàn bộ các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Ðó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng là nội dung phương pháp quy hoạch động: - Phép phân giải đệ quy bắt đầu từ bài toán lớn phân ra thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân ra tiếp thành nhiều bài toán nhỏ hơn và lại đi giải các bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa. - Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết nhưng bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu). Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thỏa mãn những yêu cầu dưới đây không:
11 Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn. Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải (bộ nhớ, đĩa, …) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được. Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước. Các bước cài đặt một chương trình sử dụng quy hoạch động: - Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng phương án. - Dùng công thức truy hồi phối hợp những lời giải của các bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của các bài toán lớn hơn rồi lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải. - Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu. Cho tới nay, vẫn chưa có một định lý nào cho biết một cách chính xác những bài toán nào có thể giải quyết hiệu quả bằng quy hoạch động. Tuy nhiên để biết được bài toán có thể giải bằng quy hoạch động hay không, ta có thể đặt câu hỏi: “Một nghiệm tối ưu của bài toán lớn có phải là sự phối hợp các nghiệm tối ưu của các bài toán con hay không?” và “Liệu có thể nào lưu trữ được nghiệm các bài toán con dưới một hình thức nào đó để phối hợp tìm được ngiệm bài toán lớn?”. II. CƠ SỞ THỰC TIỄN Gần một nửa các bài thi trong các cuộc thi code cần đến quy hoạch động và quay lui . Tất nhiên, có những cách khác để giải bài toán đó. Nhưng vì các cuộc thi code đều có giới hạn về thời gian (thường giới hạn thời gian 1s/test), cũng như bộ nhớ của chương trình, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong những trường hợp như vậy, quy hoạch động, quay lui vét can là một trong những thuật toán xuất hiện nhiều nhất. Thuật toán quy hoạch động, quay lui được ưa chuộng bởi vì ban đầu, bài toán có muôn hình vạn trạng và bạn phải suy nghĩ rất nhiều mới tìm ra được lời giải. Không có một công thức chuẩn mực nào áp dụng được cho mọi bài toán. Bởi vì sự phổ biến của nó, học sinh bắt buộc phải cực kỳ thuần thục 2 thuật toán này nếu muốn có kết quả tốt trong các cuộc thi. III. CÁC BIỆN PHÁP ĐỂ GIẢI QUYẾT VẤN ĐỀ 1. Thuật toán quay lui 1.1. Xây dựng giải thuật Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
12 Giả sử cấu hình cần liệt kê có dạng x[1..n], khi đó thuật toán quay lui thực hiện qua các bước: 1) Xét tất cả các giá trị x[1] có thể nhận, thử cho x[1] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[1] ta sẽ: 2) Xét tất cả các giá trị x[2] có thể nhận, lại thử cho x[2] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[2] lại xét tiếp các khả năng chọn x[3] … cứ tiếp tục như vậy đến bước: … n) Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị đó, thông báo cấu hình tìm được 〈x[1], x[2], …, x[n]〉. Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các cấu hình n phần tử dạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x[1] bài toán trở thành liệt kê tiếp cấu hình n - 1 phần tử x[2..n]. 1.2. Mô hình giải thuật {Thủ tục này thử cho x[i] nhận lần lượt các giá trị mà nó có thể nhận} procedure Try(i: Integer); begin for 〈mọi giá trị V có thể gán cho x[i]〉 do begin 〈Thử cho x[i] := V〉; if 〈x[i] là phần tử cuối cùng trong cấu hình〉 then 〈Thông báo cấu hình tìm được〉 else begin 〈Ghi nhận việc cho x[i] nhận giá trị V (nếu cần)〉; Try(i + 1); {Gọi đệ quy để chọn tiếp x[i+1]} 〈Nếu cần, bỏ ghi nhận việc thử x[i] := V để thử giá trị khác〉; end; end; end; Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1) 1.3. Một số ví dụ cơ bản 1.3.1. Dạng 1 - tìm tất cả các nghiệm 1.3.1.1. Liệt kê các dãy nhị phân độ dài N Biểu diễn dãy nhị phân độ dài N dưới dạng x[1..n]. Ta sẽ liệt kê các dãy này bằng cách thử dùng các giá trị {0, 1} gán cho x[i]. Với mỗi giá trị thử gán cho x[i] lại thử các giá trị có thể gán cho x[i+1]. Chương trình liệt kê bằng thuật toán quay lui có thể viết: Liệt kê các dãy nhị phân độ dài n
13 Program BinaryStrings; Const InputFile = 'BSTR.INP'; OutputFile = 'BSTR.OUT'; max = 30; var x: array[1..max] of Integer; n: Integer; f: Text; {********************************} procedure PrintResult; {In cấu hình tìm được, do thủ tục tìm đệ quy Try gọi khi tìm ra một cấu hình} var i: Integer; begin for i := 1 to n do Write(f, x[i]); WriteLn(f); end; {********************************} procedure Try(i: Integer); {Thử các cách chọn x[i]} var j: Integer; begin for j := 0 to 1 do {Xét các giá trị có thể gán cho x[i], với mỗi giá trị đó} begin x[i] := j; {Thử đặt x[i]} if i = n then PrintResult {Nếu i = n thì in kết quả} else Try(i + 1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp x[i+1]} end; end; {********************************} begin Assign(f, InputFile); Reset(f); ReadLn(f, n); {Nhập dữ liệu} Close(f); Assign(f, OutputFile); Rewrite(f); Try(1); {Thử các cách chọn giá trị x[1]} Close(f); end.
14 1.3.1.2. Liệt kê các tập con k phần tử Để liệt kê các tập con k phần tử của tập S = {1, 2, …, n} ta có thể đưa về liệt kê các cấu hình x[1..n], ở đây các x[i] ∈ S và x[1] < x[2] < … < x[k]. Ta có nhận xét: x[k] ≤ n x[k-1] ≤ x[k] - 1 ≤ n - 1 … x[i] ≤ n - k + i … x[1] ≤ n - k + 1. Từ đó suy ra x[i-1] + 1 ≤ x[i] ≤ n - k + i (1 ≤ i ≤ k) ở đây ta giả thiết có thêm một số x[0] = 0 khi xét i = 1. Như vậy ta sẽ xét tất cả các cách chọn x[1] từ 1 (=x[0] + 1) đến n - k + 1, với mỗi giá trị đó, xét tiếp tất cả các cách chọn x[2] từ x[1] +1 đến n - k + 2, … cứ như vậy khi chọn được đến x[k] thì ta có một cấu hình cần liệt kê. Liệt kê các tập con k phần tử program Combination; const InputFile = 'SUBSET.INP'; OutputFile = 'SUBSET.OUT'; max = 30; var x: array[0..max] of Integer; n, k: Integer; f: Text; {********************************} procedure PrintResult; (*In ra tập con {x[1], x[2], …, x[k]}*) var i: Integer; begin Write(f, '{'); for i := 1 to k - 1 do Write(f, x[i], ', '); WriteLn(f, x[k], '}'); end; {********************************} procedure Try(i: Integer); {Thử các cách chọn giá trị cho x[i]} var j: Integer; begin for j := x[i - 1] + 1 to n - k + i do begin
15 x[i] := j; if i = k then PrintResult else Try(i + 1); end; end; {********************************} begin Assign(f, InputFile); Reset(F); ReadLn(f, n, k); Close(f); Assign(f, OutputFile); Rewrite(f); x[0] := 0; Try(1); Close(f); end. 1.3.1.3. Bài toán phân tích số Bài toán Cho một số nguyên dương n ≤ 30, hãy tìm tất cả các cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là 1 cách. Cách làm: Ta sẽ lưu nghiệm trong mảng x, ngoài ra có một mảng t. Mảng t xây dựng như sau: t[i] sẽ là tổng các phần tử trong mảng x từ x[1] đến x[i]: t[i] := x[1] + x[2] + … + x[i]. Khi liệt kê các dãy x có tổng các phần tử đúng bằng n, để tránh sự trùng lặp ta đưa thêm ràng buộc x[i-1] ≤ x[i]. Vì số phần tử thực sự của mảng x là không cố định nên thủ tục PrintResult dùng để in ra 1 cách phân tích phải có thêm tham số cho biết sẽ in ra bao nhiêu phần tử. Thủ tục đệ quy Try(i) sẽ thử các giá trị có thể nhận của x[i] (x[i] ≥ x[i - 1]) Khi nào thì in kết quả và khi nào thì gọi đệ quy tìm tiếp ? Lưu ý rằng t[i - 1] là tổng của tất cả các phần tử từ x[1] đến x[i-1] do đó - Khi t[i] = n tức là (x[i] = n - t[i - 1]) thì in kết quả - Khi tìm tiếp, x[i+1] sẽ phải lớn hơn hoặc bằng x[i]. Mặt khác t[i+1] là tổng của các số từ x[1] tới x[i+1] không được vượt quá n. Vậy ta có t[i+1] ≤ n ⇔ t[i-1] + x[i] + x[i+1] ≤ n ⇔x[i] + x[i+1] ≤ n - t[i-1] tức là x[i] ≤ (n - t[i-1])/2. Ví dụ đơn giản khi n = 10 thì chọn x[1] =6, 7, 8, 9 là việc làm vô nghĩa vì như vậy cũng không ra nghiệm mà cũng không chọn tiếp x[2] được nữa. Một cách dễ hiểu: ta gọi đệ quy tìm tiếp khi giá trị x[i] được chọn còn cho phép chọn thêm một phần tử khác lớn hơn hoặc bằng nó mà không làm
16 tổng vượt quá n. Còn ta in kết quả chỉ khi x[i] mang giá trị đúng bằng số thiếu hụt của tổng i-1 phần tử đầu so với n. Vậy thủ tục Try(i) thử các giá trị cho x[i] có thể viết như sau: (để tổng quát cho i = 1, ta đặt x[0] = 1 và t[0] = 0). - Xét các giá trị của x[i] từ x[i - 1] đến (n - t[i-1]) div 2, cập nhật t[i] := t[i - 1] + x[i] và gọi đệ quy tìm tiếp. - Cuối cùng xét giá trị x[i] = n - t[i-1] và in kết quả từ x[1] đến x[i]. Input: file văn bản ANALYSE.INP chứa số nguyên dương n ≤ 30 Output: file văn bản ANALYSE.OUT ghi các cách phân tích số n. ANALYSE.INP ANALYSE.OUT 6 6 = 1+1+1+1+1+1 6 = 1+1+1+1+2 6 = 1+1+1+3 6 = 1+1+2+2 6 = 1+1+4 6 = 1+2+3 6 = 1+5 6 = 2+2+2 6 = 2+4 6 = 3+3 6=6 Bài toán phân tích số program Analyses; const InputFile = 'ANALYSE.INP'; OutputFile = 'ANALYSE.OUT'; max = 30; var n: Integer; x: array[0..max] of Integer; t: array[0..max] of Integer; f: Text; {********************************} procedure Init; {Khởi tạo} begin Assign(f, InputFile); Reset(f); ReadLn(f, n); Close(f); x[0] := 1; t[0] := 0; end;
17 {********************************} procedure PrintResult(k: Integer); var i: Integer; begin Write(f, n, ' = '); for i := 1 to k - 1 do Write(f, x[i], '+'); WriteLn(f, x[k]); end; {********************************} procedure Try(i: Integer); var j: Integer; begin for j := x[i - 1] to (n - T[i - 1]) div 2 do {Trường hợp còn chọn tiếp x[i+1]} begin x[i] := j; t[i] := t[i - 1] + j; Try(i + 1); end; x[i] := n - T[i - 1]; {Nếu x[i] là phần tử cuối thì nó bắt buộc phải là n-T[i-1], in kết quả} PrintResult(i); end; {********************************} begin Init; Assign(f, OutputFile); Rewrite(f); Try(1); Close(f); end. 1.3.2. Dạng 2 - tìm một nghiệm Bài toán máy rút tiền tự động ATM Một máy rút tiền tự động ATM có n (n
18 Kết quả ra file “ATM.OUT” có dạng: Nếu có thể trả đúng S thì đưa ra cách trả, nếu không thì ghi -1 ATM.INP ATM.OUT 10 390 20 20 50 50 50 100 100 200 10 20 20 50 50 50 50 100 100 Nghiệm của bài toán là một dãy nhị phân độ dài n, trong đó thành phần thứ I bằng 1 nếu tờ tiền thứ I được sử dụng để trả, bằng 0 trong trường hợp ngược lại X=(x1,x2,…,xn) là nghiệm nếu x1 x t1+ x2 x t2+…+ xn x tn=s Chương trình dưới đây có sử dụng một biến ok để kiểm soát việc tìm nghiệm. Ban đầu chưa có nghiệm, do đó khởi tạo giá trị ok=FALSE. Khi tìm được nghiệm, ok sẽ được nhận giá trị bằng TRUE. Nếu ok=TRUE (đã tìm thấy nghiệm) ta sẽ không cần tìm kiếm nữa. Máy rút tiền tự động ATM Program atm; const max =20; InputFile ='ATM.INP'; OutputFile ='ATM.OUT'; type vector =array[1..MAX]of longint; var t :array[1..MAX]of longint; x,xs :vector; n,s,sum :longint; ok :boolean; {********************************} procedure input; var f :text; i :longint; begin assign(f, InputFile); reset(f); readln(f,n, s); for i:=1 to n do read(f,t[i]); close(f); end; {********************************} procedure check(x:vector); var
19 i :longint; f :text; begin if sum = s then begin xs:=x; ok:=true; end; end; {********************************} procedure printResult; var i :longint; f :text; begin assign(f, OutputFile); rewrite(f); if ok then begin for i:=1 to n do if xs[i]=1 then write(f,t[i],' '); end else write(f,'-1'); close(f); end; {********************************} procedure Try(i:longint); var j :longint; begin for j:=0 to 1 do begin x[i]:=j; sum:=sum + x[i]*t[i]; if (i=n) then check(x) else if sum
20 {********************************} begin input; ok:=false; sum:=0; Try(1); PrintResult; end. Ngoài ra ta có cách thể hiện khác của thuật toán quay lui máy đếm tiền tự động ATM Program atm; const InputFile ='ATM.INP'; OutputFile ='ATM.OUT'; var t:array[1..100] of longint; a,x:array[1..100] of 0..1; i,n:integer; sum,s:int64; kt:boolean; fi,fo:text; {********************************} procedure xuat; var i:integer; begin sum:=0; for i:=1 to n do sum:=sum+a[i]*t[i]; if sum=s then begin x:= a; kt:=true; exit; end; end; {********************************} procedure try(i:integer); var