一． 题意：
算出汉诺塔移动序列中对应位置的号码，数据规模很大，所以不能单纯递归，而是要找出汉诺塔序列的规律。
二． 汉诺塔数列
为了得出最少的移动步数，当n为偶数时，最上层小盘子首先移动到过渡柱上；当n为奇数时，最上层小盘子首先移动到目标柱上。不论n为奇偶，过渡柱和目标柱上，盘子的叠加编号始终是奇偶叠加，不会出现奇数或偶数连续叠加。
这里的规律是：
第 n 项 ＝ n 能被 2 整除的次数 + 1。 （需要用高精度）
汉诺塔数列例子：
盘子个数 | 数列 | 至少需要步数 |
N = 1 | 1 | 2-1=1 |
N = 2 | 121 | 2-1=3 |
N = 3 | 1213121 | 2-1=7 |
N = 4 | 121312141213121 | 2-1=15 |
操作步骤：
当n=1时：将盘子从A柱直接移到C柱，完成移动，即（A→C）。当n=2时：先把n-1=1个盘子从A柱移动到B柱，再将A柱上最后一个盘子从A柱移动到C柱，最后将B柱上的n—1个盘子从B柱移动到C柱上，完成移动，即A→B，A→C，B→C。
当n=3时：先把n-1=2个盘子从A柱移动到B柱（借助C），再将B柱上剩余的盘子移动到C柱（借助A）。
当n为任意正整数时：同样是先把n-1个盘子从A柱移动到B柱（借助C），方法与上述相同。
通过以上分析，Hanoi问题是典型的利用递归来解决的，是将规模为n的问题，降解为规模为n-1的小问题、n-2的较小问题……依次降解，直到递归出口，求出最低阶规模的解，代入高一阶问题中，直至求出规模为n的问题的解。递归包括回溯和递推两个过程。
为了分辨n个不同的盘子，将其由小到大依序编号为1，2，3，…，n-1，n，以便于研究其所需的移动次数及次序、探求其规则性。
从n=1、n=2的移动情况，可归纳出一个结论：即n=2时处理n=1两次，共须移动22-1=3步，其Hanoi数列为121。同理可知n=3时，处理n=2两次，共须移动23-1=7步，其Hanoi数列为1213121，同理可知n=4时，处理n=3两次，总共须移动24-1=15步，其汉诺塔数列为121312141213121，依此类推。
分析得出递归模型：
f（1）=1（n=1）
f（n）=2×f（n-1）+1（n＞1→）
f（n）=2×f（n-1）+1
=2×（2×f（n-2）+1）+1
=2×（2×（2×f（n-3）+1）+1）+1……
=2n-1。
因此，n个盘子总共需移动最少步数计算公式为：f（n）=2n-1。
很容易看出对于n个盘子的汉诺塔的移动步骤为s(n+1)=s(n)(n+1)s(n),假设输入为p。则L（n）=2^n-1,L(n)表示n个盘子的汉诺塔的移动步骤的数目。假如p=2^n,则结果是n+1;否则可找出一个最小的n,使得p<=2^n-1。并且p>2^(n-1),否则p<=2^(n-1),由对称性知f(p)=f(p-2^(n-1)),即减去不超过P的2的最大次幂，这样一直减下去直至p=2^x.所以结果为最初始的p表示为2进制数后从右边数起的0的个数加1.
三． 代码
//
// main.cpp
// sicily-1028
//
// Created by ashley on 14-11-7.
// Copyright (c) 2014年 ashley. All rights reserved.
// #include <iostream>
#include <string>
using namespace std; int counting(string data)
{
int sum = ;
int length = (int)data.length();
for (int i = ; i < length; i++) {
data[i] = data[i] - '';
}
while (data[length - ] % == ) {
for (int i = ; i < length; i++) {
if (i + < length) {
int b = data[i + ];
data[i + ] = (data[i] % ) * + b;
}
data[i] = data[i] / ;
}
sum++;
}
return sum + ;
} int main(int argc, const char * argv[])
{
int cases;
string number;
cin >> cases;
int counter = ;
while (counter != cases) {
cin >> number;
counter++;
cout << "Case " << counter << ": " << counting(number) << endl;
if (counter < cases) {
cout << endl;
}
}
return ;
}