标题:学渣求帮助 入门训练 Fibonacci数列
只看楼主
luciferxiaoz
Rank: 1
等 级:新手上路
帖 子:13
专家分:5
注 册:2013-11-23
得分:0 
回复 7楼 czz5242199
这个不对吧= = 数列的值就变了。
2013-11-24 21:54
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
得分:0 
讲一下这个题吧,楼主结的太快了。

首先就是越界,即便你用 long long 早晚也会越界的,所以要换个思路(或者用高精度大数运算,在这显然没那个必要)

公式 (a + b) % c = (a % c + b % c) % c

所以可以使用 7L提供的方法,数列中不再存储斐波那契的值,而是存储其对 10007 的余数,这样对结果没有影响,而且不会越界


[fly]存在即是合理[/fly]
2013-11-24 22:19
Yusoga
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2014-1-20
得分:0 
这个题最好别用递归做,用数组在主函数里面实现就好,用递归的话虽然算法没问题,但是时间开销太大,真正测评的时候能过样例就不错了,
我现在也在刷这个题,只拿了70分,1,2,1000000这三个评测数据还过不了,正在优化中...
2014-01-20 21:35
djydaw
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2014-2-9
得分:0 
你这个题明显用递归是不行的,肯定会超时,如果建立数组过大,达到1000000也是不行的。我想到一个比较巧妙的方法,已经提交成功了。
#include<iostream>
using namespace std;
int fibonacci(int n){
    if(1==n || 2==n){
        return 1;
    }
    else{
        int i=3;
        int a[2];
        a[1]=a[2]=1;
        while(i<=n){
            if(i%2!=0){
                a[1]=(a[1]+a[2])%10007;
            }
            else{
                a[2]=(a[1]+a[2])%10007;
            }
            i++;
        }
        if(i%2!=0){
            return a[2];
        }
        else{
            return a[1];
        }
    }
}
int main(){
    int n;
    while(cin>>n){
        cout<<fibonacci(n);
    }
    return 0;
}
2014-02-09 10:51



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-424067-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.238181 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved