见到一个题,让算斐波那契数列的第 n 项,手工推通项没推出来,记忆化递归如下
#include <stdio.h> #define MAX 1024 int F[MAX] = {0}; int f(int n) { if (F[n] != 0) { return F[n]; } F[n] = f(n-1) + f(n-2); return F[n]; } int calc_f(int n) { if (n <= 0) { return -1; } F[1] = F[2] = 1; return f(n); } int main() { int n; while (EOF != scanf("%d", &n)) { printf("%dn", calc_f(n)); } return 0; }
输入输出
10 55
后来想起来一个非递归的 O(n) 方法
#include <stdio.h> int f(int n) { if (n <= 0) { return -1; } if (n==1 || n==2) { return 1; } int a = 1; int b = 1; n -= 2; while (1) { a = a + b; if (--n <= 0) { return a; } b = a + b; if (--n <= 0) { return b; } } } int main() { int n; while (EOF != scanf("%d", &n)) { printf("%dn", f(n)); } return 0; }
最后耍赖上网看通项,http://en.wikipedia.org/wiki/F…,通项是
注意一下浮点转整型的向下取整,于是得到代码如下
#include <stdio.h> #include <math.h> int f(int n) { double q_5 = sqrt(5.0); double ans = (1/q_5)*pow((1+q_5)/2, n)-(1/q_5)*pow((1-q_5)/2, n); return ans+0.5; } int main() { int n; while (EOF != scanf("%d", &n)) { printf("%dn", f(n)); } return 0; }
果然通项公式是第一生产力啊。。