题目25：第一个包含1000位数字的斐波那契数列项是第几项？

欧拉计划

1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:



Hence the first 12 terms will be:



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

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

题目：

以下是斐波那契数列的递归定义：



那么其 12 项为:



因此第 12 项， ，是第一个包含三位数字的项。

斐波那契数列中第一个包含 1000 位数字的项是第几项？

huomqh

def fbnq(x,y):
    return x+y
x,y=1,1
z=0
i=2
while len(str(z))<1000:
    i+=1
    z=fbnq(x,y)
    x,y=y,z

print(i,z)

4782

Plusenxue

class Fibo():
    def __init__(self):
        self.x = 0
        self.y = 1
    def __iter__(self):
        return self
    def __next__(self):
        self.x,self.y = self.y,self.x+self.y
        return self.x

value = 0
number = 1
a = Fibo()
it = iter(a)

while len(str(value)) < 1000:
    value = next(it)
    number += 1

print(number)

愤怒的大头菇

a=1;b=1
count = 0
while len(str(a))< 1000:
      
      a,b=b,a+b
      count += 1
print(count+1)

答案4782

jerryxjr1220

4782
[Finished in 0.1s]
这题属于送分题

fib = [0,1]
for a in range(1, 10000):
        fib.append (fib[a-1]+fib[a])
        if len (str(fib[-1])) >= 1000:
                print (a+1)
                exit()

芒果加黄桃

# encoding:utf-8
# 第一个包含1000位数字的fab是哪个数字
from time import time           
def euler024():
    a, b = 1, 1
    count = 2
    while True:
        a, b = b, a + b
        count += 1
        if(len(str(b))) >= 1000:
            print(count)
            break
if __name__ == '__main__':
    start = time()
    euler024()
    print('cost %.6f sec' % (time() - start))

渡风

此代码使用matlab编程
Problem25所用时间为0.2628秒
Problem25的答案为4782

%% Problem25
% 题目25:第一个包含1000个数字的斐波那契数列是第几项？        
function Output=Problem25(Input)
tic
if nargin==0
Input=1000;
end
F1=1;
F2=1;
Num=2;
Sum=1;
while (Sum<Input)
    Num=Num+1;
    F3=Vector_Plus(F1,F2);
    F1=F2;
    F2=F3;
    Sum=length(F3);
end
Output=Num;
toc
disp('此代码使用matlab编程')
disp(['Problem25所用时间为',num2str(toc),'秒'])
disp(['Problem25的答案为',num2str(Output)])
end
%% 子程序
%此程序实现两个向量的加法
function Output=Vector_Plus(a,b)
if nargin==0
    a=[9 9 9 9 9 9 ];
    b=[2 0];
end
L1=length(a);
L2=length(b);
L=max(L1,L2);
if L1<L2
   Span=L2-L1;
   Newa=[zeros(1,Span),a];
   Newb=b;
elseif L1>L2
   Span=L1-L2;
   Newa=a; 
   Newb=[zeros(1,Span),b];
else
    Newa=a;
    Newb=b;
end
Rank=Newa+Newb;
for ii=L:-1:2
    if Rank(ii)>=10
        Rank(ii)=Rank(ii)-10;
        Rank(ii-1)=Rank(ii-1)+1;
    end
end
Biggest=0;
while (Rank(1)>=10)
    if Rank(1)>=10
       Rank(1)=Rank(1)-10;
       Biggest=Biggest+1;
    end
end
if Biggest>0
    Output=[Biggest,Rank];
else
    Output=Rank;
end
end

testabc123

def Ss():
    lista=[0,1,1,2]
    while True:
        if len(str(lista[-1])) < 1000:
            lista.append(lista[-2]+lista[-1])
        else:
            return lista.index(lista[-1])




if __name__ == '__main__':
    smax=Ss()
    print(smax)

99592938

l_fib=[0,1,1]
a=b=1
while 1:
    a=a+b
    l_fib.append(a)
    if len(str(a))>=1000:
        break
    b=a+b
    l_fib.append(b)
    if len(str(b))>=1000:
        break
print(l_fib.index(max(l_fib)))

>>>
4782

看了大家的后，优化为：

fib=[0,1,1]
while 1:
    fib.append(fib[-2]+fib[-1])
    if len(str(fib[-1]))>=1000:break
print(fib.index(fib[-1]))

marmot

list_feb = [1, 1]
count = 2
while (True):
    n = list_feb[-1] + list_feb[-2]
    if len(str(n)) == 1000:
        print(count+1)      #循环到这个的时候break但是计数还是得+1
        break
    else:
        list_feb.append(n)
        count +=1

进击的小蜗牛

f1 = 1
f2 = 1
n = 2
while True:
    f3 = f1 + f2
    f1,f2 = f2,f3
    n += 1
    if len(str(f3)) == 1000:
        break
print(n)

结果：4782

王小召

第一个超过1000项的是第：4782

def Fab():
    a, b = 1, 0
    while True:
        yield a
        a, b = a+b, a

if __name__ == "__main__":
    count = 1
    for i in Fab():
        if len(str(i)) >= 1000:
            print("第一个超过1000项的是第：{}项".format(count))
            break
        else:
            count += 1

永恒的蓝色梦想

count = 1
a = 0
b = 1


while len(str(b)) < 1000:
    a, b = b, a + b
    count += 1


print(count)

4444567

a = 1
b = 1
i = 2
while True:
    a = a + b
    i += 1
    if len(str(a)) >= 1000:
        print('是a',a,i)
        break
    b = b + a
    i += 1
    if len(str(b)) >= 1000:
        print('是b',b,i)
        break
    

