Đề 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.