ปัญหาหอคอยแห่งฮานอย

หอคอยฮานอยเป็นปัญหาปริศนา ที่ที่เรามีสามยืนและ n แผ่น เริ่มแรก ดิสก์จะวางอยู่ในสแตนด์แรก เราต้องวางแผ่นดิสก์ลงในแท่นวางที่สามหรือปลายทาง แท่นรองหรือแท่นเสริมสามารถใช้เป็นขาตั้งผู้ช่วยได้

• แต่มีกฎบางอย่างที่ต้องปฏิบัติตาม
• เราโอนได้เพียงแผ่นเดียวต่อการเคลื่อนไหวแต่ละครั้ง
• หยิบแผ่นบนสุดได้จากขาตั้งเท่านั้น
• ไม่มีดิสก์ที่ใหญ่กว่าจะถูกวางที่ด้านบนของดิสก์ที่เล็กกว่า

ปัญหานี้สามารถแก้ไขได้ง่ายด้วยการเรียกซ้ำ ในตอนแรก ใช้การเรียกซ้ำ แผ่นดิสก์ด้านบน (n-1) จะถูกวางจากแหล่งกำเนิดไปยังแท่นเสริม จากนั้นจึงวางแผ่นดิสก์แผ่นสุดท้ายจากต้นทางไปยังปลายทาง จากนั้นจึงวางแผ่นดิสก์ (n-1) จากแท่นเสริมไปยังแท่นรองปลายทางโดยการเรียกซ้ำ

อินพุตและเอาต์พุต

Input:
Number of discs: 3
Output:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

อัลกอริทึม

toh(n, s, a, d)

ป้อนข้อมูล: จำนวนดิสก์ ต้นทาง เสริม ปลายทาง

ผลลัพธ์: ขั้นตอนในการย้ายแผ่นดิสก์จากต้นทางไปยังปลายทางโดยรักษากฎเกณฑ์ที่เหมาะสม

Begin
   if n = 1, then
      display move disc from s to d
   toh(n-1, s, d, a)

   display move disc from s to d
   toh(n-1, a, s, d)
End

ตัวอย่าง

#include<iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
   static int count = 0;          //store number of counts
   if(n == 1) {
      count++;
      cout << count<< ". Move disk " << n << " from "<<s <<" to "<<d<<endl;
      return;      //base case, when only one disk
   }

   TOH(n-1, s, d, a);               //recursive call the function
   count++;
   cout << count<< ". Move disk " << n << " from "<<s <<" to"<<d<<endl;
   TOH(n-1, a, s, d);
}

int main() {
   int n;
   cout << "Enter the number of disks: ";
   cin >> n;
   TOH(n, 'A','B','C');
}

ผลลัพธ์

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C