系数是常数的是线性递推,比如Fibonacci数 f[i] = f[i-1] + f[i-2]
系数不是常数的不是线性递推,比如错排方案数
https://www.luogu.com.cn/problem/P1096
给定、、三根足够长的细柱,在柱上放有个中间有孔的圆盘,共有个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为的情形)。
现要将这些圆盘移到柱上,在移动过程中可放在柱上暂存。要求:
(1)每次只能移动一个圆盘;
(2)、、三根细柱上的圆盘都要保持上小下大的顺序;
任务:设为个圆盘完成上述任务所需的最少移动次数,对于输入的,输出。
一个正整数,表示在柱上放有个圆盘。
一个正整数, 为完成上述任务所需的最少移动次数。
1
2
2
6
【限制】
对于的数据,
对于的数据,
【提示】
设法建立与的递推关系式。
#include <bits/stdc++.h> using namespace std; stringstream ss; string s; int n; int main() { cin >> n; ss << fixed << setprecision(0) << pow(2, n + 1); ss >> s; // s = ss.str(); s[s.size() - 1] -= 2; cout << s << endl; return 0; }
输入,输出,可以利用精确输出double的特性。