Problem 25 | Project Euler |

[sx349]

https://pe-cn.github.io/25/

Problem 25 1000-digit Fibonacci numberThe Fibonacci sequence is defined by the recurrence relation:F1 = 1 F2 = 1Fn = Fn−1 + Fn−2 Hence the first 12 terms will be:F1 = 1F2 = 1F3 = 2F4 = 3F5 = 5F6 = 8

[Stardusten]

Mathematica

NestWhile[#+1&,1,Fibonacci[#]<=10^999&]

[liiuhongbo]

#include<iostream>
using namespace std;

int a = 0, b = 1, num[2][1005] = { {1, 1}, {1, 1} };

int func(int x, int y) {
    num[y][0] = num[x][0];
    for (int i = 1; i <= num[y][0]; i++) {
        num[y][i] += num[x][i];
        if (num[y][i] > 9) {
            num[y][i + 1] += num[y][i] / 10;
            num[y][i] %= 10;
            if (num[y][0] == i) num[y][0]++;
        }
    }
    return num[y][0] == 1000;
}

int main() {
    cout << (sizeof(num[0]) / sizeof(int)) << endl;

    for (int i = 3; 1; i++) {
        if (func(b, a)) {
            cout << i << endl;
            break;
        }
        swap(a, b);
    }
    return 0;
}

[jinyiliu]

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

n = 1
while len(str(fib(n))) < 1000:
    n += 1

[p-gp]

#include <stdio.h>
#define M 1000

int add(int *ver1, int *ver2);

int main(){
    int a[M+2]={1,1}, b[M+2]={1,1}, cnt=0, co=2;

    while(cnt<M){
        co++;
        cnt=add(a,b);
    }

    printf("f(%d):", co);
    if(co%2==1){
        for(int i=a[0]; i>0; --i){
            i%100==0?printf("\n%d", a[i]):printf("%d", a[i]);
        }
    }else{
        for(int i=b[0]; i>0; --i){
            i%100==0?printf("\n%d", b[i]):printf("%d", b[i]);
        }
    }

    return 0;
}

int add(int *ver1, int *ver2){
    static int count=3;               
    int arr[M+2]={0}, up=0, ad=0;
    int m=ver1[0]>ver2[0]?ver1[0]:ver2[0];

    for(int i=1; i<=m; ++i){
        if((ad=ver1[i]+ver2[i]+up-10)>=0){
            up=1;
            arr[i]=ad;
            m=i==m?m+1:m;
        }else{
            arr[i]=ad+10;
            up=0;
        }
    }
    arr[0]=m;

    if(count%2==1){
        for(int i=0; i<=arr[0]; ++i){
            ver1[i]=arr[i];
        }
    }else{
        for(int i=0; i<=arr[0]; ++i){
            ver2[i]=arr[i];
        }
    }
    count++;

    return m;
}

[zhou-ying-wan]

include

include

using namespace std; const int N = 10000;

int f[N];

int fabonacci(int u) { f[1]=1,f[2]=1; for(int i =3;i<=u;i++) { f[i]=f[i-1]+f[i-2]; } return f[u]; }

int main() { int n; cin>>n;

cout<<fabonacci(n);
return 0;

}

[oldtommmy]

import java.math.BigInteger;

public class T25 {
    public static void main(String[] args) {

        BigInteger[] fab = new BigInteger[10000];
        fab[1] = BigInteger.ONE;
        fab[2] = BigInteger.ONE;
        for (int i = 3; i < 10000; i++) {
            fab[i] = fab[i-1].add(fab[i-2]);
            if (String.valueOf(fab[i]).length()>=1000){
                System.out.println(i); //4782
                break;
            }
        }
    }
}

[182663823]

include

using namespace std;

int func(int num1, int num2) { num1[0] = num2[0];

for(int i = 1; i <= num1[0]; i++) {
    num1[i] += num2[i];
    if(num1[i] > 9) {
        num1[i + 1] += num1[i] / 10;
        num1[i] %= 10;
        if(i == num1[0])
            num1[0]++;
    }
}
return num1[0] == 1000;

}

int main() { int num[2][1005] = {{1, 1}, {1, 1}}; int a = 0, b = 1;

for(int i = 1; ;i++) {
    if(func(num[a], num[b])) {
        cout << i << endl;
        break;
    }
    swap(a, b);
}

return 0;

}

[weisus]

Mathematica

(* 不再赘述如何求斐波那契数列 *)

NestWhile[# + 1 &, 1,
 (Fibonacci[#] // IntegerLength) != 1000 &]

[xiaodouzi666]

include

using namespace std;

void add(int n1, int n2) { n2[0] = n1[0]; for (int i = 1; i <= n2[0]; i++) { n2[i] += n1[i]; if (n2[i] > 9) { n2[i + 1] += n2[i] / 10; n2[i] %= 10; if (n2[0] == i) { n2[0]++; } } } }

int main() { int num[2][1005] = {{1, 1}, {1, 1}}, a = 0, b = 1; //第一个维度表示第几个数字，第二个维度表示这个数字是什么; a表示后 面一个数字，b表示前面一个数字 for (int i = 3; 1; i++) { add(num[a], num[b]); if (num[b][0] >= 1000) { cout << i << endl; break; } swap(a, b); }

return 0;

}

[AdwardAllan]

using Combinatorics

findfirst(x->x>=1000,1:10000 .|> fibonaccinum .|> digits .|> length) #4782