hanoi算法递归非递归以及扩展

这是个汉诺塔程序，在调试的时候，输入的数字最好不要大于15，因为每大一个数所得的结果的步骤都会多一倍。如果你有耐心等待结果的话除外。汉诺塔是在欧洲流行的一种游戏，有a,b,c三个竿。a竿上有若干个由大到小的圆盘，大的在下面，小的在上面，b,c都是空杆，请你把a杆上的圆盘都倒到别的杆上，或b或c，在倒盘的过程中不可以大的压小的，实例程序如下：

#include <stdio.h>
#include <stdlib.h>
void move(char x,char y) {
	printf("%c-->%c\n",x,y);
} 
void hanoi (int n,char one ,char two,char three) {
	if(n==1) 
		move (one ,three); 
	else {
		hanoi (n-1,one,three,two); 
		move(one,three); 
		hanoi(n-1,two,one,three); 
	} 
} 
int main() 
{
	int m; 
	printf("input the number of diskes:"); 
	scanf("%d",&m); 
	printf("the step to moving %3d diskes:\n",m); 
	hanoi(m,'A','B','C'); 
	system("pause");
} 

 

#include <stdio.h>
#include <conio.h>
int i=0;
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle){
	if(n>0){
		movedisc(n-1,fromneedle,usingneedle,toneedle);
		i++;
		switch(fromneedle){
            case 'a':
                switch(toneedle){
		            case 'b':printf("\t[%d]:\t%2d------>%2d\n",i,n,n);
						break;
					case 'c':printf("\t[%d]:\t%2d------------->%2d\n",i,n,n);
						break;
                }
			    break;
            case 'b':
                switch(toneedle){
		            case 'a':printf("\t[%d]:\t%2d<----------%2d\n",i,n,n);
						break;
					case 'c':printf("\t[%d]:\t\t%2d------>%2d\n",i,n,n);
						break;
				 }
			     break;
            case 'c':
                switch(toneedle){
		            case 'a':printf("\t[%d]:\t%2d<--------------%2d\n",i,n,n);
						break;
					case 'b':printf("\t[%d]:\t\t%2d<--------%2d\n",i,n,n);
						break;
                }
			    break;
		}
        movedisc(n-1,usingneedle,toneedle,fromneedle);
	}
}
int main(){
	unsigned n;
	printf("Please enter the number of discs: ");
	scanf("%d",&n);
	printf("\tneedle:\ta\t b\t c\n");
	movedisc(n,'a','c','b');
	printf("\t Total: %d\n",i);
	getch();
}

 

#include <stdio.h>
#define width (rings+1)

int main(){
	int rings, last, next, x, z[500], s[3];

	printf("how many rings?  "); scanf("%d",&rings);

	for(x=1; x<=rings; x++)  /* put rings on first peg */
		z[x]=width-x;
	for(x=0; x<=2*width; x+=width)  /* set base for each peg  */
		z[x]=1000;

	/* if even number of rings, put first ring on second peg; if odd, on third */

	if(rings%2==0){
		last=1; s[2]=0; s[1]=1;
	    z[width+1]=z[rings];
  	}else{
		last=2; s[1]=0; s[2]=1;
		z[2*width+1]=z[rings];
  	}

	printf("from 1 to %d\n",last+1); 
	s[0]=rings-1;

	while(s[0]+s[1]){ 		/* while first and second pegs aren't empty */
      
		/* next ring to move is smaller of rings on the two pegs not moved onto last */

		if(last==0)  
			next=z[width+s[1]]<z[2*width+s[2]]?1:2;
		if(last==1)  
			next=z[s[0]]<z[2*width+s[2]]?0:2;
		if(last==2)  
			next=z[s[0]]<z[width+s[1]]?0:1;

		/* top ring of 'to' peg must be larger and an even 'distance' away */

		if((z[next*width+s[next]])>(z[last*width+s[last]])||((z[last*width+s[last]]-z[next*width+s[next]])%2==0))
			last=3-next-last;

		printf("from %d to %d\n",next+1,last+1);

		s[next]=s[next]-1; s[last]=s[last]+1; /* move from 'next' to 'last' peg */
		z[last*width+s[last]]=z[next*width+s[next]+1];
    }
}

 

#include <stdio.h>

//--------------------------------------------------------
// 打印搬运动作
//--------------------------------------------------------
int MoveIt(int x,int Source,int Target)
{
    printf("Move %d From %d to %d\n",x,Source,Target);
    return 0;
}

//--------------------------------------------------------
// 用 4 根柱子移动盘子
// n 是盘子个数，编号从1 到 n
// First 是源柱子号
// Second Third 是两根过渡柱
// Fourth 是目标柱
//--------------------------------------------------------
int MoveHanoi(int n,int First,int Second,int Third,int Fourth)
{
    if (n<1) return 0;                   // 如果没有盘子就返回
    if (n==1)                            // 如果只有一个盘子
    {
        MoveIt(n,First,Fourth);          // 就直接从源柱子移到目标柱子上
        return 0;
    }
    if (n==2)                            // 如果有两个盘子
    {
        MoveIt(n-1,First,Second);        // 把上面的那片移到一个过渡柱上
        MoveIt(n,First,Fourth);          // 把下面的那片移到目标柱上
        MoveIt(n-1,Second,Fourth);      // 再把第 1 片从过渡柱移到目标柱上
		return 0;
    }
    if (n==3)                            // 如果有 3 片盘子
    {
        MoveIt(n-2,First,Second);        // 把最小的盘子移到一个过渡柱上
        MoveIt(n-1,First,Third);        // 把中间盘子移到另一过渡柱上
        MoveIt(n,First,Fourth);          // 把最大的盘子移到目标柱上
        MoveIt(n-1,Third,Fourth);        // 把中间盘子移到目标柱上
        MoveIt(n-2,Second,Fourth);      // 把最小的盘子移到目标柱上
        return 0;
    }
                                        // 递归地把上面 n-2 盘子移到一个过渡柱上
                                        // 留下最大的两个盘子
    MoveHanoi(n-2,First,Third,Fourth,Second);
    MoveIt(n-1,First,Third);            // 把倒数第 2 个盘子移到另一个过渡柱上
    MoveIt(n,First,Fourth);              // 把最底下的盘子移到目标柱上
    MoveIt(n-1,Third,Fourth);            // 把倒数第 2 个盘子移到目标柱上
                                        // 递归地把 n-2 个盘子从过渡柱上移到目标柱上
    MoveHanoi(n-2,Second,First,Third,Fourth);
    return 0;
}

int main()
{
	int num;
	scanf("%d",&num);
    MoveHanoi(num,1,2,3,4);
    return 0;
}

 

#include <stdio.h>
#include <math.h>
#define MAX_N 1000

int main(){
	double f[MAX_N];
	int n,i,j;
	double maxvalue,curvalue;
	printf("Please input count:");
	scanf("%d",&n);
	if(n>=MAX_N){
		printf("Out of range\n");
		return -1;
	}
	f[1]=1.0,f[2]=3.0;
	for(j=3;j<=n;j++){
		maxvalue=pow(2,j);
		for(i=1;i<j;i++){
			curvalue=2*f[i]+pow(2,j-i)-1;
			if(curvalue<maxvalue)
			maxvalue=curvalue;
			else
			break;
		}
		f[j]=maxvalue;
	}
	for(i=1;i<=n;i++)
		printf("m[%d]=%f\n",i,f[i]);
	return 0;
} 

 不得不佩服递归魅力，非递归实现方式实现起来让人有点费解。