Tác giả phạm hồng thái bài giảng ngôn ngữ LẬp trình c/C++



tải về 1.98 Mb.
trang28/55
Chuyển đổi dữ liệu07.07.2016
Kích1.98 Mb.
1   ...   24   25   26   27   28   29   30   31   ...   55

Lớp các bài toán giải được bằng đệ qui


Phương pháp đệ qui thường được dùng để giải các bài toán có đặc điểm:

Giải quyết được dễ dàng trong các trường hợp riêng gọi là trường hợp suy biến hay cơ sở, trong trường hợp này hàm được tính bình thường mà không cần gọi lại chính nó,

Đối với trường hợp tổng quát, bài toán có thể giải được bằng bài toán cùng dạng nhưng với tham đối khác có kích thước nhỏ hơn tham đối ban đầu. Và sau một số bước hữu hạn biến đổi cùng dạng, bài toán đưa được về trường hợp suy biến.

Như vậy trong trường hợp tính n! nếu n = 0 hàm cho ngay giá trị 1 mà không cần phải gọi lại chính nó, đây chính là trường hợp suy biến. Trường hợp n > 0 hàm sẽ gọi lại chính nó nhưng với n giảm 1 đơn vị. Việc gọi này được lặp lại cho đến khi n = 0.

Một lớp rất rộng của bài toán dạng này là các bài toán có thể định nghĩa được dưới dạng đệ qui như các bài toán lặp với số bước hữu hạn biết trước, các bài toán UCLN, tháp Hà Nội, ...

Cấu trúc chung của hàm đệ qui


Dạng thức chung của một chương trình đệ qui thường như sau:

if (trường hợp suy biến)

{

trình bày cách giải // giả định đã có cách giải

}

else // trường hợp tổng quát

{

gọi lại hàm với tham đối "bé" hơn

}

Các ví dụ


: Tìm UCLN của 2 số a, b. Bài toán có thể được định nghĩa dưới dạng đệ qui như sau:

nếu a = b thì UCLN = a

nếu a > b thì UCLN(a, b) = UCLN(a-b, b)

nếu a < b thì UCLN(a, b) = UCLN(a, b-a)

Từ đó ta có chương trình đệ qui để tính UCLN của a và b như sau.

int UCLN(int a, int b) // qui uoc a, b > 0

{

if (a < b) UCLN(a, b-a);



if (a == b) return a;

if (a > b) UCLN(a-b, b);

}

: Tính số hạng thứ n của dãy Fibonaci là dãy f(n) được định nghĩa:



f(0) = f(1) = 1

f(n) = f(n-1) + f(n-2) với "n ³ 2.


long Fib(int n)

{

long kq;



if (n==0 || n==1) kq = 1; else kq = Fib(n-1) + Fib(n-2);

return kq;

}
: Chuyển tháp là bài toán cổ nổi tiếng, nội dung như sau: Cho một tháp n tầng, đang xếp tại vị trí 1. Yêu cầu bài toán là hãy chuyển toàn bộ tháp sang vị trí 2 (cho phép sử dụng vị trí trung gian 3) theo các điều kiện sau đây

mỗi lần chỉ được chuyển một tầng trên cùng của tháp,

tại bất kỳ thời điểm tại cả 3 vị trí các tầng tháp lớn hơn phải nằm dưới các tầng tháp nhỏ hơn.

Bài toán chuyển tháp được minh hoạ bởi hình vẽ dưới đây.






















trước khi chuyển





































sau khi chuyển


























































































































































































































































































































































































































































1
















2
















3













1
















2
















3









Bài toán có thể được đặt ra tổng quát hơn như sau: chuyển tháp từ vị trí di đến vị trí den, trong đó di, den là các tham số có thể lấy giá trị là 1, 2, 3 thể hiện cho 3 vị trí. Đối với 2 vị trí di và den, dễ thấy vị trí trung gian (vị trí còn lại) sẽ là vị trí 6-di-den (vì di+den+tg = 1+2+3 = 6). Từ đó để chuyển tháp từ vị trí di đến vị trí den, ta có thể xây dựng một cách chuyển đệ qui như sau:

chuyển 1 tầng từ di sang tg,

chuyển n-1 tầng còn lại từ di sang den,

chuyển trả tầng tại vị trí tg về lại vị trí den

hiển nhiên nếu số tầng là 1 thì ta chỉ phải thực hiện một phép chuyển từ di sang den.

Mỗi lần chuyển 1 tầng từ vị trí i đến j ta kí hiệu i ® j. Chương trình sẽ nhập vào input là số tầng và in ra các bước chuyển theo kí hiệu trên.

Từ đó ta có thể xây dựng hàm đệ qui sau đây ;

void chuyen(int n, int di, int den) // n: số tầng, di, den: vị trí đi, đến

{

if (n==1) cout << di << " ® " << den << endl;



else {

cout << di << "®" << 6-di-den << endl; // 1 tầng từ di qua trung gian

chuyen(n-1, di, den) ; // n-1 tầng từ di qua den

cout << 6-di-den << "®" den << endl; // 1 tầng từ tg về lại den

}

}
main()



{

int sotang ;

cout << "Số tầng = " ; cin >> sotang;

chuyen(sotang, 1, 2);

}

Ví dụ nếu số tầng bằng 3 thì chương trình in ra kết quả là dãy các phép chuyển sau đây:



1 ® 2 , 1 ® 3 , 2 ® 3 , 1 ® 2 , 3 ® 1 , 3 ® 2 , 1 ® 2.

có thể tính được số lần chuyển là 2n - 1 với n là số tầng.


1   ...   24   25   26   27   28   29   30   31   ...   55


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương