题目描述:
糖和抖m在玩个游戏,规定谁输了就要请谁吃顿大餐:抖m给糖a b c三个驻, 并在a柱上放置了数量为n的圆盘,圆盘的大小从上到下依次增大,现在要做的事就是把a柱的圆盘全部移到c柱,移动的过程中保持小盘在上,大盘在下,且限定圆盘只能够移动到相邻的柱子,即a柱子上的圆盘只能够移动到b,b柱子上的圆盘只能够移动到a或者c,c同理。现在请你设计一个程序,计算所需移动的最小步数, 帮助糖赢得大餐!
一开始没仔细看以为是汉诺塔题,才发现题目要求柱子不能相隔移动,所有就和汉诺塔有些不同,可以推出公式,设函数f(n);要a![图片说明](https://www.nowcoder.com/equation?tex=%5Crightarrow "图片标题") C,可以用递归思想把f(n)转换到f(n-1),最大的⚪要到b上,上面n-1个⚪要移动到c柱上,然后最大⚪要到C上,上面n-1又要移到a上,最后再移回c上,总结
f(n) c转化为
1.f(n-1) a c;
2.max圈a b;
3.f(n-1) c a;
4..max圈 b c;
5.f(n-1) a c;
得到f(n)=f(n-1)+2;
#include <stdio.h> int main() { long long int a[26]; a[0]=0; int x,i; for(i=1;i<26;i++) { a[i]=3*a[i-1]+2; } while(~scanf("%d",&x)) { printf("%lld\n",a[x]); } return 0; }