KỸ THUẬT LẬP TRÌNH (p7)

Chia sẻ: Nguyễn Văn Cường | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

169
lượt xem 38
download

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

Hàm và Thủ tục Phát triển chương trình bằng phương pháp tinh chỉnh dần từng bước. Định nghĩa và sử dụng hàm trong ngôn ngữ C Hàm đệ quy Sức mạnh của đệ quy là gì? Lời giải của bài toán T gọi là đệ quy nếu nó được thực hiện bằng lời giải của bài toán T’ có dạng giống T Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. Biểu diễn giải thuật đệ quy: trong chương trình cần có thủ tục hay chương trình con. ...

Chủ đề:

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

Lưu

Nội dung Text: KỸ THUẬT LẬP TRÌNH (p7)

KỸ THUẬT LẬP TRÌNH KHÁI NIỆM ĐỆ QUY Sức mạnh của đệ quy là gì? ? KỸ THUẬT PHÁT TRIỂN CHƯƠNG TRÌNH Lời giải của bài toán T gọi là đệ quy nếu nó được thực NỘI DUNG hiện bằng lời giải của bài toán T’ có dạng giống T Hàm và Thủ tục Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. Phát triển chương trình bằng phương pháp tinh Biểu diễn giải thuật đệ quy: trong chương trình cần có chỉnh dần từng bước. thủ tục hay chương trình con. Định nghĩa và sử dụng hàm trong ngôn ngữ C • Đệ quy trực tiếp: trong thủ tục P có chứa lời gọi đến chính nó Hàm đệ quy • Đệ quy gián tiếp: trong thủ tục P có lời gọi thủ tục Q và trong Q có lời gọi đến P. • Cần xác định tình huống, điều kiện để kết thúc đệ quy. 0 1 Ví dụ 1. Hàm tính giai thừa ? Bài toán nào có thể dùng đệ quy? Hàm đệ quy thường được viết theo thuật toán sau: • 5! = 5 * 4 * 3 * 2 * 1 if (trường hợp suy biến) { • Chú ý rằng: Lời giải bài toán trong trường hợp suy biến; – 5! = 5 * 4! } – 4! = 4 * 3! ... else { • Có thể thực hiện gọi đệ qui Gọi đệ quy tới hàm với giá trị khác của tham số; • Điều kiện kết thúc gọi đệ qui: 1! = 0! = 1 } – 2! = 2 * 1! = 2 * 1 = 2; – 3! = 3 * 2! = 3 * 2 = 6; 2 3
VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY Ví dụ 1. Hàm giai thừa Fin a l va lue = 120 5! 5! if n = 0 ⎧ 1, 5! = 5 * 24 = 120 is re turn ed Fac ( n) = ⎨ ⎩n * Fac ( n − 1), if n > 0 5 * 4! 5 * 4! 4! = 4 * 6 = 24 is re turne d 4 * 3! 4 * 3! 3! = 3 * 2 = 6 is re tu rn e d function Fac(i: integer): integer; 3 * 2! 3 * 2! 2! = 2 * 1 = 2 is re turne d begin 2 * 1! 2 * 1! if i
VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY 1, if n ≤ 2 ⎧ Ví dụ 2. Dãy số Fibonacci Fib(n) = ⎨ ⎩ Fib(n − 1) + Fib( n − 2), if n > 2 Bài toán: • Các con thỏ không bao giờ chết. function Fib(n: integer):integer; • Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp begin thỏ con (1 đực, 1 cái). if n = 0 then Fib := 0 else • Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp mới. if n = 1 then Fib := 1 else • Giả sử bắt đầu từ một cặp mới ra đời thì đến tháng thứ n sẽ có Fib := Fib(n−1) + Fib(n−2); bao nhiêu cặp? end; 8 9 1 /* Fig. 5.15: fig05_15.c 2 Recursive fibonacci function */ 3 #include 4 5 long fibonacci( long n ); /* function prototype */ 6 7 /* function main begins program execution */ Gọi function fibonacci 8 int main() 9 { f( 3 ) 10 long result; /* fibonacci value */ 11 long number; /* number input by user */ 12 13 /* obtain integer from user */ 14 printf( "Enter an integer: " ); return f( 2 ) + f( 1 ) 15 scanf( "%ld", &number ); 16 17 /* calculate fibonacci value for number input by user */ 18 result = fibonacci( number ); return f( 1 ) f( 0 ) return 1 + 19 20 /* display result */ 21 printf( "Fibonacci( %ld ) = %ld\n", number, result ); 22 return 1 return 0 23 return 0; /* indicates successful termination */ 24 25 } /* end main */ 26 10
27 /* Recursive definition of function fibonacci */ 28 long fibonacci( long n ) VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY 29 { 30 Program Output /* base case */ Program 31 if ( n == 0 || n == 1 ) { 32 return n; Ví dụ 3. Đường Hilbert 33 } /* end if */ 34 else { /* recursive step */ 35 return fibonacci( n - 1 ) + fibonacci( n - 2 ); • Đường Hilbert cấp 0 là hình rỗng. 36 } /* end else */ 37 • Đường Hilbert cấp i + 1 được thành lập từ 4 đường cấp i được 38 } /* end function fibonacci */ quay theo 1 góc thích hợp và nối với nhau bởi 3 đoạn thẳng. Enter an integer: 0 Fibonacci( 0 ) = 0 Enter an integer: 1 Fibonacci( 1 ) = 1 Enter an integer: 2 Fibonacci( 2 ) = 1 Enter an integer: 3 Fibonacci( 3 ) = 2 Enter an integer: 4 Fibonacci( 4 ) = 3 13 VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY x, y - biến toạ độ; h - độ dài của đoạn nối; plot - vẽ từ vị trí hiện tại xác định bởi x, y procedure A(i:integer); begin if i > 0 then begin B(i−1); x := x − h; plot; A(i−1); y := y − h; plot; A(i−1); x := x + h; plot; D(i−1); end; 14 15
VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY VÍ DỤ VỀ CHƯƠNG TRÌNH ĐỆ QUY procedure B(i:integer); procedure C(i:integer); procedure D(i:integer); Chương trình chính Begin read(n, x, y, h); D(n); end. 16 17 BÀI TOÁN THÁP HÀ NỘI BÀI TOÁN THÁP HÀ NỘI Trường hợp 1 đĩa: Chuyển đĩa từ cột A sang cột C Ví dụ 4. Có n đĩa, kích thước khác nhau, có lỗ ở giữa và ba cột kí hiệu là A, B, C. Đĩa có thể xếp chồng lên Trường hợp 2 đĩa: nhau, xuyên qua một cột để tạo thành hình tháp. Giả • Chuyển đĩa thứ nhất (tính từ đĩa trên cùng, hay đĩa nhỏ nhất) sử ban đầu n đĩa được đặt ở cột A theo thứ tự lớn dưới từ cột A sang cột B nhỏ trên. Cần dời các đĩa đến cột C nhưng vẫn phải • Chuyển đĩa thứ 2 từ cột A sang cột C giữ thứ tự cũ, với các ràng buộc sau: • Chuyển đĩa thứ nhất từ cột B sang cột C. − Mỗi lần chỉ chuyển một đĩa từ cột này sang cột khác Trường hợp n đĩa (n >2) − Đĩa lớn không được chồng lên đĩa nhỏ • Chuyển (n−1) đĩa từ cột A sang cột B − Được phép dùng cột B để làm trung gian • Chuyển đĩa thứ n từ cột A sang cột C • Chuyển (n − 1) đĩa từ cột B sang cột C 18 19
BÀI TOÁN THÁP HÀ NỘI BÀI TOÁN THÁP HÀ NỘI Procedure HanoiTower(n, A, B, C: byte) Các thuật toán “ Chia để trị” (Divide−and−Conquer) Begin • Để giải bài toán B với bộ dữ liệu S, ta chia s thành các bộ dữ liệu con S1, S2, …, Sk mà với bộ dữ liệu này, bài toán B giải 1. if n = 1 then Chuyển đĩa từ A sang C được bằng một thuật toán đơn giản. Sau đó tổ hợp lời giải của 2. else begin các bài toán trên bộ dữ liệu Si sẽ cho lời giải của bài toán B với bộ dữ liệu S. Call HanoiTower(n−1, A, C, B); • Thường sử dụng lời gọi đệ quy Call HanoiTower(1, A, B, C); Call HanoiTower(n − 1, B, A, C); end; 20 21 THUẬT TOÁN QUAY LUI KHI NÀO KHÔNG SỬ DỤNG ĐỆ QUY? Thuật ngữ: Backtracking [D.H. Lehmer, 1950] Thuật toán đệ quy Cải tiến từ thuật toán tìm kiếm thô function Fac(i: integer): integer; {lưu ý nên dùng số nguyên lớn} begin Tìm kiếm có hệ thống, theo chiều sâu, trên tập các phương án có thể. if i
KHI NÀO KHÔNG SỬ DỤNG ĐỆ QUY? Đệ qui và lặp: Thuật toán không đệ quy (Sử dụng vòng lặp) Lặp function Fac2(i: integer):integer; • Lặp: rõ ràng, kiểm soát trong quá trình chạy chương trình begin • Đệ qui: lặp lại lời gọi hàm i := 0; F := 1; Kết thúc while i < n do • Lặp: điều kiện lặp sai (false) begin • Đệ qui: nhận ra tình huống, điều kiện để kết thúc đệ qui i := i +1; Cả hai đều có thể lặp vô hạn F := F * i; Cân nhắc end; • Chọn giữa lặp và gọi đệ qui? end; 24 25 KHI NÀO KHÔNG SỬ DỤNG ĐỆ QUY? BÀI TẬP 1. Xây dựng các hàm số sau bằng phương pháp đệ quy: Đệ quy là tốt nhất? f(x,n) = xn , (n >=0) Khi nào nên dùng đệ quy s(n) = (2n)! Những mô hình bài toán nên tránh dùng đệ quy: 2. Viết chương trình sử dụng hàm đệ quy để tính UCLN P ≡ if B then S; P end; của hai số nguyên dương theo quy tắc sau: P ≡ S; if B then P end; hay • Nếu x= y thì UCLN(x, y) = x • Nếu x > y thì UCLN(x, y) = UCLN(x − y, y); • Nếu x < y thì UCLN(x, y) = UCLN(x, y −x); 26 27
BÀI TẬP 3. Viết chương trình sử dụng hàm đệ quy để vẽ đường Hilber cấp k (k nhập vào từ bàn phím) 4. Viết chương trình sử dụng đệ quy để giải bài toán Tháp Hà Nội 28