intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

ĐỆ QUY (Recursion)

Chia sẻ: Trần Công Chính | Ngày: | Loại File: PPT | Số trang:58

Thêm vào BST
Báo xấu
366
lượt xem 122
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phương pháp thiết kế một giải thuật đệ quy: Tham số hoá bài toán. Phân tích trường hợp chung : đưa bài toán dưới dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến. Tìm trường hợp suy biến.

Chủ đề:

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

Lưu

Nội dung Text: ĐỆ QUY (Recursion)

  1. Chương 2: Ch ĐỆ QUY (Recursion)
  2. NộI DUNG  Đệ quy (recursion) 1. Các loại đệ quy (types of recursion) 2. 2
  3. 1. Đệ quy (Recursion) Phương pháp thiết kế một giải thuật đệ quy:  Tham số hoá bài toán ◦ Phân tích trường hợp chung : đưa bài toán dưới dạng bài  ◦ toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn  theo nghiã dần dần sẽ tiến đến trường hợp suy biến Tìm trường hợp suy biến ◦ 3 Chương 2: Hàm – Đệ quy
  4. 1. Đệ quy (Recursion)  Chương trình đệ quy gồm hai phần chính: 1. Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng) 2. Phần đệ quy: Trong phần thân chương trình có lời gọi  đến chính bản thân chương trình với giá trị mới của  tham số nhỏ hơn giá trị ban đầu 4 Chương 2: Hàm – Đệ quy
  5.  1. Đệ quy (Recursion) – GT.41 Ví dụ 1 : Lập hàm tính n! bằng đệ quy  n * (n - 1)! n!=  0! = 1 int GT(int n) { if (n==0) // điểm dừng return 1; else  return n*GT(n­1); } 5 Chương 2: Hàm – Đệ quy
  6.  1. Đệ quy (Recursion) Minh họa Gọi hàm answer
  7.  1. Đệ quy (Recursion) Minh họa Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  8.  1. Đệ quy (Recursion) Minh họa Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  9.  1. Đệ quy (Recursion) Minh họa Chưa xong: 3*GT(2) GT. 3rd: N=3, Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  10.  1. Đệ quy (Recursion) Minh họa Chưa xong: 2*GT(1) GT. 4th: N=2, Chưa xong: 3*GT(2) GT. 3rd: N=3, Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  11.  1. Đệ quy (Recursion) Minh họa Chưa xong: 1*GT(0) GT. 5th: N=1, Chưa xong: 2*GT(1) GT. 4th: N=2, Chưa xong: 3*GT(2) GT. 3rd: N=3, Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  12.  1. Đệ quy (Recursion) Minh họa GT. 6th: N=0, xong: returns 1 Chưa xong: 1*GT(0) GT. 5th: N=1, Chưa xong: 2*GT(1) GT. 4th: N=2, Chưa xong: 3*GT(2) GT. 3rd: N=3, Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  13.  1. Đệ quy (Recursion) Minh họa GT. 5th: N=1, xong: returns 1*1 Chưa xong: 2*GT(1) GT. 4th: N=2, Chưa xong: 3*GT(2) GT. 3rd: N=3, Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  14.  1. Đệ quy (Recursion) Minh họa GT. 4th: N=2, xong: returns 2*1 Chưa xong: 3*GT(2) GT. 3rd: N=3, Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  15.  1. Đệ quy (Recursion) Minh họa GT. 3rd: N=3, xong: returns 3*2 Chưa xong: 4*GT(3) GT. 2nd: N=4, Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  16.  1. Đệ quy (Recursion) Minh họa GT. 2nd: N=4, xong: returns 4*6 Chưa xong: 5*GT(4) GT. 1st: N=5, Chưa xong: answer
  17.  1. Đệ quy (Recursion) Minh họa GT. 1st: N=5, xong: returns 5*24 Chưa xong: answer
  18.  1. Đệ quy (Recursion) Minh họa CT chính: xong: answer
  19.  1. Đệ quy (Recursion) Ví dụ 2: Tính bằng đệ quy  Dãy số Fibonaci: F1 = F2 = 1; Fn = Fn­1 + Fn­2.        (n ≥  3) int  Fibo(int  n) { if (n≤  2) // điểm dừng return 1; else  return Fibo(n­1)+Fibo(n­2); } 19 Chương 2: Hàm – Đệ quy
  20.  1. Đệ quy (Recursion) Nhận xét:  Thông thường thay vì sử dụng lời giải đệ quy cho một ◦ bài toán, ta có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng phương pháp lặp. Việc sử dụng giải thuật đệ quy có: ◦ Ưu điểm Khuyết điểm Thuận lợi cho việc không được Có khi biểu diễn bài toán tối ưu về thời gian Ngắn gọn Có thể gây tốn bộ nhớ ◦ Chính vì vậy, trong lập trình người ta cố tránh sử dụng thủ tục đệ quy nếu thấy không cần thiết. 20 Chương 3: Hàm – Đệ quy
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2