hanoi

برج هانوی , معمایی است که از سه میله و N دیسک با اندازه های متفاوت تشکیل می شود .اگر فرض شود که  دیسکی روی یک میله باشد , فقط دیسکی که قطر آن کوچکتر است می تواند بالای آن قرار گیرد مسئله چنین است که هر بار فقط یک دیسک انتقال یابد . این مسئله با استفاده از یک الگوریتم باز گشتی حل می شود. این معما در درسهایی همچون ساختمان گسسته و ساختمان داده مورد بحث و بررسی قرار می گیرد . این برنامه همچنین یکی از سوال های کتاب دیتل نیز هست .

الگوریتم :
اگر فقط یک دیسک باشد آنگاه آن را به میله مورد نظر انتقال می دهیم. اگر n > 1 باشد ; برای این کار n-1 دیسک بالای میله 1 را به میله 2 انتقال می دهیم . حالا دیسک پایینی میله 1 را ثابت باقی می ماند . حال دیسک باقیمانده در میله 1 را به میله 3 منتقل میکنیم . سرانجام بار دیگر بصورت بازگشتی الگوریتم را فرا خوانده تا n - 1 دیسک میله دو را به 3 منتقل کند . اکنون موفق شدیم n دیسک را از میله 1 به 3 منقل کنیم . 

/* hanoi.cpp solves the Towers of Hanoi puzzle

 recursively. 
 * 
 * Input:  numDisks, the number of disks to be moved 
 * Output: a sequence of moves that solve the puzzle */ 

#include <iostream.h> 
#include <conio.h> 


void Move(int n, char source, char destination, char spare); 
int count = 0; 

int main() 
{ 
  const char PEG1 = 'A',            // the three pegs 
             PEG2 = 'B', 
             PEG3 = 'C'; 

  cout << "This program solves the Hanoi Towers puzzle. "; 

  cout << "Enter the number of disks: "; 
  int numDisks;                     // the number of disks to be moved 
  cin >> numDisks; 
  cout << endl; 

  Move(numDisks, PEG1, PEG2, PEG3); // the solution 
 // getch(); 
  return 0; 

} 

/* Move is a recursive function to solve the 
 * Towers of Hanoi puzzle. 
 * 
 *  Receive: n, the number of disks to be moved; 
 *           source, peg containing disk to move 
 *           destination, peg where to move disk 
 *           spare, peg to store disks temporarily, 
 *  Output:  A message describing the move 
 **************************************************/ 

void Move(int n, 
          char source, char destination, char spare) 
{ 
  if (n <= 1)                      // anchor 
 cout << "Move the top disk from " << source 
         << " to " << destination << endl; 
  else 
  {                                // inductive case 
    Move(n-1, source, spare, destination); 
    Move(1, source, destination, spare); 
    Move(n-1, spare, destination, source); 
  } 
}

/* hanoi.cpp solves the Towers of Hanoi puzzle

 moji

 * 
 * Input:  numDisks, the number of disks to be moved 
 * Output: a sequence of moves that solve the puzzle */ 

#include <iostream.h> 
#include <conio.h> 


void Move(int n, char source, char destination, char spare); 
int count = 0; 

int main() 
{ 
  const char PEG1 = 'A',            // the three pegs 
             PEG2 = 'B', 
             PEG3 = 'C'; 

  cout << "This program solves the Hanoi Towers puzzle. "; 

  cout << "Enter the number of disks: "; 
  int numDisks;                     // the number of disks to be moved 
  cin >> numDisks; 
  cout << endl; 

  Move(numDisks, PEG1, PEG2, PEG3); // the solution 
 // getch(); 
  return 0; 

} 

/* Move is a recursive function to solve the 
 * Towers of Hanoi puzzle. 
 * 
 *  Receive: n, the number of disks to be moved; 
 *           source, peg containing disk to move 
 *           destination, peg where to move disk 
 *           spare, peg to store disks temporarily, 
 *  Output:  A message describing the move 
 **************************************************/ 

void Move(int n, 
          char source, char destination, char spare) 
{ 
  if (n <= 1)                      // anchor 
 cout << "Move the top disk from " << source 
         << " to " << destination << endl; 
  else 
  {                                // inductive case 
    Move(n-1, source, spare, destination); 
    Move(1, source, destination, spare); 
    Move(n-1, spare, destination, source); 
  } 
}