الگوريتم برج هانوي (hanoi) + برنامه (با ++c)


اینم از این الگوریتم معروف که یکی از دوستان درخواست کرده بود.

برج هانوی , معمایی است که از سه میله و 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.\n\n"; 

  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); 
  } 
}