汉诺塔V
http://acm.hdu.edu.cn/showproblem.php?pid=1995
设当有N个盘子时,第i个盘子从一个柱子移到另一个柱子需要移动的步数为f[n,p],则有:当N=p时(即p是最底下的那个盘子),f[n,p]=1;而当N!=p时,p要跟着上面N-1个盘子先移动到B柱子,等N移到C后再移到C柱子。所以此时f[n,p]=2*f[n-1,p]。
View Code
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iomanip>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
long long p_hanno(int n,int p)
{
if (n==p) return 1;
else
return 2*p_hanno(n-1,p);
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
int p;
cin>>n>>p;
cout<<p_hanno(n,p)<<endl;
}
return 0;
}
汉诺塔III
http://acm.hdu.edu.cn/showproblem.php?pid=2064
只允许先从中间过渡。那么设b[i]为i个盘子从两边(中间)移到中间(两边)(模拟计算一下发现两个一样的)的步数。
所以容易有a[i]=2*b[i-1]+1+2*b[i-1]+1+2*b[i-1]。(把i个盘子从A移到C需要先把前i-1个盘子A->B->C,再让i移到B,再让前i-1个盘子移动C->B->A,然后i从B->C,然后前i-1从A->B->C,完成)即,a[i]=6*b[i-1]+2; 而容易得到:b[i]=3*b[i-1]+1。
View Code
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iomanip>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
long long B(int n)
{
if (n==1) return 1;
else
return 3*B(n-1)+1;
}
long long A(int n)
{
if (n==1) return 2;
else
return 6*B(n-1)+2;
}
int main()
{
int n;
while(cin>>n)
{
cout<<A(n)<<endl;
}
return 0;
}
汉诺塔IV
http://acm.hdu.edu.cn/showproblem.php?pid=2077
和Ⅲ类似,如果允许最大的放上面,则只需要前i-1从A->B,i从A->B->C,前i-1从B->C。所以跟上面比只有a[i]=2*b[i-1]+2不一样。
View Code
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iomanip>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
long long B(int n)
{
if (n==1) return 1;
else
return 3*B(n-1)+1;
}
long long A(int n)
{
if (n==1) return 2;
else
return 2*B(n-1)+2;
}
int main()
{
int n;
int t;
cin>>t;
while(t--)
{
cin>>n;
cout<<A(n)<<endl;
}
return 0;
}
汉诺塔VI
http://acm.hdu.edu.cn/showproblem.php?pid=1996
水题本性。允许不按最优步骤走,计算有多少种序列。n个盘子,每个盘子都可以选择三个柱子,即3^n。
View Code
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iomanip>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
long long hanno6(int n)
{
if (n==0) return 1;
else
return 3*hanno6(n-1);
}
int main()
{
int n;
int t;
cin>>t;
while(t--)
{
cin>>n;
cout<<hanno6(n)<<endl;
}
return 0;
}