Chương 5: Đệ qui

Chia sẻ: Batman_1 Batman_1 | Ngày: | Loại File: PPT | Số trang:27

Thêm vào BST

Báo xấu

62
lượt xem 8
download

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

Khái niệm (định nghĩa) đệ qui có dùng lại chính nó. Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân cho giai thừa của n-1 nếu n 0 Quá trình đệ qui gồm 2 phần: Trường hợp cơ sở (base case) Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở Ví dụ trên: Giai thừa của n là 1 nếu n là 0 Giai thừa của n là n * (giai thừa của n-1) nếu n0

Chủ đề:

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

Lưu

Nội dung Text: Chương 5: Đệ qui

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 5: Đệ qui
Khái niệm đệ qui Khái niệm (định nghĩa) đệ qui có dùng lại chính nó.   Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân cho giai thừa của n-1 nếu n > 0 Quá trình đệ qui gồm 2 phần:   Trường hợp cơ sở (base case)  Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở Ví dụ trên:   Giai thừa của n là 1 nếu n là 0  Giai thừa của n là n * (giai thừa của n-1) n ếu n>0 2 Chương 5: Đệ qui
Tính giai thừa Định nghĩa không đệ qui:   n! = n * (n-1) * … * 1 Định nghĩa đệ qui:  nếu n=0  n! = 1 nếu n>0 n * (n-1)! Mã C++:  int factorial(int n) { if (n==0) return 1; else return (n * factorial(n - 1)); } 3 Chương 5: Đệ qui
Thi hành hàm tính giai thừa factorial (3) n=3 factorial (2) … n=2 3*factorial(2) … factorial (1) 6 n=1 2*factorial(1) … 2 factorial (0) n=0 1*factorial(0) … 1 return 1; 1 4 Chương 5: Đệ qui
Trạng thái hệ thống khi thi hành hàm tính giai thừa Stack hệ thống factorial(0) factorial(1) factorial(1) factorial(1) factorial(2) factorial(2) factorial(2) factorial(2) factorial(2) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) t Thời gian hệ thống Trả về từ Trả về từ Trả về từ Trả về từ Gọi hàm Gọi hàm Gọi hàm Gọi hàm hàm hàm hàm hàm factorial(3) factorial(2) factorial(1) factorial(0) factorial(0 factorial(1 factorial(2 factorial(3 ) ) ) ) t 5 Chương 5: Đệ qui
Bài toán Tháp Hà nội Luật:   Di chuyển mỗi lần một đĩa  Không được đặt đĩa lớn lên trên đĩa nh ỏ 6 Chương 5: Đệ qui
Bài toán Tháp Hà nội – Thiết kế hàm Hàm đệ qui:   Chuyển (count-1) đĩa trên đỉnh của cột start sang c ột temp  Chuyển 1 đĩa (cuối cùng) của cột start sang cột finish  Chuyển count-1 đĩa từ cột temp sang cột finish magic 7 Chương 5: Đệ qui
Bài toán Tháp Hà nội – Mã C++ void move(int count, int start, int finish, int temp) { if (count > 0) { move(count − 1, start, temp, finish); cout
Bài toán Tháp Hà nội – Thi hành 9 Chương 5: Đệ qui
Bài toán Tháp Hà nội – Cây đệ qui 10 Chương 5: Đệ qui
Thiết kế các giải thuật đệ qui Tìm bước chính yếu (bước đệ qui)  Tìm qui tắc ngừng  Phác thảo giải thuật   Dùng câu lệnh if để lựa chọn trường h ợp. Kiểm tra điều kiện ngừng   Đảm bảo là giải thuật luôn dừng lại. Vẽ cây đệ qui   Chiều cao cây ảnh hưởng lượng bộ nhớ cần thiết.  Số nút là số lần bước chính yếu được thi hành. 11 Chương 5: Đệ qui
Cây thi hành và stack hệ thống Cây thi hành 12 Chương 5: Đệ qui
Đệ qui đuôi (tail recursion) Định nghĩa: câu lệnh thực thi cuối cùng là lời gọi đệ qui đến  chính nó. Khử: chuyển thành vòng lặp.  13 Chương 5: Đệ qui
Khử đệ qui đuôi hàm giai thừa Giải thuật:  product=1 for (int count=1; count < n; count++) product *= count; 14 Chương 5: Đệ qui
Dãy số Fibonacci Định nghĩa:   F0 = 0  F1 = 1  Fn = Fn-1 + Fn-2 khi n>2 Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …  Hàm đệ qui:  int fibonacci (int n) { if (n
Dãy số Fibonacci – Cây thi hành Đã tính rồi 16 Chương 5: Đệ qui
Dãy số Fibonacci – Khử đệ qui Nguyên tắc:   Dùng biến lưu trữ giá trị đã tính của F n-2 biến lưu trữ giá trị đã tính của Fn-1  Dùng Fn = Fn-1 + Fn-2 và lưu lại để dùng cho lần sau  Tính Giải thuật:  int Fn2=0, Fn1=1, Fn; for (int i = 2; i
Bài toán 8 con Hậu 18 Chương 5: Đệ qui
Bài toán 4 con Hậu 19 Chương 5: Đệ qui
Bài toán 8 con Hậu – Giải thuật Algorithm Solve Input trạng thái bàn cờ Output if trạng thái bàn cờ chứa đủ 8 con hậu 1. 1.1. In trạng thái này ra màn hình 2. else 2.1. for mỗi ô trên bàn cờ mà còn an toàn 2.1.1. thêm một con hậu vào ô này 2.1.2. dùng lại giải thuật Solve với trạng thái mới 2.1.3. bỏ con hậu ra khỏi ô này End Solve Vét cạn 20 Chương 5: Đệ qui