TAILIEUCHUNG - Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 1 - Chương 6

PHƯƠNG PHÁP QUAY LUI Giả sử ta phải tìm trong một tập dữ liệu D cho trước một dãy dữ liệu: v = (v[1], v[2],., v[n]) thoả mãn đồng thời hai tính chất P và Q. Trước hết ta chọn một trong hai tính chất đã cho để làm nền, giả sử ta chọn tính chất P. Sau đó ta thực hiện các bước sau đây: Bước 1. (Khởi trị) Xuất phát từ một dãy ban đầu v = (v[1],., v[i]) nào đó của các phần tử trong D sao cho v thoả P. Bước 2. Nếu v thoả Q. | Sáng tạo trong Thuật toán và Lập trình Tập I 163 CHƯƠNG 6 PHƯƠNG PHÁP QUAY LUI Giả sử ta phải tìm trong một tập dữ liệu D cho trước một dãy dữ liệu v v 1 v 2 . v n thoả mãn đồng thời hai tính chất P và Q. Trước hết ta chọn một trong hai tính chất đã cho để làm nền giả sử ta chọn tính chất P. Sau đó ta thực hiện các bước sau đây Bước 1. Khởi trị Xuất phát từ một dãy ban đầu v v 1 . v i nào đó của các phần tử trong D sao cho v thoả P. Bước 2. Nếu v thoả Q ta dừng thuật toán và thông báo kết quả là dãy v ngược lại ta thực hiện Bước 3. Bước 3. Tìm tiếp một phần tử v i 1 để bổ sung cho v sao cho v v 1 . v i v i 1 thoả P. Có thể xảy ra các trường hợp sau đây . Tìm được phần tử v i 1 quay lại bước 2. . Không tìm được v i 1 như vậy tức là với mọi v i 1 có thể lấy trong D dãy v v 1 . v i v i 1 không thoả P. Điều này có nghĩa là đi theo đường v v 1 . v i sẽ không dẫn tới kết quả. Ta phải đổi hướng tại một vị trí nào đó. Để thoát khỏi ngõ cụt này ta tìm cách thay v i bằng một giá trị khác trong D. Nói cách khác ta loại v i khỏi dãy v giảm i đi một đơn vị rồi quay lại Bước 3. Cách làm như trên được gọi là quay lui lùi lại một bước. Dĩ nhiên ta phải đánh dấu v i là phần tử đã loại tại vị trí i để sau đó không đặt lại phần tử đó vào vị trí i trong dãy v. Khi nào thì có thể trả lời là không tồn tại dãy v thoả đồng thời hai tính chất P và Q Nói cách khác khi nào thì ta có thể trả lời là bài toán vô nghiệm Dễ thấy bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng. Ta nói là đã vét cạn mọi khả năng. Chú ý rằng có thể đến một lúc nào đó ta phải lùi liên tiếp nhiều lần. Từ đó suy ra rằng thông thường bài toán vô nghiệm khi ta không còn có thể lùi được nữa. Có nhiều sơ đồ giải các bài toán quay lui dưới đây là hai sơ đồ khá đơn giản không đệ quy. Sơ đồ 1 Giải bài toán quay lui tìm 1 nghiệm Khởi trị v v thoả P repeat if v thoả Q then begin Ghi nhận nghiệm exit Sơ đồ 2 Giải bài toán quay lui tìm 1 nghiệm Khởi trị v v thoả P repeat if v thoả Q then begin Ghi nhận nghiệm exit Sáng

• Kỹ thuật lập trình
• ngôn ngữ Pascal
• lập trình C#
• giải bài toán tin
• giáo trình lập trình
• thuật toán máy tính
• Ngôn ngữ lập trình Pascal
• Bài giảng Ngôn ngữ lập trình Pascal
• Thực hành Turbo Pascal
• Turbo Pascal Version 5
• Turbo Pascal Version 7
• Cách khởi động Turbo Pascal
• kinh nghiệm sử dụng
• lập trình căn bản
• ngôn ngữ lập trình
• kỹ thuật pascal
• tài liệu về pascal
• lập trình pascal
• giáo trình pascal căn bản
• kỹ thuật phần mềm
• giải bài toán pascal
• tài liêu bài toán pascal
• bài tập tin học
• Pascal
• tài liệu ngôn ngữ pascal
• giáo trình pascal
• bài giảng ngôn ngữ pascal
• Lý thuyết và bài tập Pascal
• Thành phần ngôn ngữ Pascal
• Ngôn ngữ lập trình cấp cao
• Ký hiệu của Pascal
• Ký tự trong Pascal
• Giáo trình Ngôn ngữ lập trình Pascal
• Giới thiệu chương trình Pascal
• Cấu trúc chương trình Pascal
• Ký tự sử dụng trong Pascal
• Bài tập Pascal cơ bản
• Các dạng bài tập Pascal
• Một số mẫu bài tập Pascal
• Bài tập Pascal
• Ôn tập Pascal
• Bài giảng môn Lập trình Pascal
• Môn lập trình Pascal
• Môi trường làm việc của Turbo Pascal
• Kỹ thuật Lập trình Pascal
• ứng dụng Pascal
• giáo trình
• Giáo trình bài tập Pascal
• Bài tập ngôn ngữ lập trình Pascal
• Bài giảng Lập trình Pascal
• Lệnh cơ bản trong Pascal
• Cấu trúc một chương trình Pascal
• Thuật toán lập trình
• Các khái niệm trong Pascal
• Kiểu dữ liệu đơn giản
• Các câu lệnh điều khiển
• giáo án tin học
• Giáo trình Tin học
• Cách sử dụng ngôn ngữ Pascal
• Câu hỏi Pascal
• Thành phần Pascal
• Ôn tập thi liên thông ngành tin học
• Thành phần của ngôn ngữ lập trình pascal
• Ôn tập Pascal cơ bản
• toán Pascal
• bài tập toán Pascal
• tài liệu toán Pascal
• lý thuyết toán Pascal
• Tự học lập trình Pascal
• Bài tập lập trình Pascal
• Kỹ thuật lập trình
• Học lập trình Pascal