问题:
思路:
汉诺塔问题非常经典，不懂推荐去看B站正月点灯笼老师的对于汉诺塔的讲解: 「递归练习」汉诺塔，非常生动.
不过这道题单靠传统汉诺塔解法会超时，仔细思考发现，其实没有必要同时搜索hanoi(n - 1, A, C, B)和hanoi(n - 1, B, A, C).
只需调用一次hanoi(n - 1)就可通过计算确定一次操作的移动次数和消耗体力. 使用结构体记录状态. 代码如下:
1 #include <iostream> 2 using namespace std; 3 typedef long long ll; 4 5 struct node { 6 ll cost; 7 ll step; 8 }; 9 node hanoi(int n) 10 { 11 node np; 12 if (n == 1) { 13 np.step = 1; 14 np.cost = 1; 15 } 16 else { 17 node tmp = hanoi(n - 1); 18 np.step = tmp.step * 2 + 1; 19 np.cost = tmp.cost * 2 + n; 20 } 21 return np; 22 } 23 24 int main() 25 { 26 int n; 27 cin >> n; 28 node x = hanoi(n); 29 cout << x.step << ' ' << x.cost << endl; 30 return 0; 31 }转载于:https://www.cnblogs.com/AntonLiu/p/10800033.html
