web analytics

汉诺塔问题扩展 打表

描述

“汉诺塔”,是一个众所周知的古老游戏。现在我们把问题稍微改变一下:如果一共有4根柱子,而不是3根,

那么至少需要移动盘子多少次,才能把所有的盘子从第1根柱子移动到第4根柱子上呢?

为了编程方便,您只需要输出这个结果mod 10000的值。

输入

第一行为测试数据的个数n(1<=n<=100);
下面跟若干行,每行一个整数m。(1<=m<=100)

输出

每行一个正整数,表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。

样例输入

样例输出

提示因为多了一根柱子,所以可以把第1根柱子最上面的若干个盘子先移到第2根柱子上,然后把剩下的所有盘子移到第4根柱子上,最后把第2根柱子上的若干个盘子移到第4根柱子上,即可完成移动。需要注意两点:
1. 因为第2根柱子已经放了上面的若干个盘子,因此在移动第1根柱子上剩下的盘子时,第2跟柱子就没法再利用了,否则就会造成大盘子压在小盘子上面;
2. 因为要求最少的移动次数,所以在移动第1根柱子最上面的若干个盘子到第2根柱子上时,就要把所有分法都考虑到,并且取其中移动次数最少的。

 

分析:

于是打个表就好:

找规律打表。

打表code

 

 

Post a Comment

You must be logged in to post a comment.