Trang ChínhTrang Chính  CalendarCalendar  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Hãy sử dụng FireFox để web hiển thị tốt hơn!


Share | 
 

 Tháp Hà Nội-(Đệ quy)

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Tboy
Cá voi
Cá voi
avatar


Nam Tổng số bài gửi : 178
Cảm ơn : 413
Danh vọng : 4
Join date : 03/01/2011
Age : 25
Đến từ : TPHCM

Bài gửiTiêu đề: Tháp Hà Nội-(Đệ quy)   Sat Jan 22, 2011 12:21 am

Sat Jan 22, 2011 12:21 am » Tháp Hà Nội-(Đệ quy)
Đề bài: Có 3 cột được đặt tên là A,B,C.Với n cái đĩa có kích thước khác nhau, lúc đầu được đặt ở cột A theo thứ tự đĩa lớn nằm dưới đĩa nhỏ nằm trên.Viết một hàm đệ quy mô tả các bước để chuyển các đĩa từ cột A sang cột C sao cho:
1.Mỗi bước chỉ được phép chuyển 1 đĩa.
2.Tại mỗi thời điểm trên các cột(A,B,C) đĩa nhỏ luôn nằm trên đĩa lớn.
3.Được phép sử dụng cột trung gian B trong quá trình chuyển đĩa.

Ta tìm tính đệ quy và cách giải:



Ta nhận thấy với N đĩa ở cột A:
Qui trình X:ta phải thực hiện cho các đĩa nhỏ hơn ở cột A sang cột B, cột A chỉ còn lại đĩa lớn nhất, rồi mới cho đĩa lớn nhất sang cột C
Qui trình Y: thực hiện tiếp cho các đĩa nhỏ hơn ở cột B sang cột A và cho đĩa lớn nhất ở cột B sang C.....
2 qui trình đều thực hiện với mục đích cho đĩa lớn nhất trong cột ở đầu qui trình sang cột C.
Tiếp tục 2 qui trình này đến khi hoàn thành.
Như vậy, ta có thể nhận thấy Qui trình X và Y tương đương nhau nhưng chỉ thay đổi vai trò của A và B, và kết thúc đều cho đĩa lớn nhất sang cột C.
Tức là thực hiện Qui trình X với các đĩa ở cột A, kết thúc Qui trình X, ta lại thực hiện lại Qui trình này nhưng với n-1 đĩa ở cột B, quá trình này kết thúc khi không còn đĩa nào tức n=0.
Ví dụ:
Ban đầu ta có n đĩa ở cột A

Thực hiện Qui trình X

Ta lại thực hiện Qui trình X với n-1 đĩa còn lại...

Ở đây,đổi lại vị trí cột A<->B để bạn thấy rõ vai trò tương đương của 2 cột A,B khi thực hiện lặp lại qui trình X.













Kết quả

Ta có code sơ khởi như sau:
Code:
#include <stdio.h>
#include <conio.h>
void ThapHN(int N,char A,char B,char C);
void main()
{
   int n;
   do
   {
      printf("Nhap vao so dia: ");
      scanf("%d",&n);
   }while(n<1);
   ThapHN(n,'A','B','C');
   getch();
}
void ThapHN(int N,char A,char B,char C)
{
   if(N==0)
      return;
   ......................................
   printf("Chuyen tu %c sang %c\n",A,C);
   ThapHN(N-1,B,A,C);
}
Đến đây ta lại làm rõ việc thực hiện trong Qui trình X, chính xác là việc làm thế nào cho các đĩa nhỏ hơn sang cột A hoặc B, gọi nó là việc K.
Ta biết kết quả của Quá trình X là số đĩa ở cột A sang cột C.Bây giờ ta lại thực hiện việc K bằng cách thực hiện Qui trình X nhưng với mục đích chuyển n-1 đĩa sang B.
Mình sẽ phân tích kỹ hơn cách thực hiện việc K bằng cách lặp lại suy luận phía trên để bạn có thề nhận ra tính đệ quy:
Ta nhận thấy với N-1 đĩa(chính là số đĩa khi thực hiện việc K):
Qui trình T:ta phải thực hiện cho các đĩa nhỏ hơn ở cột A sang cột C, cột A chỉ còn lại đĩa lớn nhất, rồi mới cho đĩa lớn nhất sang cột B
Qui trình Z: thực hiện tiếp cho các đĩa nhỏ hơn ở cột C sang cột A và cho đĩa lớn nhất ở cột C sang B.....
Tiếp tục như thế cho đến khi n=0 và bạn lại thấy Qui trình T,Z tương đương và cuối cùng qui về nó chính là Qui trình X ban đầu nhưng có sự thay đổi trong mục đích xếp đĩa và với số đĩa là n-1.












Kết quả


Hoàn thiện code:
Code:
#include <stdio.h>
#include <conio.h>
void ThapHN(int N,char A,char B,char C);
void main()
{
   int n;
   do
   {
      printf("Nhap vao so dia: ");
      scanf("%d",&n);
   }while(n<1);
   ThapHN(n,'A','B','C');
   getch();
}
void ThapHN(int N,char A,char B,char C)
{
   if(N==0)
      return;
   ThapHN(N-1,A,C,B);
   printf("Chuyen tu %c sang %c\n",A,C);
   ThapHN(N-1,B,A,C);
}

Hoặc viết:
Code:
void ThapHN(int N,char A,char B,char C)
{
   if(N>0)
   {
      ThapHN(N-1,A,C,B);
      printf("Chuyen tu %c sang %c\n",A,C);
      ThapHN(N-1,B,A,C);
   }
}

Bạn có thể vào [You must be registered and logged in to see this link.] để chơi trò này.

[You must be registered and logged in to see this link.]


Tboy

Về Đầu Trang Go down
Xem lý lịch thành viên http://taplaptrinh.forumvi.com
 

Tháp Hà Nội-(Đệ quy)

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
 :: Cơ sở lập trình 1 :: Bài tập thực hành-