HDU汉诺塔系列

　　这几天刷了杭电的汉诺塔一套，来写写题解。

　　HDU1207 汉诺塔II　　　　　　　　

　　HDU1995 汉诺塔V

　　HDU1996 汉诺塔VI

　　HDU1997 汉诺塔VII

　　HDU2064 汉诺塔III

　　HDU2077 汉诺塔IV

　　HDU2175 汉诺塔IX

　　HDU2184 汉诺塔VIII

　　HDU2511 汉诺塔 X

HDU1207 汉诺塔II

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1207 ,多柱汉诺塔问题。

先说下四柱汉诺塔的Frame算法：　

　　（1）用4柱汉诺塔算法把A柱上部分的n- r个碟子通过C柱和D柱移到B柱上。　　【F( n- r )步】

　　（2）用3柱汉诺塔经典算法把A柱上剩余的r个碟子通过C柱移到D柱上。　　【2^r-1步】

　　（3）用4柱汉诺塔算法把B柱上的n-r个碟子通过A柱和C柱移到D柱上。　【F(n-r)步】

　　（4）依据上边规则求出所有r（1≤r≤n）情况下步数f(n)，取最小值得最终解。

　　　　因此Frame算法的递归方程如下：　　F(n)=min(2*F(n-r)+2^r-1)，（1≤r≤n）。

　　通过这个方程我们能得到所有4柱汉诺塔的步骤个数，同时也有人证明了，对于四柱汉诺塔，当r=(sqrt(8*n+1)-1)/2时，能保证f(n)取得最小值。所以算法的复杂度是F(n)=O(sqrt(2*n)*2^ sqrt(2*n))。

基于四柱汉诺塔的Frame算法，我们可以引申到多柱(M柱)汉诺塔的情况，我们简称M柱汉诺塔算法：

　　（1）用M柱汉诺塔算法把1柱上部分的n-r个碟子通过3…M柱移到2柱上【M( n- r )步】。

　　（2）用M-1柱汉诺塔算法把1柱上剩余的r个碟子通过3…M-1柱移到M柱上【<M-1>(r)步】。

　　（3）用M柱汉诺塔算法把2柱上的n-r个碟子通过1柱和3…M柱移到M柱上【M( n- r )步】。

　　（4）依据上边规则求出所有r（1≤r≤n）情况下步数m(n)，取最小值得最终解M(n)。

综上，题目的解答可以通过方程直接得到

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
const int maxn = 65;
LL pow2[maxn] , r[maxn] , tower4[maxn];
int main() 
{
    int n;
    pow2[0] = 1;
    for(int i = 1 ; i < maxn ; i++)
        pow2[i] = pow2[i - 1] << 1;
    for(int i = 1 ; i < maxn ; i++) {
        double tmp = (sqrt(8.0 * i + 1) - 1) * 0.5;
        r[i] = int(tmp);
    }
    for(int i = 1 ; i < maxn ; i++) {
        int j = r[i];
        tower4[i] = 2 * tower4[i - j] + pow2[j] - 1;
    }
    while(cin >> n)
    {
        cout << tower4[n] << endl;
    }
    return 0;
}

HDU1207

HDU1995 汉诺塔V

　　(PS：先上课了，晚上更新)

HDU汉诺塔系列

原文：http://www.cnblogs.com/H-Vking/p/4362539.html