洛谷 P1720 月落乌啼算钱

洛谷 P1720 月落乌啼算钱"/>

洛谷 P1720 月落乌啼算钱

题目描述：


思路：算出前几项之后找规律，发现符合斐波那契数列规律，因此决定采用递归思想。

但是若只是简单的函数递归，则会造成超时问题：

#include<stdio.h>
int f(int n);
int main() 
{int n;int Fn;scanf("%d",&n);Fn = f(n);printf("%.2lf",(double)Fn);return 0;
}
int f(int n)
{int result;if(n == 1 || n ==2)result = 1;else result = f(n-1)+f(n-2);return result;
}

其实超时的症结在于部分 f(n) 被重复计算，因此决定采用记忆数组的方法，在函数返回值之前将n以内的数组对应值一次性计算出来，返回 a[n] 作为结果：

#include<stdio.h>
int f(int n,int a[]);
int main() 
{int n;int a[50];  //记忆数组 int Fn;scanf("%d",&n);Fn = f(n,a);printf("%.2lf",(double)Fn);return 0;
}
int f(int n,int a[])
{int i;a[0] = 0;a[1] = 1;for(i = 2;i <= n;i++)a[i] = a[i-1]+a[i-2];return a[n];
}

结果？？？当 n=48 时又华丽丽地wa了？？？
在调试过程中发现，当 n=47 时，a[47] 就变成了负值。由此可见，问题在于数据超出了 int 的范围！再次更改代码：

#include<stdio.h>
long long int f(int n,long long int a[]);
int main() 
{int n;long long int a[50];  //记忆数组 long long Fn;scanf("%d",&n);Fn = f(n,a);printf("%.2lf",(double)Fn);return 0;
}
long long int f(int n,long long int a[])
{int i;a[0] = 0;a[1] = 1;for(i = 2;i <= n;i++)a[i] = a[i-1]+a[i-2];return a[n];
}

AC撒花~