hanoi

/* brief function:
 * 汉诺塔求解，它的阶数手动输入；求解结果在控制台和文件中同步输出
* 计算n阶汉诺塔求解所花费时间，花费时间在控制台和文件中同步输出
* 
* move函数中的printf和fprintf函数十分耗费时间。在求解15阶汉诺塔的时候，如果注释掉move函数，则求解时间是毫秒级；
* 而不注释掉move函数，15阶汉诺塔求解时间大约是13~14秒之间（个人pc运行）
*/

#include
#include


long int count = 0;
FILE *fp;


void move(char x, int n, char z)
{
printf("\r\nstep %ld: move disk %d from %c to %c", ++count, n, x, z);
fprintf(fp, "\r\nstep %ld: move disk %d from %c to %c", count, n, x, z);
}


void hanoi(int n, char x, char y, char z)
{
if(n == 1)
{
move(x, 1, z);//将编号为1的圆盘由x移动到z 
}
else
{
hanoi(n-1, x, z, y);//将x上的编号为1至n-1的圆盘移动到y，z作辅助塔 
move(x, n, z); //将编号为n的圆盘由x移动到z 
hanoi(n-1, y, x, z);//将y上的编号为1至n-1的圆盘移动到z，x做辅助塔 
}
}


int main(void)
{
int n; 
clock_t start, finish;
double  hanoi_time_spent;

printf("\r\n请输入汉诺塔阶数：\r\n");
scanf("%d", &n);

fp = fopen("move_record.txt", "w+");
if(fp == NULL)
{
printf("record file open failed\r\n");
return 0;
} 

start = clock();
hanoi(n, 'A', 'B', 'C');
finish = clock();
hanoi_time_spent = (double)(finish - start) / CLOCKS_PER_SEC;

printf("\r\nmove hanoi time spent: %f second", hanoi_time_spent);
fprintf(fp, "\r\nmove hanoi time spent: %f second", hanoi_time_spent);

fclose(fp);

return 1;
}