TAILIEUCHUNG - Giáo trình lập trình nâng cao - Chương 5

Tài liệu tham khảo Giáo trình lập trình nâng cao trên ngôn ngữ Pascal soạn theo chương trình đã được Bộ giáo dục và đào tạo phê chuẩn - Chương 5 Giải thuật đệ quy | Chương 5 Giải thuật đệ quy Nội dung của chương này đề cập đến những bài toán có tính đệ quy. Không phải bài toán nào cũng có tính đệ quy và không phải các bài toán có tính đệ quy thì đều phải giải bằng giải thuật đệ quy. Các vấn đề cần quan tâm trong chương này Bài toán có tính đệ quy không Có cần dùng giải thuật đệ quy không Đệ quy có mang lại hiệu quả hơn các phương pháp thông thường hay không Trường Đại học Nông nghiên 1 - Giáo trình ĩ ập trình nâng cao 133 1. Khái niệm đệ quy Trong thân một chương trình con có thể đưa lời gọi tới chính chương trình con đó tính chất này được gọi là tính Đệ qui của chương trình con . Trong toán học khái niệm giai thừa được định nghĩa như sau 0 1 Nếu n 0 thì n 1 2 3 . n Từ định nghĩa trên dễ dàng thấy rằng n n n-1 n-1 n-1 n-2 1 1 0 1 Cách thức lập luận như trên đưa chúng ta tới một nhận xét tổng quát là lời giải của bài toán A có thể được thực hiện bởi lời giải của bài toán A có dạng giống như A. Thật vậy việc tính n có thể được thực hiện bởi việc tính n-1 . Điều quan trọng để bài toán có lời giải là tuy A giống như A song thực chất A phải nhỏ hơn A và quá trình thu nhỏ phải có điểm dừng. Trong bài toán tính giai thừa từ chỗ cần tính giai thừa của n chúng ta đi tính giai thừa của n-1 để tính giai thừa của n-1 chúng ta đi tính giai thừa của n-2 . kết thúc là giai thừa của 0. Một đối tượng được gọi là đệ quy nếu nó được định nghĩa dưới dạng của chính nó. Giải thuật của bài toán A được gọi là đệ quy nếu nó dẫn tới việc giải bài toán A giống như A nhưng nhỏ hơn A và quá trình phải có điểm dừng. Xét bài toán tính giai thừa với n 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1 Ô nhớ cuối 1 1 2 2 1 3 3 2 4 4 3 Ô nhớ đầu 5 5 4 Hình Như vậy khi biết 1 thì tính được 2 biết 2 Thì tính được 3 . Bằng cách sử dụng bộ nhớ ngăn xếp theo nguyên tắc LIFO Last In - First Out Hình những gì gửi vào cuối cùng thì được lấy ra trước tiên. Bóc ô nhớ trên đỉnh ta có 1 1 và lộ ra ô tiếp theo 2 2 1 . Vì 1 đã biết nên tính được 2 2 bóc tiếp ô nhớ phía dưới ta có 3 3 2

• Kỹ thuật lập trình
• ngôn ngữ Pascal
• lập trình Pascal
• lập trình nâng cao
• kiểu dữ liệu
• chương trình con
• 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
• 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