tailieunhanh - 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 đượ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! | om .c ng co an th o ng du u cu Company LOGO 1 https 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 TS. Nguyễn Phúc Khải https tailieudientucntt 2 Đệ quy là gì n Ví dụ 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 TS. Nguyễn Phúc Khải https 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 TS. Nguyễn Phúc Khải https 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 TS. Nguyễn Phúc Khải https 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 cu trình truy hồi trên. TS. Nguyễn Phúc Khải https tailieudientucntt 6 CÁC BÀI TOÁN Tìm kiếm nhị phân om .c Chuyển số nguyên sang chuỗi ký tự ASCII ng co an th o ng du u cu TS. Nguyễn Phúc Khải https tailieudientucntt 7 om .c ng co an th o ng du u cu TS. Nguyễn Phúc Khải https tailieudientucntt 8