Problem 25 1000-digit Fibonacci number

Problem 25: 1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂= 1.

Hence the first 12 terms will be:

• F₁ = 1
• F₂ = 1
• F₃ = 2
• F₄ = 3
• F₅ = 5
• F₆ = 8
• F₇ = 13
• F₈ = 21
• F₉ = 34
• F₁₀ = 55
• F₁₁ = 89
• F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

分析

求Fibonacci数列的第一个包含1000位数字的项对应的序号。

本质还是大数问题，和 Problem 16 Power digit sum 相同。所以可以直接复用 Problem 16 中的方法。

方法1 使用字符串实现乘法，适用于C++

详见 Problem 16 Power digit sum ，复用其中的add/mul等函数即可，此处不再赘述。

CPP

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main()
{
    std::vector<char> f1; // f1 = 1
    f1.push_back('1');

    std::vector<char> f2; // f2 = 1
    f2.push_back('1');

    int seq = 3;
    while(true){
        std::vector<char> f3 = add(f1, f2); // 复用 Problem 16 中的add
        if (f3.size() >= 1000){
            printf("seq:%d\n", seq);
            for(int i=0; i < f3.size(); i++) printf("%d", f3[i]);
            break;
        }

        f1 = std::move(f2);
        f2 = std::move(f3);
        seq ++;
    }

    return 0;
}

方法2 使用大数包，适用于golang

package main

import (
    "fmt"
    "math/big"
)

func main() {

    f1 := big.NewInt(1) // f1 = 1
    f2 := big.NewInt(1) // f2 = 1

    seq := 3
    for {
        f3 := f1.Add(f1,f2)
        if len(f3.String()) >= 1000 {
            fmt.Println(seq)
            fmt.Println(f3.String())
            break
        }
        f1 = f2
        f2 = f3
        seq ++
    }
}

方法3 直接计算，适用于python

f1, f2, seq = 1, 1, 3 # f1 = 1, f2 = 1
while True:
    f3 = f1 + f2
    if len(str(f3)) >= 1000:
        print(seq, f3)
        break
    seq = seq + 1
    f1, f2 = f2, f3

答案

4782

作者：JarvisChu
原文链接：Problem 25 1000-digit Fibonacci number
版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0