斐波那契数列,比较实用的O(n)方法 ( 有O(lgn)方法,但不实用)
九度OJ 1387
#include <iostream> using namespace std; long long arr[72]; // 注意一定是longlong 否则会溢出 int last; int main() { std::ios::sync_with_stdio(false); last = 1; arr[0] = 0; arr[1] = 1; int n; while(cin>>n) { if(n > last) { for(int i = last + 1;i <= n;i++) { arr[i] = arr[i - 1] + arr[i - 2]; } last = n; } cout<<arr[n]<<endl; } return 0; }
扩展1: 青蛙跳水,一次跳一个台阶或者两个台阶
九度OJ 1388
////青蛙跳台阶,一次可以跳一个台阶,也可以跳两个台阶,问跳到n台阶有多少种跳法 // ////转换成斐波那契数列 // #include <iostream> using namespace std; long long arr[72]; // 注意一定是longlong 否则会溢出 int last; int main() { std::ios::sync_with_stdio(false); last = 2; arr[0] = 0; arr[1] = 1; arr[2] = 2; int n; while(cin>>n) { if(n > last) { for(int i = last + 1;i <= n;i++) { arr[i] = arr[i - 1] + arr[i - 2]; } last = n; } cout<<arr[n]<<endl; } return 0; }
扩展2 青蛙跳水问题,一个可以跳 1、2、...、n个台阶, 九度OJ 1389
//一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。 //求该青蛙跳上一个n级的台阶总共有多少种跳法 //f[n] = Sigma (1<=i<=n-1) (f[i]) = 2^(n-1) #include <cstdio> using namespace std; int main() { int n; long long ret; while(scanf("%d",&n)!=EOF) { if(n>=32)//大于8字节后,需要分两次移位,否则出错 { ret = 1 << 30; ret = ret << (n - 31); } else ret = 1 << (n - 1); printf("%lld\n",ret); } return 0; }
扩展3 矩形覆盖问题
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
2*n的矩形方法数定义为f(n). 第一个2*1的小矩形覆盖大矩形的左边,要么竖着放,转化成f(n-1),要么横着放两次,转化成f(n-2), 因此f(n) = f(n-1) + f(n-2)
九度OJ 1390
#include <iostream> using namespace std; long long arr[72]; // 注意一定是longlong 否则会溢出 int last; int main() { std::ios::sync_with_stdio(false); last = 2; arr[0] = 0; arr[1] = 1; arr[2] = 2; int n; while(cin>>n) { if(n > last) { for(int i = last + 1;i <= n;i++) { arr[i] = arr[i - 1] + arr[i - 2]; } last = n; } cout<<arr[n]<<endl; } return 0; }