汉诺塔的C++.doc

汉诺塔的C/C++程序
2009-11-05 09:58:08| 分类： 默认分类 | 标签：无|字号大中小订阅
借鉴+创新=succes 我已调试成功，新手望指教
// hanoizjqendend.cpp : Defines the entry point for the console application.
//zjq// 9:18/11/4/2009
//profit:先搭架构再填函数
// 递归的思想：一个出口+一个关系
// 函数入口是形参，出口是return(只有一个返回值)或指针||引用（直接改变内存值）
// 注意全局变量的应用好处
// 灵活的思维+好的习惯
// return 0;和break;都有中断异情的作用，灵活用之
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
struct layer
{
int numOfTower;
int Layer[12];
};
struct Hanoi
{
struct layer a;
struct layer b;
struct layer c;
};
struct Hanoi H={1,{1,2,3,4,5,6,7,8,9,10,11,12},2,
{0,0,0,0,0,0,0,0,0,0,0,0},3,{0,0,0,0,0,0,0,0,0,0,0,0}};//初始化////,/////;/////
void hanoi(int n,struct layer*pre,struct layer*mid,struct layer*end);
void displayOfNum(int n,struct layer*pre,struct layer*mid,struct layer*end);//步骤d数字显示
void move2end(int n_bottom,struct layer*pre,struct layer*mid,struct layer*end);
int createHanoi();
void displayOfImage(int m,struct layer*pre,struct layer*mid,struct layer*end);//步骤d图像显示
void Delay(int seconds) ;//delay function
void moveLayer(int m,struct layer*pre,struct layer*mid,struct layer*end);//塔层移动：改变layer值
void starplay(int m);//每次输出m个“*”
int sumOfStep=0;//record the steps
int n=0;
struct layer*pre=&H.a; //initialization
struct layer*mid=&H.b; //将柱子的编号地址交给指针
struct layer*end=&H.c;
main()
{
n=createHanoi(); //创建的塔层数
hanoi(n,pre,mid,end);
cout<<"总共步数："<<sumOfStep<<endl;
//setw(n) 右对齐<iomanip.h>
return 0;
}
//汉诺塔递归函数
void hanoi(int n,struct layer*pre,struct layer*mid,struct layer*end)
//修改一定是依据形参进行的,里面形参决定一切 //递归的同一个函数关系：
//hanoi(int n,int*pre,int*mid,int*end)
//只要将其他的要求解的函数对应的参数传
//递过来就好了
{

if(n==1) //递归出口:初始值/初始步骤
{ //递归一定要有出口
//this is important//
displayOfNum(1,pre,mid,end); //函数运行到出口就回到下一步了
moveLayer(0,pre,mid,end); //记录塔层移动后的塔层分布，i.e layer的重新赋值
displayOfImage(0,pre,mid,end);

}
else
{ //递归精髓1个出口 + 1个f(n)与f(n-1)的关系
hanoi(n-1,pre,end,mid); //f(n)与f(n-1)的循环关系
move2end(n,pre,mid,end); //实为move2end(n,pre,end)，中间mid是为了显示用的;
hanoi(n-1,mid,pre,end);
}
}
//步骤的数字显示
void displayOfNum(int n,struct layer*pre,struct layer*mid,struct layer*end)
{
cout<<(*pre).numOfTower<<"->"<<(*end).numOfTower<<endl;
sumOfStep++;
}
//A底到C底--move2end
void move2end(int n_bottom,struct layer*pre,struct layer*mid,struct layer*end)
{
cout<<(*pre).numOfTower<<"->"<<(*end).numOfTower<<endl;
sumOfStep++;
moveLayer(0,pre,mid,end);
displayOfImage(0,pre,mid,end);
}
//创建汉诺塔
int createHanoi()
{
int m; //m: the layers of beginning
start: cout<<"input the number of the hanoi tower(<12):"<<endl;
cin>>m;
if(m<1||m>12)
{
cout<<"the number is outflow,please input again:"<<endl;
goto start;
//return 0;
}
return m;
}
//图像显示
void displayOfImage(int m,struct layer*pre,struct layer*mid,struct layer*end)
//显示有问题，未掉过顺序来
{
for(m=0;m<n;m++)
{
if((*pre).numOfTower==1)
starplay((*pre).Layer[m]); //(*pre).numOfTower来决定显示的顺序
else if((*mid).numOfTower==1)
starplay((*mid).Layer[m]);
else
starplay((*end).Layer[m]);
if((*pre).numOfTower==2)
starplay((*pre).Layer[m]); //(*pre).numOfTower来决定显示的顺序
else if((*mid).numOfTower==2)
starplay((*mid).Layer[m]);
else
starplay((*end).Layer[m]);
if((*pre).numOfTower==3)
starplay((*pre).Layer[m]); //(*pre).numOfTower来决定显示的顺序
else if((*mid).numOfTower==3)
starplay((*mid).Layer[m]);
else
starplay((*end).Layer[m]);
cout<<endl;
}
/////cout<<(*pre).Layer[0]<<"->"<<(*mid).Layer[2]<<endl;
Delay(1); //动态渐近显示
//cout<<setw(3)<<"* "<<endl<<setw(3)<<"***"<<endl;
}
//塔层移动---分情况讨论，为零的情况有多种，1a=0,c=1 |2a=0,c=0 |3a=1,c=1 |4a=1,c=1
void moveLayer(int m,struct layer*pre,struct layer*mid,struct layer*end)
{
int i,j;
for(i=m;i<n;i++)
{
if((*pre).Layer[n-1]==0)
{
i=n-1;
break;
}
else if((*pre).Layer[i]!=0)
break;
}
for(j=m;j<n;j++)
{
if((*end).Layer[n-1]==0)
{
j=n-1;
break;
}
else if((*end).Layer[j]==0&&(*end).Layer[j+1]!=0)
break;
}
(*end).Layer[j]=(*pre).Layer[i];
(*pre).Layer[i]=0;
}
//延时程序
void Delay(int seconds)//延时seconds秒的程序 入口 delay(int n)，强制延时
{

clock_t start=clock();//像计数器
clock_t lay=(clock_t)seconds*CLOCKS_PER_SEC;
while((clock()-start)<lay);
}
//星星显示
void starplay(int j)
{
int maxLayer=2*n-1;
int numOfOut=(2*j-1);
int blankNum1=(maxLayer-numOfOut)/2;//空格数
int blankNum2=(maxLayer-numOfOut)/2;
if(j!=0)
{
while(blankNum1!=0)
{
cout<<" ";
blankNum1--;
}
while(numOfOut!=0)
{
cout<<"*";
numOfOut--;
}
while(blankNum2!=0)
{
cout<<" ";
blankNum2--;
}
}
else
{
while(maxLayer!=0)
{
cout<<" ";
maxLayer--;
}
}
}