益智玩具汉诺塔( 二 ) _生活百科

C语言#include <stdio.h>#include <windows.h>void Hanoi(int n, char a,char b,char c);void Move(int n, char a, char b);int count;int main(){ int n=8; printf("汉诺塔的层数:\n"); scanf(" %d",&n); Hanoi(n, 'A', 'B', 'C'); Sleep(20000); return 0;}void Hanoi(int n, char a, char b, char c){ if (n == 1) { Move(n, a, c); } else { Hanoi(n - 1, a, c, b); Move(n, a, c); Hanoi(n - 1, b, a, c); }}void Move(int n, char a, char b){ count++; printf("第%d次移动 Move %d: Move from %c to %c !\n",count,n,a,b);} FORTRAN C HANOI LIST PROGRAM MAIN INTEGER N PRINT *, "ENTER THE AMOUNT OF STEP:" READ *, N CALL HANOI(N,'A','B','C') END RECURSIVE SUBROUTINE HANOI(N,START,STATION,AIM) INTEGER N CHARACTER :: START, STATION, AIM IF (N.EQ.1) THEN CALL MOVE(START,AIM) ELSE CALL HANOI(N-1,START,AIM,STATION) CALL MOVE(START,AIM) CALL HANOI(N-1,STATION,START,AIM) END IF END SUBROUTINE SUBROUTINE MOVE(START, AIM) CHARACTER :: START, AIM PRINT *, START, " -> ", AIM END SUBROUTINE汉诺塔问题的非递归实现#include<stdio.h>#include<math.h>#include<stdlib.h>//第0位置是柱子上的塔盘数目intzhua[100]= {0},zhub[100]= {0},zhuc[100]= {0};charcharis(charx,intn)//左右字元出现顺序固定，且根据n值奇偶尔不同{ switch(x) { case'A': return(n%2==0)?'C':'B'; case'B': return(n%2==0)?'A':'C'; case'C': return(n%2==0)?'B':'A'; default: return'0'; }}voidprint(charlch,charrch)//列印字元{ if(lch=='A') { switch(rch) { case'B': zhub[0]++; zhub[zhub[0]]=zhua[zhua[0]]; zhua[zhua[0]]=0; zhua[0]--; break; case'C': zhuc[0]++; zhuc[zhuc[0]]=zhua[zhua[0]]; zhua[zhua[0]]=0; zhua[0]--; break; default: break; } } if(lch=='B') { switch(rch) { case'A': zhua[0]++; zhua[zhua[0]]=zhub[zhub[0]]; zhub[zhub[0]]=0; zhub[0]--; break; case'C': zhuc[0]++; zhuc[zhuc[0]]=zhub[zhub[0]]; zhub[zhub[0]]=0; zhub[0]--; break; default: break; } } if(lch=='C') { switch(rch) { case'A': zhua[0]++; zhua[zhua[0]]=zhuc[zhuc[0]]; zhuc[zhuc[0]]=0; zhuc[0]--; break; case'B': zhub[0]++; zhub[zhub[0]]=zhuc[zhuc[0]]; zhuc[zhuc[0]]=0; zhuc[0]--; break; default: break; } } printf("\t"); inti; printf("("); for(i=1; i<=zhua[0]; i++) printf("%d",zhua[i]); printf(")"); printf("("); for(i=1; i<=zhub[0]; i++) printf("%d",zhub[i]); printf(")"); printf("("); for(i=1; i<=zhuc[0]; i++) printf("%d",zhuc[i]); printf(")"); printf("\n");}voidHannuo(intn){//分配2^n个空间 bool*isrev; isrev=(bool*)malloc(sizeof(bool)*(int)pow（2,n)); for(inti=1; i<pow（2,n);i++)isrev[i]=false;//循环计算是否逆序for(intci=2; ci<=n; ci++){ for(intzixh=(int)pow（2,ci-1）；zixh<pow（2,ci); zixh+=4）//初始值重複一次，自增值可加4，减少循环次数。 isrev[zixh]=isrev[(int)pow（2,ci)-zixh];//该位置为中间位置，且奇次幂逆序，偶数幂不逆序 isrev[(int)pow（2,ci)]=((ci-1）%2==0)?false:true; } charlch='A',rch; rch=(n%2==0?'B':'C'); printf("%d\t",1）； printf("%c->%c",lch,rch); print(lch,rch); for(intk=2; k<pow（2,n); k++){ if(k%2==0) rch=charis(lch,n); else lch=charis(rch,n); printf("%d\t",k); if(isrev[k]) { printf("%c->%c",rch,lch); print(rch,lch); } else { printf("%c->%c",lch,rch); print(lch,rch); } }}intmain(){ intn; printf("Inputthenum:"); scanf("%d",&n); zhua[0]=n; for(inti=1; i<=n; i++) zhua[i]=n-i+1; Hannuo(n); return0;}

益智玩具 汉诺塔( 二 )

益智玩具汉诺塔( 二 )