洛谷 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撒花~
更多推荐
洛谷 P1720 月落乌啼算钱
发布评论