print(2*(2**int(input())-1))
解题思路:
假设有n个盘子,而且我们已经知道了: 移动n-1个盘子所需的最少步数,记为 fn -1于是有式子fn=2*( fn-1) +1
为什么呢?
n个盘子上面的 n -1个盘子(编号0~n -2)视为一个整体,我们需要将其移动到 B(经过空的 C柱)需要f(n )-1 步(不考虑柱子编号,我们利用空柱子将这一部分移动过去需要的步数相同)。此时仅仅需要 1 步将第 n 个盘子(编号为 n -1)移动到C,此时这个大盘子不影响我们移动剩余的 n -1个盘子。那我们就可以经A ,将其移动到 C 柱,又需fn -1 步,此时n 个盘子移动完毕。
共需要: fn=2*( fn-1) +1次 (这便是移动n个盘子到目标状态的最小步数)
利用数列知识: f[n] +1= 2 (f(n -1) +1)此时为等比数列,且f(1) = 1,故有: fn = 2” - 1
2n个盘子就是2fn
就是2*(2” - 1)
0.0分
2 人评分
简单的a+b (C语言代码)浏览:528 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:557 |
罗列完美数 (C语言代码)浏览:491 |
1071题解浏览:493 |
Tom数 (C语言代码)浏览:527 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:646 |
C二级辅导-等差数列 (C语言代码)浏览:695 |
神奇的fans (C语言代码)浏览:989 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1000 |
A+B for Input-Output Practice (III) (C语言代码)浏览:424 |