Bài giảng Hệ thống máy tính và ngôn ngữ C: Chương 14 - TS. Nguyễn Phúc Khải

Bài giảng Hệ thống máy tính và ngôn ngữ C - Chương 14: Đệ quy, được biên soạn gồm các nội dung chính sau: Đệ quy là gì?; Đệ quy và lặp; Tháp Hà nội; Dãy số Fibonacci; Tìm kiếm nhị phân; Chuyển số nguyên sang dãy ký tự ASCII; Cấu trúc dữ liệu cây – cây nhị phân. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ thống máy tính và ngôn ngữ C: Chương 14 - TS. Nguyễn Phúc Khải om .c ng co an th o ng du ucu Company LOGO 1CuuDuongThanCong.com https://fb.com/tailieudientucntt Các nội dung: Đệ quy là gì? om .c Đệ quy và lặp ng Tháp Hà nội co Dãy số Fibonacci an Tìm kiếm nhị phân th o ng Chuyển số nguyên sang dãy ký tự ASCII du u Cấu trúc dữ liệu cây – cây nhị phân cu CuuDuongThanCong.com © TS. Nguyễn Phúc Khải https://fb.com/tailieudientucntt 2 Đệ quy là gì? n Ví dụ 18.1: Tính tổng  i om 1 .c int RunningSum(int n) ng { co if (n == 1) an return 1; else th ng return n + RunningSum(n-1); o du } u cu CuuDuongThanCong.com © TS. Nguyễn Phúc Khải https://fb.com/tailieudientucntt 3 ĐỆ QUY VÀ LẶP Tất cả các hàm đệ quy đều có thể được viết om bằng vòng lặp. .c ng Việc sử dụng đệ quy sẽ dễ dàng và trong co sáng hơn khi dùng vòng lặp. an th Bản đệ quy tương đối chậm vì các hàm đệ quy ng chịu sự gọi hàm còn vòng lặp thì không. o du u cu CuuDuongThanCong.com © TS. Nguyễn Phúc Khải https://fb.com/tailieudientucntt 4 THÁP HÀ NỘI Bài toán: một nền có ba cột, một trong ba cột có các om đĩa gỗ sắp theo thứ tự đĩa nhỏ ở trên đĩa lớn ở dưới. .c Chúng ta phải chuyển tất cả các đĩa từ cột hiện thời ng co qua một trong hai cột kia theo hai luật sau: mỗi lần an chỉ được di chuyển một đĩa và đĩa lớn không được đặt th trên đĩa nhỏ. ng o du u cu CuuDuongThanCong.com © TS. Nguyễn Phúc Khải https://fb.com/tailieudientucntt 5 DÃY SỐ FIBONACCI om Ta có phương trình toán truy hồi sau .c f (n) = f (n - 1) + f (n - 2) ng co f (1) = 1 an f (0) = 1 th o ng hàm đệ quy để tính số Fibonacci thứ n là phương du u ...