剑指OFFER之二维数组中的查找（九度OJ1384）
剑指OFFER之二维数组中的查找（九度OJ1384）
用户1154259
发布于 2018-01-17 19:21:21
发布于 2018-01-17 19:21:21
文章被收录于专栏：xingoo, 一个梦想做发明家的程序员
题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。斐波那契数列的定义如下：
输入：
输入可能包含多个测试样例，对于每个测试案例，
输入包括一个整数n(1<=n<=70)。
输出：
对应每个测试案例，
输出第n项斐波那契数列的值。
样例输入：3
样例输出：
2
解题思路：
题目中可以看到，n的范围是70，最先想到的递归肯定是不行的，那么我们钻一个空子，事先生成一个数组，到时候取出来就可以了。太高端的想法，也想不出，记得有一个用矩阵求解的方法，很快。这道题只要不超时就可以了。 另外要注意的地方，就是70的时候递归的数据时很大的，记得类型要用最大的long long 输出%lld才可以！
代码:
#include <stdio.h>
long long num[71] = {0,1};
void createfi(long long *num);
int main(void){
int n;
createfi(num);
while(scanf("%d",&n)!=EOF && n>=1 && n<=70){
printf("%lld\n",num[n]);
}
return 0;
}
void createfi(long long *num){
int i;
for(i=2;i<71;i++){
num[i] = num[i-1]+num[i-2];
}
}
/**************************************************************
Problem: 1387
User: xhalo
Language: C
Result: Accepted
Time:0 ms
Memory:916 kb
****************************************************************/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2014-05-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
