汉诺塔非递归算法
这是个好问题，很少看到有人写汉诺塔的非递归...其实只要先写出递归，然后把递归的每一步要做的事情记录在一个栈里面就可以了
public class Test {
private static void emitStep(int source, int dest) {
System.out.println(source + " -> " + dest);
}
static class Step {
Step(int n, int s, int d, int t) {
this.n = n;
source = s;
dest = d;
temp = t;
}
int n, source, dest, temp;
}
private static void hanoi(int n, int source, int dest, int temp) {
java.util.Stack<Step> steps = new java.util.Stack<Step>();
steps.add(new Step(n, source, dest, temp));
while (steps.empty() == false) {
Step step = steps.pop();
if (step.n == 1) {
emitStep(step.source, step.dest);
continue;
}
steps.push(new Step(step.n - 1, step.temp, step.dest, step.source));
steps.push(new Step(1, step.source, step.dest, 0));
steps.push(new Step(step.n - 1, step.source, step.temp, step.dest));
}
}
public static void main(String[] args) {
hanoi(3, 1, 3, 2);
}
}
㈡ python汉诺塔非递归
python汉诺塔非递归，运用list和function知识的解答
无论stack还是recursion都是从汉诺塔的原理去解决问题，但如果已经想清楚汉诺塔的原理，其实只用把答案print出来就行了
先找规律：
一层：A-->C
两层：A-->B
-------
A-->C
-------
B-->C
三层：A-->C
A-->B
C-->B
-------
A-->C
-------
B-->A
B-->C
A-->C
注意到n层汉诺塔有(2**n) - 1 个步骤，而中间的一步（两个分割线之间）都是“A-->C”，中间的这一步将这一层汉诺塔的解分为上下两个部分
仔细观察，上面一部分是将上一层的解中所有的B，C交换，下面一部分是将上一层的解中所有的A，B交换
例如第二层是：
A-->B
A-->C
B-->C
第三层上部分就将第二层的解的C换成B，B换成C，即得出：
A-->C
A-->B
C-->B
第三层下部分就将第二层的解的A换成B，B换成A，即得出：
B-->A
A-->C
C-->B
这个规律同样适用于第一层，和以后的所有层
然后就好办了，代码如图：
代码
其中convertAB,convertBC就是AB交换，BC交换的函数，这两个函数可以自己定义，用中间变量即可
㈢ 如何使用非递归算法来实现汉诺塔问题
#include<iostream>
usingnamespacestd;
voidHanoi(charsrc,chardes,charvia,intn)
{
if(n==1)
{
cout<<n<<":"<<src<<"-->"<<des<<endl;
return;
}
Hanoi(src,via,des,n-1);
cout<<n<<":"<<src<<"-->"<<des<<endl;
Hanoi(via,des,src,n-1);
}
intmain()
{
intn;
cin>>n;
cout<<"recusive:"<<endl;
Hanoi('A','C','B',n);
cout<<endl;
cout<<"normal:"<<endl;
charorder[2][256];
charpos[64];
order[0]['A']='B';
order[0]['B']='C';
order[0]['C']='A';
order[1]['A']='C';
order[1]['B']='A';
order[1]['C']='B';
//0是顺序1是逆序
intindex[64];
//确定轨迹的顺序还是逆序
inti,j,m;
for(i=n;i>0;i-=2)
index[i]=1;
for(i=n-1;i>0;i-=2)
index[i]=0;
memset(pos,'A',sizeof(pos));
for(i=1;i<(1<<n);i++)
{
for(m=1,j=i;j%2==0;j/=2,m++);
cout<<m<<":"<<pos[m]<<"-->"<<order[index[m]][pos[m]]<<endl;
pos[m]=order[index[m]][pos[m]];
}
return0;
}
㈣ c语言hanoi塔问题 求用非递归解决
#include<stdio.h>
#defineMAXSTACK10/*栈的最大深度*/
intc=1;/*一个全局变量，表示目前移动的步数*/
structhanoi{/*存储汉诺塔的结构，包括盘的数目和三个盘的名称*/
intn;
charx,y,z;
};
voidmove(charx,intn,chary)/*移动函数，表示把某个盘从某根针移动到另一根针*/
{
printf("%d.Movedisk%dfrom%cto%cn",c++,n,x,y);
}
voidhanoi(intn,charx,chary,charz)/*汉诺塔的递归算法*/
{
if(1==n)
move(x,1,z);
else{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}
voidpush(structhanoi*p,inttop,charx,chary,charz,intn)
{
p[top+1].n=n-1;
p[top+1].x=x;
p[top+1].y=y;
p[top+1].z=z;
}
voinreverse_hanoi(structhanoi*p)/*汉诺塔的非递归算法*/
{
inttop=0;
while(top>=0){
while(p[top].n>1){/*向左走到尽头*/
push(p,top,p[top].x,p[top].z,p[top].y,p[top].n);
top++;
}
if(p[top].n==1){/*叶子结点*/
move(p[top].x,1,p[top].z);
top--;
}
if(top>=0){/*向右走一步*/
move(p[top].x,p[top].n,p[top].z);
top--;
push(p,top,p[top+1].y,p[top+1].x,p[top+1].z,p[top+1].n);
top++;
}
}
}
intmain(void)
{
structhanoip[MAXSTACK];
printf("reverseprogram:n");
hanoi(3,'x','y','z');
printf("unreverseprogram:n");
c=1;
p[0].n=3;
p[0].x='x',p[0].y='y',p[0].z='z';
unreverse_hanoi(p);
return0;
}
㈤ C语言汉诺塔问题非递归解法代码求大神讲解
int game2()要改为int main()后才可编译运行：
#include<stdio.h>
#include<stdlib.h>
#define CSZL 10
#define FPZL 10
typedef struct hanoi
{
int n;
char x,y,z;
}hanoi;
typedef struct Stack //定义栈结点
{
hanoi *base,*top;
int stacksize;
}Stack;
int InitStack(Stack *S)
{
S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); //申请栈空间
if(!S->base) //若申请不成功返回失败信息
return 0;
S->top=S->base; //置为空栈
S->stacksize=CSZL; //栈结点数
return 1;
}
int PushStack(Stack *S,int n,char x,char y,char z) //入栈
{
if(S->top-S->base==S->stacksize) //若栈已满
{
S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); //补充申请，扩充栈空间
if(!S->base) //若申请不成功返回失败信息
return 0;
S->top=S->base+S->stacksize; //重置栈顶指针
S->stacksize+=FPZL; //重置栈空间尺寸
}
S->top->n=n; //新结点信息存入栈顶结点
S->top->x=x;
S->top->y=y;
S->top->z=z;
S->top++; //栈中元素加1
return 1;
}
int PopStack(Stack *S,int *n,char *x,char *y,char *z) //出栈
{
if(S->top==S->base) //若栈已空
return 0; //返回出错信息
else
{
S->top--; //栈顶指针减1
*n=S->top->n; //返回出栈元素信息
*x=S->top->x;
*y=S->top->y;
*z=S->top->z;
return 1;
}
}
int EmptyStack(Stack *S) //判定是否空栈
{
if(S->base==S->top)
return 1;
else
return 0;
}
int i=1;
void Move(char x,char z) //打印移动盘子的信息
{
printf(" 第%d步，%c-->%c",i++,x,z);
}
int main() /* 非递归法 */
{
int n;
char x,y,z;
Stack *S;
system("cls"); /*清屏指令*/
S=(Stack *)malloc(sizeof(Stack)); //申请栈空间
if(!S)
return 0;
if(!InitStack(S)) //初始化栈
return 0;
printf("请输入汉诺塔的初始盘子数量以及轴的名称：");
scanf("%d %c%c%c",&n,&x,&y,&z);
if(!PushStack(S,n,x,y,z)) //要移动的盘子数及各轴名称入栈
return 0;
while(!EmptyStack(S)) //当栈非空时循环
{
if(!PopStack(S,&n,&x,&y,&z)) //若空栈则退出循环，否则出栈一个任务
break;
if(n==1) //若只有一个盘子，直接移动
{
Move(x,z);
}
else //有1个以上的盘子时入栈（注意栈的工作特点，是后进先出，所以最先做的事要最后入栈）
{
if(!PushStack(S,n-1,y,x,z)) //将上层的n-1个盘子从y移向z
break;
if(!PushStack(S,1,x,y,z)) //将底层的盘子从x移向z
break;
if(!PushStack(S,n-1,x,z,y)) //将上层的n-1个盘子从x移向y
break;
}
}
free(S->base);
S->base=NULL;
S->top=NULL;
S->stacksize=0;
return 0;
}
㈥ c++汉诺塔不用递归怎么做
算法介绍：
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n - 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。
●汉诺塔算法的递归实现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;
}●汉诺塔算法的递归实现C源代码：
#include<stdio.h>
void hanoi(int n,char A,char B,char C)
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B);
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C);
}
}
main()
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题：\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}
●汉诺塔算法的非递归实现C++源代码
#include <iostream>
using namespace std;
//圆盘的个数最多为64
const int MAX = 64;
//用来表示每根柱子的信息
struct st{
int s[MAX]; //柱子上的圆盘存储情况
int top; //栈顶，用来最上面的圆盘
char name; //柱子的名字，可以是A，B，C中的一个
int Top()//取栈顶元素
{
return s[top];
}
int Pop()//出栈
{
return s[top--];
}
void Push(int x)//入栈
{
s[++top] = x;
}
} ;
long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数
int main(void)
{
int n;
cin >> n; //输入圆盘的个数
st ta[3]; //三根柱子的信息用结构数组存储
Creat(ta, n); //给结构数组设置初值
long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
Hannuota(ta, max);//移动汉诺塔的主要函数
system("pause");
return 0;
}
void Creat(st ta[], int n)
{
ta[0].name = 'A';
ta[0].top = n-1;
//把所有的圆盘按从大到小的顺序放在柱子A上
for (int i=0; i<n; i++)
ta[0].s[i] = n - i;
//柱子B，C上开始没有没有圆盘
ta[1].top = ta[2].top = 0;
for (int i=0; i<n; i++)
ta[1].s[i] = ta[2].s[i] = 0;
//若n为偶数，按顺时针方向依次摆放 A B C
if (n%2 == 0)
{
ta[1].name = 'B';
ta[2].name = 'C';
}
else //若n为奇数，按顺时针方向依次摆放 A C B
{
ta[1].name = 'C';
ta[2].name = 'B';
}
}
long Pow(int x, int y)
{
long sum = 1;
for (int i=0; i<y; i++)
sum *= x;
return sum;
}
void Hannuota(st ta[], long max)
{
int k = 0; //累计移动的次数
int i = 0;
int ch;
while (k < max)
{
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " <<
"Move disk " << ch << " from " << ta[i%3].name <<
" to " << ta[(i+1)%3].name << endl;
i++;
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if (k < max)
{ //把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
if (ta[(i+1)%3].Top() == 0 ||
ta[(i-1)%3].Top() > 0 &&
ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << "Move disk "
<< ch << " from " << ta[(i-1)%3].name
<< " to " << ta[(i+1)%3].name << endl;
}
else
{
ch = ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout << ++k << ": " << "Move disk "
<< ch << " from " << ta[(i+1)%3].name
<< " to " << ta[(i-1)%3].name << endl;
}
}
}
}
㈦ 求C语言汉诺塔非递归算法
#include#define MAXSTACK 10 /* 栈的最大深度 */int c = 1; /* 一个全局变量，表示目前移动的步数 */struct hanoi { /* 存储汉诺塔的结构，包括盘的数目和三个盘的名称 */
int n;
char x, y, z;
};void move(char x, int n, char y) /* 移动函数，表示把某个盘从某根针移动到另一根针 */
{
printf("%d. Move disk %d from %c to %cn", c++, n, x, y);
}void hanoi(int n, char x, char y, char z) /* 汉诺塔的递归算法 */
{
if (1 == n)
move(x, 1, z);
else {
hanoi(n - 1, x, z, y);
move(x, n, z);
hanoi(n - 1, y, x, z);
}
}void push(struct hanoi *p, int top, char x, char y, char z,int n)
{
p[top+1].n = n - 1;
p[top+1].x = x;
p[top+1].y = y;
p[top+1].z = z;
}void unreverse_hanoi(struct hanoi *p) /* 汉诺塔的非递归算法 */
{
int top = 0;while (top >= 0) {
while (p[top].n > 1) { /* 向左走到尽头 */
push(p, top, p[top].x, p[top].z, p[top].y, p[top].n);
top++;
}
if (p[top].n == 1) { /* 叶子结点 */
move(p[top].x, 1, p[top].z);
top--;
}
if (top >= 0) { /* 向右走一步 */
move(p[top].x, p[top].n, p[top].z);
top--;
push(p, top, p[top+1].y, p[top+1].x, p[top+1].z, p[top+1].n);
top++;
}
}
}int main(void)
{
int i;
printf("reverse program:n");
hanoi(3, 'x', 'y', 'z');
printf("unreverse program:n");
struct hanoi p[MAXSTACK];
c = 1;
p[0].n = 3;
p[0].x = 'x', p[0].y = 'y', p[0].z = 'z';
unreverse_hanoi(p);return 0;
}