讨论汉诺塔有关问题
讨论汉诺塔问题
1，对于N层汉诺塔，说明其存在唯一最优解（步数最优）及其最优步数
2，对于N层汉诺塔，给定一个N与M（M <=最优步数），求出最优解的第M
步的走法，格式为“第*层：从*堆－> 到*堆”，*是要填的内容。
上面都假设有三个堆ABC，初始所有盘都在A堆上，目标在C堆上；N很大。
下午我贴上的我解。
------解决方案--------------------
感觉题目的答案都比较直接；
m(1)=1;
m(2)=3;
m(3)=7;
...
m(n)=2*(m(n-1))+1=2^n-1;
对于n层的汉诺塔，必须经过三步，
1）.上面的n-1层的移到过渡杆,
2).第n层的盘子移动到目标杆，
3).过度杆上的n-1层的移到目标杆,
用归纳法可证题一；
对于第二题；
递归求解
fun(int n,char src,char tmp,char dst,int m)
{
int mid=2^(n-1)+1;
if (m==mid) printf( "move %c to %c ",src,dst);
else if (m <mid) fun(n-1,src,dst,tmp,m);
else fun(n-1,tmp,src,dst,m-mid);
}
时间复杂度O(logN);
------解决方案--------------------
非常简单的优化. 也不需要什么严格的数学证明.
fun(int n,char src,char tmp,char dst,int m)
{
int mid=2^(n-1)+1;
if (m==mid) printf( "move %c to %c ",src,dst);
else if (m <mid) fun(n-1,src,dst,tmp,m); // O(n)是因为这一步浪费的
else fun(n-1,tmp,src,dst,m-mid);
}
每次只要取mid = 2^k + 1 <= m, 要求k最尽可能大即可. 若m == mid, 则输出, 否则必是m > mid的情况, 此时问题变成fun(k, tmp, src, dst, m - mid).
显然, 每次至少减少m二进制表示的一位, 且与n无关. 故时间复杂度O(logM).
------解决方案--------------------
n,m所需的大小极不相同，当n=64时，m最大就可能需要
18,446,744,073,709,551,615．
而这就是unsigned __int64的最大值，所以，可以把
void Hanoit( unsigned __int64 n, unsigned __int64 m )
改为,
void Hanoit( byte n, unsigned __int64 m )
------解决方案--------------------
更正错误，刚才没睡醒，稀里糊涂乱说一通。
先说寻找k，线性比较需要O(N)，二分比较需要O(lgN)，某些CPU支持计算一个机器字内的前导零计数的指令，需要O(1)。
按最快的办法O(1)来算，你准备在算法中使用多少次计算k呢？通过严格的证明一次前导零的计算不足以改变整个算法的时间界，相当于O(N)变成O(N-1)。如果持续使用直到算法终止，那么指令使用次数等于M二进表示中1的个数，那么M中究竟有多少个1？概率分析求出1个数期望为N/2，那么仍没有改变算法的时间界是O(N)的事实。其他两种寻找k的办法个人认为最优化时间界对应为O(N)和O(x*NlgN)（x值计算太麻烦，就不贴了）。
再说“else if (m <mid) fun(n-1,src,dst,tmp,m)”这句代码，如果利用计算k的值来持续递归则需要处理参数的转移问题，当然这可以在O(1)时间内解决。
整个算法要比楼主的递归复杂一些，那么算法时间的常数因子要大一些。
通过整个分析说明利用求k的办法优化不合适。如果没能在算法高层上做优化这些小优化起的作用并不大。
期待LeeMaRS(小菜虎，仍需努力)同志研究出更好的优化办法。
------解决方案--------------------
OK. N这一块没有问题. 我没注意到N也就是M的最大二进制位数了.
O((logM)^2)是直接考虑最坏情况得出来的. 首先我每次都需要找M的二进制最高位, 要logM时间.
然后最坏情况下这样要做logM次. 所以得出一个O((logM)^2)的复杂度出来的.
另外我还被你带晕了一次. 算法复杂度可以做到O(logM).
因为整个算法流程下来, 我只需要对M的二进制表示扫描两次. 第一次是从最低位扫到最高位, 第二次是从最低位扫到最高位.
至于和O(N)比哪个更好, 应该说O(logM)的更好. 因为N可以很大, 而M可以很小.
1，对于N层汉诺塔，说明其存在唯一最优解（步数最优）及其最优步数
2，对于N层汉诺塔，给定一个N与M（M <=最优步数），求出最优解的第M
步的走法，格式为“第*层：从*堆－> 到*堆”，*是要填的内容。
上面都假设有三个堆ABC，初始所有盘都在A堆上，目标在C堆上；N很大。
下午我贴上的我解。
------解决方案--------------------
感觉题目的答案都比较直接；
m(1)=1;
m(2)=3;
m(3)=7;
...
m(n)=2*(m(n-1))+1=2^n-1;
对于n层的汉诺塔，必须经过三步，
1）.上面的n-1层的移到过渡杆,
2).第n层的盘子移动到目标杆，
3).过度杆上的n-1层的移到目标杆,
用归纳法可证题一；
对于第二题；
递归求解
fun(int n,char src,char tmp,char dst,int m)
{
int mid=2^(n-1)+1;
if (m==mid) printf( "move %c to %c ",src,dst);
else if (m <mid) fun(n-1,src,dst,tmp,m);
else fun(n-1,tmp,src,dst,m-mid);
}
时间复杂度O(logN);
------解决方案--------------------
非常简单的优化. 也不需要什么严格的数学证明.
fun(int n,char src,char tmp,char dst,int m)
{
int mid=2^(n-1)+1;
if (m==mid) printf( "move %c to %c ",src,dst);
else if (m <mid) fun(n-1,src,dst,tmp,m); // O(n)是因为这一步浪费的
else fun(n-1,tmp,src,dst,m-mid);
}
每次只要取mid = 2^k + 1 <= m, 要求k最尽可能大即可. 若m == mid, 则输出, 否则必是m > mid的情况, 此时问题变成fun(k, tmp, src, dst, m - mid).
显然, 每次至少减少m二进制表示的一位, 且与n无关. 故时间复杂度O(logM).
------解决方案--------------------
n,m所需的大小极不相同，当n=64时，m最大就可能需要
18,446,744,073,709,551,615．
而这就是unsigned __int64的最大值，所以，可以把
void Hanoit( unsigned __int64 n, unsigned __int64 m )
改为,
void Hanoit( byte n, unsigned __int64 m )
------解决方案--------------------
更正错误，刚才没睡醒，稀里糊涂乱说一通。
先说寻找k，线性比较需要O(N)，二分比较需要O(lgN)，某些CPU支持计算一个机器字内的前导零计数的指令，需要O(1)。
按最快的办法O(1)来算，你准备在算法中使用多少次计算k呢？通过严格的证明一次前导零的计算不足以改变整个算法的时间界，相当于O(N)变成O(N-1)。如果持续使用直到算法终止，那么指令使用次数等于M二进表示中1的个数，那么M中究竟有多少个1？概率分析求出1个数期望为N/2，那么仍没有改变算法的时间界是O(N)的事实。其他两种寻找k的办法个人认为最优化时间界对应为O(N)和O(x*NlgN)（x值计算太麻烦，就不贴了）。
再说“else if (m <mid) fun(n-1,src,dst,tmp,m)”这句代码，如果利用计算k的值来持续递归则需要处理参数的转移问题，当然这可以在O(1)时间内解决。
整个算法要比楼主的递归复杂一些，那么算法时间的常数因子要大一些。
通过整个分析说明利用求k的办法优化不合适。如果没能在算法高层上做优化这些小优化起的作用并不大。
期待LeeMaRS(小菜虎，仍需努力)同志研究出更好的优化办法。
------解决方案--------------------
OK. N这一块没有问题. 我没注意到N也就是M的最大二进制位数了.
O((logM)^2)是直接考虑最坏情况得出来的. 首先我每次都需要找M的二进制最高位, 要logM时间.
然后最坏情况下这样要做logM次. 所以得出一个O((logM)^2)的复杂度出来的.
另外我还被你带晕了一次. 算法复杂度可以做到O(logM).
因为整个算法流程下来, 我只需要对M的二进制表示扫描两次. 第一次是从最低位扫到最高位, 第二次是从最低位扫到最高位.
至于和O(N)比哪个更好, 应该说O(logM)的更好. 因为N可以很大, 而M可以很小.