Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.



 
Trang ChínhTrang Chính  Tìm kiếmTìm kiếm  Latest imagesLatest images  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

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
Tboy


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

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

Tháp Hà Nội-(Đệ quy) Titleb10 Sat Jan 22, 2011 12:21 am » Tháp Hà Nội-(Đệ quy) Tháp Hà Nội-(Đệ quy) Titleb13
Đề 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:
Tháp Hà Nội-(Đệ quy) Tower_of_Hanoi

Tháp Hà Nội-(Đệ quy) Tower_of_Hanoi_4
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áp Hà Nội-(Đệ quy) 180772_128903103843604_100001717462646_198234_5701385_n
Thực hiện Qui trình X
Tháp Hà Nội-(Đệ quy) 164755_128904097176838_100001717462646_198245_1708740_n
Ta lại thực hiện Qui trình X với n-1 đĩa còn lại...
Tháp Hà Nội-(Đệ quy) 180384_128906790509902_100001717462646_198249_2304414_n
Ở đâ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.
Tháp Hà Nội-(Đệ quy) 179032_128906817176566_100001717462646_198250_1222772_n

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

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

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

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

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

Tháp Hà Nội-(Đệ quy) 167718_128909190509662_100001717462646_198271_2788638_n
Kết quả
Tháp Hà Nội-(Đệ quy) 163207_128909120509669_100001717462646_198266_7129141_n
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.

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

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

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

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

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

Tháp Hà Nội-(Đệ quy) 164834_128914733842441_100001717462646_198308_7188927_n
Kết quả
Tháp Hà Nội-(Đệ quy) 167031_128903127176935_100001717462646_198235_1775697_n

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.



Tboy

Tháp Hà Nội-(Đệ quy) Border10 Tháp Hà Nội-(Đệ quy) Border14
Về Đầu Trang Go down
https://taplaptrinh.forumvi.com
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 

 Similar topics

-
» Thập phân sang nhị phân-(Đệ quy)
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-