Hỏi đáp

Khái Niệm Đệ Quy Là Gì Và Lúc Nào Tôi Nên Sử Dụng Nó? Đệ Quy Là Gì – viettingame

Contents

InstallShield12,2009,2010IIS6.0,7.0 ConfigJavascriptASP.NETC#, Cshap, VB.NETCấu trúc dữ liệu và giảithuật

Menu

1. Đệ quy là gì ?

Một đối tượng người sử dụng được gọi là đệ quy nếu nó được mô tả trải qua định nghĩa của nó. Nghĩa là, những đối tượng người sử dụng này được định nghĩa một cách quy nạp từ những luận điểm giản dị nhất cùng dạng với nó. Trong toán học và tin học với rất nhiều đối tượng người sử dụng như vậy. VD :

– Số tự nhiên được định nghĩa như sau :

0 là một số trong những tự nhiênNếu k là một số trong những tự nhiên thì k+1 cũng là một số trong những tự nhiên

Theo đó, ta sẽ sở hữu : 1=0+một là số tự nhiên, 2=1+1 cũng là một số trong những tự nhiên,….Cứ như vậy ta sẽ định nghĩa được những số tự nhiên khác to hơn. Do đó, số tự nhiên là luận điểm mang thực chất đệ quy.

Đang xem: đệ quy là gì và một khi tôi nên sử dụng nó?

– Định nghĩa giai thừa của n (n!) :

Lúc n=0, ta với 0!=1Khi nvàgt;0, ta với n!=(n-1)! x n

Như vậy, ta suy ra : 1! = 0! x 1, 2! = 1! x 2,… –> giai thừa cũng là một luận điểm mang ý nghĩa đệ quy.

2. Bài toán đệ quy

Này là những bài toán mang thực chất đệ quy. Nghĩa là những bài toán này mà thậm chí được phân rã thành những bài toán nhỏ hơn, giản dị hơn nhưng với cùng dạng với bài toán thuở đầu. Những bài toán nhỏ lại được phân rã thành những bài toán nhỏ hơn. Cứ như vậy, việc phân rã chỉ tạm dừng lúc bài toán con giản dị tới mức mà thậm chí suy ra ngay thành quả mà không nhất thiết phải phân rã nữa. Ta phải giải toàn bộ những bài toán con rồi phối kết hợp những thành quả này lại để sở hữu được lời giải cho bài toán to thuở đầu. Cách phân rã bài toán như vậy gọi là “chia để trị” (devide and conquer), là một dạng của đệ quy.

3. Đệ quy trong lập trình

Một hàm được gọi là đệ quy nếu bên trong thân nó với một lời gọi tới chính nó. Nghe với vẻ vô lý nhỉ ? Một hàm làm sao mà thậm chí gọi nó mãi được, vì thế nếu như vậy sẽ sinh ra một vòng lặp vô tận. Tuy nhiên trong thực tiễn, một hàm đệ quy luôn luôn với ĐK đừng được gọi là “điểm neo”. Lúc đạt tới điểm neo, hàm sẽ không còn gọi chính nó nữa.

Lúc được gọi, hàm đệ quy thường được truyền cho một tham số, thông thường là kích thước của bài toán to thuở đầu. Sau mỗi lời gọi đệ quy, tham số sẽ nhỏ dần, nhằm mục đích phản ánh bài toán đã nhỏ hơn và giản dị hơn. Lúc tham số đạt tới một giá trị cực tiểu (tại điểm neo), hàm sẽ ngừng.

Trong lập trình, một bài toán muốn xử lý bằng đệ quy thì bạn dạng thân nó phải là một bài toán đệ quy. Tức là bài toán đó mà thậm chí được đưa về bài toán cùng dạng nhưng giản dị hơn.

4. Một trong những bài toán đệ quy kinh điển

a. Bài toán tính giai thừa

Cho n là một số trong những tự nhiên (nvàgt;=0). Hãy tính giai thừa của n (n!) biết rằng 0!=1 và n!=(n-1)! x n.

Phân tích :

– Theo giả thiết, ta với : n! = (n-1)! x n. Như vậy :

Để tính n! ta cần phải tính (n-1)!Để tính (n-1)! ta phải tính (n-2)!…

– Cứ như vậy, cho tới lúc gặp gỡ trường hợp 0!. Lúc đó ta lập tức với được thành quả là 1 trong những, không nhất thiết phải tính trải qua một thành quả trung gian khác.

Thiết lập trên C# :

Code

– Ở trên đây, điểm neo đó là n=0. Sau mỗi lời gọi đệ quy, n sẽ tránh xuống 1 cho tới lúc gặp gỡ điểm neo.

b. Dãy Fibonaci

