2 qq 33748682 qq_33748682 于 2016.01.16 22:02 提问

汉诺塔C语言编程问题,求帮忙

Description
大家都听说过汉诺塔吧?有n个圆盘由小到大排列,套在a柱上,每次只能移动一个圆盘,而且只能大的在下,小的在上,让你把a柱上的圆盘移到b柱,给你一个多余的c柱,问你最少移动多少次才能完成任务。

Input
输入有多组数据,每组包括一个整数n(n<=10000000),表示初始状态下有n个圆盘,当输入的n为0时,程序结束,n为负的情况不作处理。

Output
对每个输入,对应一行输出,每行输出包括一个整数,即移动的最小次数,因为数目非常大,所以请对9973求余后再输出。

Sample Input
Original Transformed
1
2
3
4
0

Sample Output
Original Transformed
1
3
7
15

Hint
采用结构:
……
for(;;){
scanf("%d",&n);
if(n==0)
break;
……
printf(……);
……
}
……至少需要2的n次方减1步
这是我写的代码,但是数非常大的时候就不能正常输出了,应该是溢出了,但具体怎么修改,求帮忙啊图片

5个回答

lm_whales
lm_whales   Rxr 2016.01.17 00:43
已采纳

写个快速(模)幂运算即可
注意这一条
请对9973求余后再输出
因为有这一条,所以直接拥int 类型就足够了,实际上 short 也 完全够用

caozhy
caozhy   Ds   Rxr 2016.01.16 22:33

因为只要求次数,所以其实这个问题就是大数的运算,汉诺塔的移动次数的计算公式是2^n-1

参考:http://blog.csdn.net/odaynot/article/details/8117682

qq_27183003
qq_27183003   Ds   Rxr 2016.01.16 22:35

用double类型试试。

91program
91program   Ds   Rxr 2016.01.16 23:41

汉诺塔问题是一个经典的算法,网上实现的代码很多,查找一下肯定可以找到。

John_ToStr
John_ToStr   Rxr 2016.01.25 18:11
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!