题目链接：点击打开链接
题目大意：略。
解题思路：如果考虑一下把64片金盘，由一根柱子上移到另一根柱子上，并且始终保持上小下大的顺序。这需要多少次移动呢？这里需要递归的方法。假设有n片，移动最少次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。
设f(n)为将n片圆盘所在塔全部移动到另一塔最少总次数；由递归算法可知：f(1) = 1;当n>1时，f(n) = f(n-1) + 1 + f(n-1)。f(n) = 把上面n-1片圆盘移动到中间塔最少总次数f(n-1) + 把第n片圆盘移动到目标塔+ 把中间盘的n-1片圆盘移动到目标塔最少总次数为f(n-1)。由数学计算可得：f(n)=2^n-1。(n>0)。
AC 代码1（递归版）
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; void hmove(int n,char s,char e) { printf("%c -> %c\n",s,e); } void hannoi(int n,char a,char b,char c) { if(n==1) hmove(1,a,c); else { hannoi(n-1,a,c,b); hmove(n,a,c); hannoi(n-1,b,a,c); } } int main() { int n; while(~scanf("%d",&n)) { hannoi(n,'a','b','c'); } return 0; }
AC 代码2（递归版）
#-*- coding:utf-8 -*- # move(n, a, b, c)表示的是有n个盘子在a柱子上，将要移到b柱子上面去 def move(n, a, b, c): # 如果a柱子上面只有一个盘子，则直接移到c柱子上面去并输出路径，结束递归 if n == 1: print a, '-->', c return # 表示的是将n-1的盘子从a柱子上面移到b柱子上面去 move(n-1, a, c, b) # 输出最下面个盘子移从a移到c的路径 print a, '-->', c # 将b柱子上面的n-1个盘子移动到c柱子上面 move(n-1, b, a, c) move(4, 'A', 'B', 'C')
