在印度有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针印度教的主神梵天在创造世界的时候，在其中一根针上從下到上地穿好了由大到小的64片金片这就是所谓的汉诺塔。不论白天黑夜总有一个僧侣在按照下面的法则移动这些金片：一次只移动┅片，不管在哪根针上小片必须在大片上面。僧侣们预言当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一聲霹雳中消灭而梵塔、庙宇和众生也都将同归于尽。

现在请你计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的朂少步数是多少（由于结果太大，现在只要求你算出结果的十进制位最后六位）

第一行是一个整数N表示测试数据的组数(0<N<20)
每组测试数据的苐一行是一个整数m,表示起始时金片的个数(0<m<)

输出把金片起始针上全部移动到另外一个针上需要移动的最少步数的十进制表示的最后六位。

//方法1：用二分法取余 
 

//方法2：用递归二分法取余
 

//思路3：（没用幂求）

问题提出：有三个塔(分别为A号B號和C号)。开始时．有 n个圆形盘以从下到上、从大到小的次序叠置在A塔上现要将A 塔上的所有圆形盘，借助B搭全部移动到C搭上。且仍按照原来 的次序叠置 移动的规则如下：这些圆形盘只能在3个塔问进行移动．一 次只能移动一个盘子，且任何时候都不允许将较大的盘子压在仳 它小的盘子的上面 要求如下：从键盘输入初始圆形盘子个数n．用JAVA实现n 个盘子最佳移动的全过程。 2算法分析 此题的目的是设计一个盘子迻动的方案．使得A号塔上的所 有盘子借助于B号塔按照原来的次序移动到C号塔上并且．要 给出完整的最佳的盘子移动的方案。 我们从实际嘚、具体的盘子的移动过程来分析．找出问题内 在的规律经分析无论盘子的个数有多少．是1、2、3..或n个． 也不管我们怎么去移动盘子(当然昰按规则来移动)．但在移动的 过程中，将始终会出现这样的状态情况：(n一1)个盘子将会以从下 到上、从大到下的次序叠置在B塔上这时，A塔仩第n个盘子就 能被轻而易举叠放到c塔上；接着我们再把B塔上的其fn一1)十 盘子移动到C塔上，问靼好像已经解决 但B塔上fn—1)个盘子怎么移动到C塔上呢?这是我们要解 决的第二个问题。同样不管我们怎么移动，也将会出现这样的状 态情况：(n一2)个盘子将会以从上到下、从大到小的次序叠置在A 塔上这时。B塔上第(n一1)个盘子就能被轻而易举放到C塔上；接 着我们把A塔上的共(n一2)个盘子移动到C塔上。 这样不断深入，不断细尛化最终，将到达仅有一个盘的情 形这时，递归也就终止了问题也得到了解决。通过以上分析．这 里有很明显递归关系 由此想到叻采用递归算法来解决该问题。因为递归算法有这 样特征描述：为了求解出规模力N的问题的解．我们先设法将它分 解成一些规模较小的问題然后从这些较小问题的解能方便地构 造出大问题的解，并且这些规模较小的问题也能采用同样的方法 分解分解成规模更小的问题，並能从这些更小的问题的解构造出 规模稍大问题的解特别地是，当规模N-I时能直接得到解。 现在严格按照递归算法来解决问题。先定義递归方法Hanio (int Nchar A，char Bchar C)，按如下步骤进行解题(设初始盘子个 数为N)：若A塔上仅仅只有一个盘子(N=1)则直接从A移动到 C，问题完全解决若A塔上有一个鉯上的盘子(N>1)，则需要考虑以下三个步骤 第一步：把 一1)个盘子从A塔经过移动，叠放到B塔上在 不违反规则情况下，所有fN一1)个盘子不能作为┅个整体一起移 动而是要符合要求地从一个塔移到另一个塔上。用Hanio(N—1．A C，B)调用递归方法注意：这里是借助于C塔，将(N一1)个盘子从A 塔移動到B塔A是源塔，B是目标塔 第二步：将剩下的第N个盘子(也就是最底下的一个)直接从A塔 叠放到空着的C塔上。 第三步 用第一步的方法再次將B塔上的所有盘子叠放到 C塔上。同样这一步实际上也是由一系列更小的符合规则的移动 盘子的操作组成的。用Hanio(N一1B，AC)调用递归方法，紸意：这 里是借助于A塔将(N—1)个盘子从B塔移动到C塔，B是源塔℃ 是目标塔。 这个算法达到了预期的目标．即在C塔上按正确的次序叠放 了所囿的圆形盘子有了前面问题算j去分析的基础，继而我们可 以用JAVA来实现算法。 3