论坛 › 欧拉计划（Project Euler） › 题目25：第一个包含1000位数字的斐波那契数列项是第几项？

欧拉计划 发表于 2015-4-23 16:37:42

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

本帖最后由 欧拉计划 于 2015-4-23 21:23 编辑

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 发表于 2016-6-19 10:04:55

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 发表于 2016-8-27 20:25:42

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)

愤怒的大头菇 发表于 2016-8-29 22:45:47

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


答案4782

jerryxjr1220 发表于 2016-9-20 17:44:38

4782

这题属于送分题
fib =
for a in range(1, 10000):
        fib.append (fib+fib)
        if len (str(fib[-1])) >= 1000:
                print (a+1)
                exit()

芒果加黄桃 发表于 2017-1-12 14:41:03

本帖最后由 芒果加黄桃 于 2017-1-12 14:44 编辑

# 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))

渡风 发表于 2017-1-22 13:30:33

此代码使用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=;
    b=;
end
L1=length(a);
L2=length(b);
L=max(L1,L2);
if L1<L2
   Span=L2-L1;
   Newa=;
   Newb=b;
elseif L1>L2
   Span=L1-L2;
   Newa=a;
   Newb=;
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=;
else
    Output=Rank;
end
end

testabc123 发表于 2017-3-10 14:35:41

def Ss():
    lista=
    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 发表于 2017-3-15 15:44:42

本帖最后由 99592938 于 2017-3-15 15:51 编辑

l_fib=
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=
while 1:
    fib.append(fib[-2]+fib[-1])
    if len(str(fib[-1]))>=1000:break
print(fib.index(fib[-1]))

marmot 发表于 2017-3-17 19:20:40

list_feb =
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

进击的小蜗牛 发表于 2017-5-24 09:38:22

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

王小召 发表于 2019-6-12 09:42:30

第一个超过1000项的是第：4782def 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

永恒的蓝色梦想 发表于 2020-9-11 13:50:38

count = 1
a = 0
b = 1


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


print(count)

4444567 发表于 2020-9-19 21:38:06

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
   

有马_冬巳 发表于 2020-10-21 16:12:44

'''斐波那契数列中第一个包含 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 发表于 2021-3-12 10:47:37

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

main()
{
        char num1 = "1", num2 = "1", temp;
       
        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 - '0';
                        b = num2 - '0';
                        c = a + b;
                        d = (c + e) % 10;

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


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

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

ft215378 发表于 2021-10-16 19:39:29

#第一个包含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 发表于 2022-1-2 21:13:29

本帖最后由 guosl 于 2022-1-2 21:15 编辑

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

struct stBigInt//高精度数字类
{
unsigned char a;//存放具体的各位数字
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 + x.a;
      y.a = s % 10;
      s = s / 10;
    }
    if (s > 0)
      y.a = s;
    y.nBits = bs;
    return y;
}
};

int main(void)
{
stBigInt f0, f1, f2;
f0.a = 1;
f0.nBits = 1;
f1.a = 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 发表于 2022-1-3 08:54:30

本帖最后由 guosl 于 2022-1-3 08:57 编辑

其实这个题目还有一种用数学方式来求解。斐波那契数列的递推公式为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 发表于 2022-5-27 18:33:00

#include<iostream>
using namespace std;

void fib(int *n1, int *n2){
    n2 = n1;
    for(int i = 1; i <= n2; i++){
      n2 += n1;
      if(n2 > 9) {
            n2++;
            n2 -= 10;
            if(i == n2){
                n2++;
            }
      }
    }
}

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

      swap(a, b);
    }

    return 0;
}

查看完整版本: 题目25：第一个包含1000位数字的斐波那契数列项是第几项？