漢諾塔非遞歸演算法
這是個好問題，很少看到有人寫漢諾塔的非遞歸...其實只要先寫出遞歸，然後把遞歸的每一步要做的事情記錄在一個棧裡面就可以了
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;
}