有马_冬巳

'''斐波那契数列中第一个包含 1000 位数字的项是第几项？'''

start = time.time()

f1 = 1
f2 = 1
fn = 0
n = 2
while len(str(fn)) < 1000:
    if n % 2 == 0:
        n += 1
        f1 = f1 + f2
        fn = f1
    elif n % 2 == 1:
        n += 1
        f2 = f1 + f2
        fn = f2
print("第一个包含1000为数字的项是第%d项" %n)
#print("这个项的值为: %d" %fn)

end = time.time()
print("共用时%f秒" %(end - start))

第一个包含1000为数字的项是第4782项
共用时0.031272秒

a1351468657

#include <stdio.h>
#include <string.h>

main()
{
        char num1[1100] = "1", num2[1100] = "1", temp[1100];
        
        int i, j;
        int a, b, c, d, e = 0, f, count = 0;
        while (strlen(num2) < 1000)
        {
                strcpy(temp, num2);
                j = strlen(num1);
                for (i = 0; i < j; i++)//让num1和num2相加并存到num2中
                {
                        a = num1[i] - '0';
                        b = num2[i] - '0';
                        c = a + b;
                        d = (c + e) % 10;

                        num2[i] = d + '0';
                        e = (c + e)/ 10;
                }
                while (e)//此时还有进位
                {
                        if (num2[i] != NULL)
                        {
                                f = num2[i] - '0';
                                f += e;
                                num2[i] = f + '0';
                
                        }
                        else
                        {
                                num2[i] = e + '0';
                        }
                        e /= 10;
                        i++;
                }
                if (num2[i] == NULL)//添加结束符
                {
                        num2[i] = '\0';
                }
                else
                {
                        num2[i + 1] = '\0';
                }


                strcpy(num1, temp);//将上一个num2的值给num1
                
                count++;//记录项数
        }
        
        printf("\n%d\n", count + 2);
}

大佬帮我看看还有没有可以优化的地方，谢谢！

ft215378

#第一个包含1000位数字的斐波那契数列项是第几项
from time import *
def fibonacci(n):
    n1 = 1
    n2 = 1
    n3 = 1

    if n < 1 :
        print('输入有误！')
        return -1
    while (n-2) > 0:
        n3 = n2 + n1
        n1 = n2
        n2 = n3
        n -= 1

    return n3


num = 1000
start = time()
while num:
    result = len(str(fibonacci(num)))
    if result < 1000:
        num += 1000
    elif result > 1000:
        num -= 1
    elif result == 1000:
        print(num)
        break
        
end = time()
print("用时：%f s" % (end-start))

guosl

/*
答案：4782
耗时：0.0103192秒
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct stBigInt//高精度数字类
{
  unsigned char a[1100];//存放具体的各位数字
  int nBits;//该高精度数的位数
  stBigInt(void)//构造函数
  {
    memset(a, 0, sizeof(a));
    nBits = 0;
  }
  stBigInt(const stBigInt& x)//复制构造函数
  {
    memcpy(a, x.a, sizeof(a));
    nBits = x.nBits;
  }
  const stBigInt& operator=(const stBigInt& x)//重载=运算符
  {
    memcpy(a, x.a, sizeof(a));
    nBits = x.nBits;
    return *this;
  }
  stBigInt operator+(const stBigInt x) const//重载+运算符
  {
    int bs = max(nBits, x.nBits);
    stBigInt y;
    unsigned char s = 0;
    for (int i = 0; i < bs; ++i)
    {
      s += a[i] + x.a[i];
      y.a[i] = s % 10;
      s = s / 10;
    }
    if (s > 0)
      y.a[bs++] = s;
    y.nBits = bs;
    return y;
  }
};

int main(void)
{
  stBigInt f0, f1, f2;
  f0.a[0] = 1;
  f0.nBits = 1;
  f1.a[0] = 1;
  f1.nBits = 1;
  int k = 2;
  while (true)
  {
    f2 = f0 + f1;//依次计算斐波那契数列的各项
    ++k;
    if (f2.nBits >= 1000)//首次出现位数大于等于1000的项
      break;
    f0 = f1;
    f1 = f2;
  }
  cout << k << endl;
  return 0;
}

guosl

其实这个题目还有一种用数学方式来求解。斐波那契数列的递推公式为f3=f2+f1，f1=1,f2=1。我们可以根据这个递推公式得到这个序列的特征方程x^2-x-1=0，然后得到其通项公式：
f(n)=1/sqrt(5)*((1+sqrt(5))/2)^n-(1-sqrt(5))/2)^n)。又由于abs((1-sqrt(5))/2)/sqrt(5))<1，所以其十进制下的位数有((1+sqrt(5))/2)^n)/sqrt(5)决定，所以就有下面的代码：

#include <iostream>
#include <cmath>
using namespace std;

int main(void)
{
  double t = 999.0 + 0.5 * log10(5.0);
  t /= log10(sqrt(5.0) + 1.0) - log10(2.0);
  int k = int(t);
  if ((k & 1) == 1)
    cout << ceil(t) << endl;
  else
    cout << floor(t) << endl;
  return 0;
}

jungestory

#include<iostream>
using namespace std;

void fib(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;
            if(i == n2[0]){
                n2[0]++;
            }
        }
    }
}

int main(){
    int num[2][1005] = {{1, 1}, {1, 1}}, a = 0, b = 1;
    for(int i = 3; 1; i++){
        fib(num[a], num[b]);
        if(num[b][0] >= 1000){
            cout << i << endl;
            break;
        }

        swap(a, b);
    }

    return 0;
}