hanoi.c

recursive:数据结构(黄国瑜 叶乃菁 编著)中的递归例子

/*=========================================Program Description ==========================*/
/*程序名称 :hanoi.c                                                                    */
/*程序目的 :运用递归来解决河内塔问题                                                  */
/*written by chen xiao yong .(chen studio)                                 */
/*=======================================================================================*/

/*---------------------------------------------------------*/
/*递归解决河内塔问题*/
/*---------------------------------------------------------*/
# include <stdio.h>
long int Counter;   //可能超过int的表示范围

int Hanoi(char From,char To,char Auxiliary,int N)
{
	if (N == 1) {               /*递归结束条件*/
		Counter ++;             /*计数器递增*/
		printf("Step %d :",Counter);
		printf("Move disk 1 from peg-%c to peg-%c.\n",From,To);
	}
	else {                      /*递归执行部分*/
		   /*将目的桩和辅助桩交换*/
		Hanoi(From,Auxiliary,To,N-1); /*将前N-1 个铁盘从来源桩移往辅助桩*/
		Counter ++;               /*计数器递增*/
		printf("step %d :",Counter);
		printf("Move disk %d from peg-%c to peg-%c.\n",N,From,To);/*将编号为N的铁盘从来源桩移往目的地*/
		/*将来源桩和辅助桩交换*/
		Hanoi(Auxiliary,To,From,N-1);    /*将前N-1个铁盘从辅助桩移往目的桩*/
	}
}



/*-----------------------------------------------------------*/
/*主程序*/
/*-----------------------------------------------------------*/

                   /*计数器变量*/
void main()
{	double step;
	step = pow(2,24);
	printf("2的24次方等于%f,如果24个铁盘,那么要2(24) -1次",step);


	int Number;              /*铁盘数目变量*/
	char Source;             /*源桩*/
	char Destination;        /*目的桩*/
	char Auxiliary;          /*辅助桩*/


	Counter = 0;
	printf("The Tower of Hanoi program.\n");
	printf("Please enter the number of disks  :");
	scanf("%d",&Number);            /*输入铁盘数*/
	printf("\nThe source peg :");
	Source = getche();            /*输入来源桩*/
	printf("\nThe Auxiliary  :");
	Auxiliary = getche();       /*输入辅助桩*/
	printf("\nThe Destination peg :");
	Destination = getche();      /*输入目的桩*/

	printf("\n");

	Hanoi(Source,Destination,Auxiliary,Number);   /*调用递归函式*/
}