Dãy Fibonaci là dãy vô hạn những số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau :

F(n) = 1, nếu n=1 hoặc n=2F(n) = F(n-1) + F(n-2), nếu nvàgt;=3

Yêu cầu : tính số fibonaci thứ n với n cho trước.

Xem thêm: Welcome To Avatar Tự động Carriers Llc Usdot 3202823, Avatar Tự động Care Centre Company Profile

Phân tích : theo giả thiết

– Với n

– Với nvàgt;=3 :

Đế tính F(n) ta phải tính F(n-1) và F(n-2).Để tính F(n-1) ta lại phải tính F(n-2) và F(n-3), và để tính F(n-2) ta phải tính F(n-3) và F(n-4).…Cứ như vậy cho tới lúc n=1 và n=2.

Thiết lập trên C# :

Code

– Dưới trên đây là sơ đồ đệ quy lúc gọi hàm tính F(5) :

*

Như vậy, bài toán đã được xử lý một cách thật giản dị bằng đệ quy.

c. Bài toán “Tháp thủ đô” (Tower of Ha Noi)

Phía trên là một bài toán rất nổi tiếng và kinh điển, rất thích hợp để minh họa cho thuật toán đệ quy. Sau trên đây là nội dung bài toán :

Với 3 chiếc cọc được ghi lại lần lượt là A, B, C và n chiếc đĩa. Những đĩa này còn có kích thước không giống nhau và mỗi đĩa đều phải sở hữu một lỗ ở giữa để cắm vào cọc. Lúc đầu, những đĩa đều nằm tại cọc A, trong đó, đĩa nhỏ luôn luôn nằm trên đĩa to hơn.

*

Yêu cầu : chuyển n đĩa từ cọc A lịch sự cọc đích C với những ĐK sau :

+ Mỗi lần chỉ chuyển được 1 đĩa

+ Trong quy trình chuyển, đĩa nhỏ phải luôn luôn nằm trên đĩa to hơn.

+ Cho phép sử dụng cọc B làm cọc trung gian

Phân tích : ta sẽ xét những trường hợp của n

– Trường hợp giản dị nhất, n=1, ta chỉ việc chuyển 1 đĩa từ cọc A lịch sự cọc C.

– Nhiều hơn thế nữa một chút, n=2, ta chuyển đĩa nhỏ nhất lịch sự cọc B, chuyển đĩa sót lại lịch sự cọc C, và sau cùng chuyển đĩa nhỏ ở cọc B lịch sự cọc C.

– Lúc này ta xét n đĩa (nvàgt;2). Giả sử ta đã với cách chuyển n-1 đĩa từ một cọc lịch sự một cọc khác. Như vậy, để chuyển n đĩa từ cọc nguồn lịch sự cọc đích, ta cần chuyển n-1 đĩa từ cọc nguồn lịch sự cọc trung gian. Sau đó chuyển đĩa to nhất từ cọc nguồn lịch sự cọc đích. Sau cuối, chuyển n-1 từ cọc trung gian về cọc đích.

Thiết lập bằng C# :

Code

public static void ThapHaNoi(int n, char nguon, char dich, char tgian){ //điểm neo if (n == 1) Console.WriteLine(“Chuyen 1 dia tu {0} lịch sự {1}”, nguon, dich); else { //chuyển n-1 đĩa từ cọc nguồn lịch sự cọc trung gian, //lấy cọc đích làm cọc phụ ThapHaNoi(n – 1, nguon, tgian, dich); //chuyển sót lại từ cọc nguồn lịch sự cọc đích Console.WriteLine(“Chuyen 1 dia tu {0} lịch sự {1}”, nguon, dich); //chuyễn n-1 từ cọc trung gian về cọc đích, //lấy cọc nguồn làm cọc trung gian ThapHaNoi(n – 1, tgian, dich, nguon); }}

Hàm trên với trách nhiệm chuyển n đĩa từ cột nguon lịch sự cọc dich, sử dụng cọc tgian làm cọc phụ. Ở trên đây ta ký hiệu những cột là A, B, C nên ta sẽ sử dụng kiểu char.

Xem thêm: Nhân Mã Sinh Ngày 2 Tháng 12 Là Cung Gì ? Nhân Mã Sinh Ngày 2 Tháng 12

Như vậy, ta đã tìm hiểu xong những điểm cơ bạn dạng về đệ quy. Trên trên đây chỉ là những bài toán đệ quy giản dị. Còn rất nhiều bài toán và kỹ thuật khác sử dụng phương pháp đệ quy.

Về Viettingame.com

Viettingame.com - Chuyên trang web tổng hợp những thông tin hữu ích trên internet như thông tin về game, tin tổng hợp
Xem tất cả các bài viết của Viettingame.com →

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *