《数据结构》递归实现汉诺塔

main.cpp:汉诺塔实现。

思路分析:

若n=1,则只需把盘子从a挪动到c

若n>1,

(1)把前n-1个盘子从a经过c挪动到b

(2)把第n个盘子从a挪动到c

(3)把前n-1个盘子从b经过a挪动回c

实现:

#include <fstream>
#include <iostream>
using namespace std;

ofstream fout("out.txt");

void Move(int n,char x,char y)
{
 fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
 if(n==1)
  Move(1,a,c);
 else
 {
  Hannoi(n-1,a,c,b);
  Move(n,a,c);
  Hannoi(n-1,b,a,c);
 }
}

int main()
{
 fout<<"以下是7层汉诺塔的解法:"<<endl;
 Hannoi(7,'a','b','c');
 fout.close();
 cout<<"输出完毕!"<<endl;
 return 0;
}

Leave a Reply

Your email address will not be published.