qq_33748682
2016-01-16 14:02
采纳率: 33.3%
浏览 2.3k

汉诺塔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 2016-01-16 16:43
    已采纳

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

    打赏 评论
  • threenewbee 2016-01-16 14:33

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

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

    打赏 评论
  • ysuwood 2016-01-16 14:35

    用double类型试试。

    打赏 评论
  • 91program 2016-01-16 15:41

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

    打赏 评论
  • John_ToDebug 2016-01-25 10:11
    打赏 评论

相关推荐 更多相似问题