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

Bài giảng Kỹ thuật lập trình đệ quy

Chia sẻ: 5A4F5AFSDG 5A4F5AFSDG | Ngày: | Loại File: PDF | Số trang:57

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

Bài giảng Kỹ thuật lập trình đệ quy gồm có những nội dung chính sau: Giới thiệu về lập trình đệ quy, phân loại các dạng đệ quy, hoạt động của đệ quy, xây dựng giải thuật đệ quy, các giải thuật đệ quy tiêu biểu, các giải pháp thay thế cho đệ quy. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình đệ quy

  1. 5/4/2016 1
  2. Nội dung Giới thiệu về lập trình đệ quy Phân loại các dạng đệ quy Hoạt động của đệ quy Xây dựng giải thuật đệ quy Các giải thuật đệ quy tiêu biểu Các giải pháp thay thế cho đệ quy Tóm tắt chương 5/4/2016 2
  3. [3.1] Giới thiệu về lập trình đệ quy Khi lập trình, gặp dạng bài toán: đối tượng khó định nghĩa một cách tường minh. Kỹ thuật định nghĩa đối tượng qua chính nó: kỹ thuật đệ quy (recursion). Ví dụ: 2 chiếc gương đối diện nhau. Chiếc thứ nhất chứa hình chiếc thứ hai và ngược lại. Ta hình dung ra dãy các ảnh vô hạn của hai chiếc gương. Ví dụ: trên truyền hình, biên tập viên ngồi kế bên màn hình của chương trình đang phát, có dãy hình ảnh lập đi lập lại nhưng nhỏ dần.. 5/4/2016 3
  4. [3.1] Giới thiệu về lập trình đệ quy Đệ quy được sử dụng rộng rãi trong khoa học máy tính và lý thuyết tính toán. Định nghĩa theo đệ quy của một khái niệm là định nghĩa khái niệm mới thông qua chính khái niệm đang muốn định nghĩa. Ví dụ: về các định nghĩa đệ quy như sau: Giai thừa của n (n!):  Nếu n=0 hoặc n=1 thì n!=1.  Nếu n>1 thì n!=(n-1)! * n 5/4/2016 4
  5. [3.1] Giới thiệu về lập trình đệ quy Ký hiệu số phần tử của một hữu hạn S là |S|: Nếu S= thì |S| = 0. Nếu S≠ thì chắc chắn có một phần tử xS, khi đó |S|=|S\{x}|+1. Đây là phương pháp định nghĩa tập hợp. Tập số tự nhiên: Số 1 là số tự nhiên (1N). Số tự nhiên bằng số tự nhiên cộng 1 (nN  (n+1)N). 5/4/2016 5
  6. [3.1] Giới thiệu về lập trình đệ quy Cấu trúc danh sách liên kết (linklist/xâu) kiểu T: Cấu trúc rỗng là danh sách liên kết kiểu T. Kết nối một thành phần kiểu T (nút kiểu T) vào một danh sách liên kết kiểu T, ta có một danh sách liên kết kiểu T. 5/4/2016 6
  7. [3.1] Giới thiệu về lập trình đệ quy Ví dụ trên, để định nghĩa đệ quy gồm 2 phần: Phần cố định (cơ sở - neo – anchor): các trường hợp suy biến (trường hợp đặc biệt) của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy – chương trình phải có tính dừng). Phần đệ quy (quy nạp): mô tả thuật toán trong trường hợp phổ biến qua chính đối tượng (gọi hàm đệ quy) một cách gián tiếp hay trực tiếp. Lưu ý: phần đệ quy phải tiến về phần không đệ quy. 5/4/2016 7
  8. [3.2] Phân loại đệ quy Đệ quy tuyến tính. Đệ quy nhị phân. Đệ quy phi tuyến. Đệ quy hỗ tương. 5/4/2016 8
  9. Đệ quy tuyến tính Bước 1: Nếu thỏa điều kiện dừng thì thực hiện thao tác S (trả về kết quả) Bước 2: Ngược lại: Bước 2.1 thực hiện lệnh S* Bước 2.2 Gọi hàm đệ quy (cho đối tượng thường là nhỏ hơn) S, S*: xử lý không đệ quy. Có thể gộp bước 2.1 và 2.2 lại. 5/4/2016 9
  10. Đệ quy tuyến tính Hàm tính giai thừa (n!) Bước 1: Nếu n=0 hoặc n=1 thì trả về 1 Bước 2: Ngược lại: trả về n*Giai_thừa(n-1) 5/4/2016 10
  11. Đệ quy tuyến tính Cài đặt: int giaiThua(int n) { if (n == 1 || n == 0) return 1; return giaiThua(n - 1) * n; } 5/4/2016 11
  12. Đệ quy tuyến tính Uớc chung lớn nhất của 2 số dựa vào thuật toán Euclide: Bước 1: Nếu n=0 thì trả về m Bước 2: Ngược lại: trả về USCLN(n, m mod n) 5/4/2016 12
  13. Đệ quy tuyến tính Cài đặt: int UCLN(int m, int n) { if (n == 0) return m; return uCLN(n, m% n); } 5/4/2016 13
  14. Đệ quy tuyến tính Tính tổng giá trị của dãy số nguyên Bước 1: Nếu n=1 thì trả về a[n-1] Bước 2: Ngược lại: trả về a[n-1]+tongDay(a,n-1) 5/4/2016 14
  15. Đệ quy tuyến tính Cài đặt: int tongDay(int []a, int n) { if (n == 1) return a[n-1]; return a[n-1]+tongDay(a, n-1); } 5/4/2016 15
  16. Đệ quy tuyến tính Liệt kê các giá trị lẻ của dãy số nguyên Bước 1: Nếu n=0 thì dừng Bước 2: Ngược lại: Bước 2.1 Nếu a[n-1] lẻ xuất A[n-1] Bước 2.2 gọi hàm lietKeLe(a, n-1) 5/4/2016 16
  17. Đệ quy tuyến tính Cài đặt: void lietKeLe(int[] a, int n) { if (n == 0) return ; if (a[n - 1] % 2 != 0) printf(“%d\t”,a[n - 1]); lietKeLe(a, n - 1); } 5/4/2016 17
  18. Đệ quy tuyến tính Kết quả xuất ra ngược với dãy ban đầu nhập vào. Xuất xuôi lại ta làm như sau: Bước 1: Nếu n=0 thì dừng Bước 2: Ngược lại: Bước 2.1 gọi hàm lietKeLe(a, n-1) Bước 2.2 Nếu a[n-1] lẻ xuất A[n-1] 5/4/2016 18
  19. Đệ quy tuyến tính Cài đặt: void lietKeLe(int[] a, int n) { if (n == 0) return ; lietKeLe(a, n - 1); if (a[n - 1] % 2 != 0) printf(“%d\t", a[n - 1]); } 5/4/2016 19
  20. Đệ quy tuyến tính Đối với hàm đệ quy không có trị trả về (void), ta có thể viết theo dạng sau Bước 1: Nếu chưa dừng (n>0) thì: Bước 1.1 gọi hàm lietKeLe(a, n-1) Bước 1.2 Nếu a[n-1] lẻ xuất A[n-1] 5/4/2016 20
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
3=>0