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: Chương 3 - Trần Minh Thái, Phạm Đức Thành

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PPTX | Số trang:107

Thêm vào BST
Báo xấu
89
lượt xem 8
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 - Chương 3: Kỹ thuật lập trình đệ quy" trình bày các 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. 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: Chương 3 - Trần Minh Thái, Phạm Đức Thành

  1. KỸ THUẬT LẬP TRÌNH Chương 3 Kỹ thuật lập trình đệ quy TRẦN MINH THÁI – minhthai@huflit.edu.vn, www.minhthai.edu.vn  PHẠM ĐỨC THÀNH –  phamducthanh@huflit.edu.vn, www.phamthao.com  9/17/16 Trần Minh Thái - Phạm Đức Thành 1
  2. Nội dung v 3.1. Giới thiệu về lập trình đệ quy v 3.2. Phân loại các dạng đệ quy v 3.3. Hoạt động của đệ quy v 3.5. Xây dựng giải thuật đệ quy v 3.6. Các giải thuật đệ quy tiêu biểu v 3.7. Các giải pháp thay thế cho đệ quy v 3.8. Tóm tắt chương 9/17/16 Trần Minh Thái - Phạm Đức Thành 2
  3. [3.1] Giới thiệu về lập trình v đệ 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 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 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.. 9/17/16 Trần Minh Thái - Phạm Đức Thành 3
  4. [3.1] Giới thiệu về lập trình v Đệ đệ 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. v Đị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 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 9/17/16 Trần Minh Thái - Phạm Đức Thành 4
  5. [3.1] Giới thiệu về lập trình đệ quy v 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. v 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). 9/17/16 Trần Minh Thái - Phạm Đức Thành 5
  6. [3.1] Giới thiệu về lập trình đệ quy v 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. 9/17/16 Trần Minh Thái - Phạm Đức Thành 6
  7. [3.1] Giới thiệu về lập trình đệ quy v 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. v Lưu ý: phần đệ quy phải tiến về phần không 9/17/16 Trần Minh Thái - Phạm Đức Thành 7
  8. [3.2] Phân loại đệ quy v Đệ quy tuyến tính v Đệ quy nhị phân v Đệ quy phi tuyến v Đệ quy hỗ tương 9/17/16 Trần Minh Thái - Phạm Đức Thành 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) v S, S*: xử lý không đệ quy. Có thể gộp bước 2.1 và 2.2 lại. 9/17/16 Trần Minh Thái - Phạm Đức Thành 9
  10. Đệ quy tuyến tính Viết hàm tính giai thừa của n bằng cách dùng vòng lặp static int GiaiThua(int n) { ??? } 9/17/16 Trần Minh Thái - Phạm Đức Thành 10
  11. Đệ quy tuyến tính v 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) 9/17/16 Trần Minh Thái - Phạm Đức Thành 11
  12. Đệ quy tuyến tính v Cài đặt: static int giaiThua(int n) { if (n == 1 || n == 0) return 1; return giaiThua(n - 1) * n; } 9/17/16 Trần Minh Thái - Phạm Đức Thành 12
  13. Đệ quy tuyến tính Bài tập: Cho n là số nguyên dương, hãy viết hàm tính các tổng sau bằng phương pháp đệ quy: 2 2 2 2 S ( n) 1 2 3  n 1 1 1 S ( n) 1  2 3 n 9/17/16 Trần Minh Thái - Phạm Đức Thành 13
  14. Đệ quy tuyến tính Viết hàm tìm ước số chung lớn nhất của 2 số nguyên dương m và n bằng cách sử dụng vòng lặp static int UCLN (int m, int n) { ??? } 9/17/16 Trần Minh Thái - Phạm Đức Thành 14
  15. Đệ quy tuyến tính v 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) 9/17/16 Trần Minh Thái - Phạm Đức Thành 15
  16. Đệ quy tuyến tính v Cài đặt: static int uCLN(int m, int n) { if (n == 0) return m; return uCLN(n, m% n); } 9/17/16 Trần Minh Thái - Phạm Đức Thành 16
  17. Đệ quy tuyến tính Viết hàm xuất các phần tử lẻ trong mảng một chiều số nguyên bằng cách sử dụng vòng lặp static void XuatLe (int []a) { ??? } 9/17/16 Trần Minh Thái - Phạm Đức Thành 17
  18. Đệ quy tuyến tính v 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) 9/17/16 Trần Minh Thái - Phạm Đức Thành 18
  19. Đệ quy tuyến tính v Cài đặt: static void lietKeLe(int[] a, int n) { if (n == 0) return ; if (a[n - 1] % 2 != 0) Console.Write("{0,4}", a[n - 1]); lietKeLe(a, n - 1); } 9/17/16 Trần Minh Thái - Phạm Đức Thành 19
  20. Đệ quy tuyến tính v Kết quả xuất ra ngược với dãy ban đầu nhập vào. v 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] 9/17/16 Trần Minh Thái - Phạm Đức Thành 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
2=>2