题目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

1. def fbnq(x,y):
   
2.     return x+y
   
3. x,y=1,1
   
4. z=0
   
5. i=2
   
6. while len(str(z))<1000:
   
7.     i+=1
   
8.     z=fbnq(x,y)
   
9.     x,y=y,z
   
10. 
    
11. print(i,z)
    

复制代码

4782

Plusenxue

1. 
   
2. class Fibo():
   
3.     def __init__(self):
   
4.         self.x = 0
   
5.         self.y = 1
   
6.     def __iter__(self):
   
7.         return self
   
8.     def __next__(self):
   
9.         self.x,self.y = self.y,self.x+self.y
   
10.         return self.x
    
11. 
    
12. value = 0
    
13. number = 1
    
14. a = Fibo()
    
15. it = iter(a)
    
16. 
    
17. while len(str(value)) < 1000:
    
18.     value = next(it)
    
19.     number += 1
    
20. 
    
21. print(number)
    

复制代码

愤怒的大头菇

1. a=1;b=1
   
2. count = 0
   
3. while len(str(a))< 1000:
   
4.       
   
5.       a,b=b,a+b
   
6.       count += 1
   
7. print(count+1)
   

复制代码

答案4782

jerryxjr1220

1. 4782
   
2. [Finished in 0.1s]
   
3. 这题属于送分题

复制代码

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

复制代码

芒果加黄桃

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

复制代码

渡风

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

1. %% Problem25
   
2. % 题目25:第一个包含1000个数字的斐波那契数列是第几项？       
   
3. function Output=Problem25(Input)
   
4. tic
   
5. if nargin==0
   
6. Input=1000;
   
7. end
   
8. F1=1;
   
9. F2=1;
   
10. Num=2;
    
11. Sum=1;
    
12. while (Sum<Input)
    
13.     Num=Num+1;
    
14.     F3=Vector_Plus(F1,F2);
    
15.     F1=F2;
    
16.     F2=F3;
    
17.     Sum=length(F3);
    
18. end
    
19. Output=Num;
    
20. toc
    
21. disp('此代码使用matlab编程')
    
22. disp(['Problem25所用时间为',num2str(toc),'秒'])
    
23. disp(['Problem25的答案为',num2str(Output)])
    
24. end
    
25. %% 子程序
    
26. %此程序实现两个向量的加法
    
27. function Output=Vector_Plus(a,b)
    
28. if nargin==0
    
29.     a=[9 9 9 9 9 9 ];
    
30.     b=[2 0];
    
31. end
    
32. L1=length(a);
    
33. L2=length(b);
    
34. L=max(L1,L2);
    
35. if L1<L2
    
36.    Span=L2-L1;
    
37.    Newa=[zeros(1,Span),a];
    
38.    Newb=b;
    
39. elseif L1>L2
    
40.    Span=L1-L2;
    
41.    Newa=a;
    
42.    Newb=[zeros(1,Span),b];
    
43. else
    
44.     Newa=a;
    
45.     Newb=b;
    
46. end
    
47. Rank=Newa+Newb;
    
48. for ii=L:-1:2
    
49.     if Rank(ii)>=10
    
50.         Rank(ii)=Rank(ii)-10;
    
51.         Rank(ii-1)=Rank(ii-1)+1;
    
52.     end
    
53. end
    
54. Biggest=0;
    
55. while (Rank(1)>=10)
    
56.     if Rank(1)>=10
    
57.        Rank(1)=Rank(1)-10;
    
58.        Biggest=Biggest+1;
    
59.     end
    
60. end
    
61. if Biggest>0
    
62.     Output=[Biggest,Rank];
    
63. else
    
64.     Output=Rank;
    
65. end
    
66. 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

1. l_fib=[0,1,1]
   
2. a=b=1
   
3. while 1:
   
4.     a=a+b
   
5.     l_fib.append(a)
   
6.     if len(str(a))>=1000:
   
7.         break
   
8.     b=a+b
   
9.     l_fib.append(b)
   
10.     if len(str(b))>=1000:
    
11.         break
    
12. print(l_fib.index(max(l_fib)))

复制代码

>>>
4782

看了大家的后，优化为：

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

复制代码

marmot

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

复制代码

进击的小蜗牛

1. f1 = 1
   
2. f2 = 1
   
3. n = 2
   
4. while True:
   
5.     f3 = f1 + f2
   
6.     f1,f2 = f2,f3
   
7.     n += 1
   
8.     if len(str(f3)) == 1000:
   
9.         break
   
10. print(n)

复制代码

结果：4782

王小召

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

1. def Fab():
   
2.     a, b = 1, 0
   
3.     while True:
   
4.         yield a
   
5.         a, b = a+b, a
   
6. 
   
7. if __name__ == "__main__":
   
8.     count = 1
   
9.     for i in Fab():
   
10.         if len(str(i)) >= 1000:
    
11.             print("第一个超过1000项的是第：{}项".format(count))
    
12.             break
    
13.         else:
    
14.             count += 1

复制代码

永恒的蓝色梦想

1. count = 1
   
2. a = 0
   
3. b = 1
   
4. 
   
5. 
   
6. while len(str(b)) < 1000:
   
7.     a, b = b, a + b
   
8.     count += 1
   
9. 
   
10. 
    
11. print(count)

复制代码

4444567

1. a = 1
   
2. b = 1
   
3. i = 2
   
4. while True:
   
5.     a = a + b
   
6.     i += 1
   
7.     if len(str(a)) >= 1000:
   
8.         print('是a',a,i)
   
9.         break
   
10.     b = b + a
    
11.     i += 1
    
12.     if len(str(b)) >= 1000:
    
13.         print('是b',b,i)
    
14.         break
    
15.    

复制代码

有马_冬巳

1. '''斐波那契数列中第一个包含 1000 位数字的项是第几项？'''
   
2. 
   
3. start = time.time()
   
4. 
   
5. f1 = 1
   
6. f2 = 1
   
7. fn = 0
   
8. n = 2
   
9. while len(str(fn)) < 1000:
   
10.     if n % 2 == 0:
    
11.         n += 1
    
12.         f1 = f1 + f2
    
13.         fn = f1
    
14.     elif n % 2 == 1:
    
15.         n += 1
    
16.         f2 = f1 + f2
    
17.         fn = f2
    
18. print("第一个包含1000为数字的项是第%d项" %n)
    
19. #print("这个项的值为: %d" %fn)
    
20. 
    
21. end = time.time()
    
22. print("共用时%f秒" %(end - start))

复制代码

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

a1351468657

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. main()
   
5. {
   
6.         char num1[1100] = "1", num2[1100] = "1", temp[1100];
   
7.        
   
8.         int i, j;
   
9.         int a, b, c, d, e = 0, f, count = 0;
   
10.         while (strlen(num2) < 1000)
    
11.         {
    
12.                 strcpy(temp, num2);
    
13.                 j = strlen(num1);
    
14.                 for (i = 0; i < j; i++)//让num1和num2相加并存到num2中
    
15.                 {
    
16.                         a = num1[i] - '0';
    
17.                         b = num2[i] - '0';
    
18.                         c = a + b;
    
19.                         d = (c + e) % 10;
    
20. 
    
21.                         num2[i] = d + '0';
    
22.                         e = (c + e)/ 10;
    
23.                 }
    
24.                 while (e)//此时还有进位
    
25.                 {
    
26.                         if (num2[i] != NULL)
    
27.                         {
    
28.                                 f = num2[i] - '0';
    
29.                                 f += e;
    
30.                                 num2[i] = f + '0';
    
31.                
    
32.                         }
    
33.                         else
    
34.                         {
    
35.                                 num2[i] = e + '0';
    
36.                         }
    
37.                         e /= 10;
    
38.                         i++;
    
39.                 }
    
40.                 if (num2[i] == NULL)//添加结束符
    
41.                 {
    
42.                         num2[i] = '\0';
    
43.                 }
    
44.                 else
    
45.                 {
    
46.                         num2[i + 1] = '\0';
    
47.                 }
    
48. 
    
49. 
    
50.                 strcpy(num1, temp);//将上一个num2的值给num1
    
51.                
    
52.                 count++;//记录项数
    
53.         }
    
54.        
    
55.         printf("\n%d\n", count + 2);
    
56. }

复制代码

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

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

1. /*
   
2. 答案：4782
   
3. 耗时：0.0103192秒
   
4. */
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. #include <cstring>
   
8. using namespace std;
   
9. 
   
10. struct stBigInt//高精度数字类
    
11. {
    
12.   unsigned char a[1100];//存放具体的各位数字
    
13.   int nBits;//该高精度数的位数
    
14.   stBigInt(void)//构造函数
    
15.   {
    
16.     memset(a, 0, sizeof(a));
    
17.     nBits = 0;
    
18.   }
    
19.   stBigInt(const stBigInt& x)//复制构造函数
    
20.   {
    
21.     memcpy(a, x.a, sizeof(a));
    
22.     nBits = x.nBits;
    
23.   }
    
24.   const stBigInt& operator=(const stBigInt& x)//重载=运算符
    
25.   {
    
26.     memcpy(a, x.a, sizeof(a));
    
27.     nBits = x.nBits;
    
28.     return *this;
    
29.   }
    
30.   stBigInt operator+(const stBigInt x) const//重载+运算符
    
31.   {
    
32.     int bs = max(nBits, x.nBits);
    
33.     stBigInt y;
    
34.     unsigned char s = 0;
    
35.     for (int i = 0; i < bs; ++i)
    
36.     {
    
37.       s += a[i] + x.a[i];
    
38.       y.a[i] = s % 10;
    
39.       s = s / 10;
    
40.     }
    
41.     if (s > 0)
    
42.       y.a[bs++] = s;
    
43.     y.nBits = bs;
    
44.     return y;
    
45.   }
    
46. };
    
47. 
    
48. int main(void)
    
49. {
    
50.   stBigInt f0, f1, f2;
    
51.   f0.a[0] = 1;
    
52.   f0.nBits = 1;
    
53.   f1.a[0] = 1;
    
54.   f1.nBits = 1;
    
55.   int k = 2;
    
56.   while (true)
    
57.   {
    
58.     f2 = f0 + f1;//依次计算斐波那契数列的各项
    
59.     ++k;
    
60.     if (f2.nBits >= 1000)//首次出现位数大于等于1000的项
    
61.       break;
    
62.     f0 = f1;
    
63.     f1 = f2;
    
64.   }
    
65.   cout << k << endl;
    
66.   return 0;
    
67. }

复制代码

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)决定，所以就有下面的代码：

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. int main(void)
   
6. {
   
7.   double t = 999.0 + 0.5 * log10(5.0);
   
8.   t /= log10(sqrt(5.0) + 1.0) - log10(2.0);
   
9.   int k = int(t);
   
10.   if ((k & 1) == 1)
    
11.     cout << ceil(t) << endl;
    
12.   else
    
13.     cout << floor(t) << endl;
    
14.   return 0;
    
15. }

复制代码

jungestory

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. void fib(int *n1, int *n2){
   
5.     n2[0] = n1[0];
   
6.     for(int i = 1; i <= n2[0]; i++){
   
7.         n2[i] += n1[i];
   
8.         if(n2[i] > 9) {
   
9.             n2[i + 1]++;
   
10.             n2[i] -= 10;
    
11.             if(i == n2[0]){
    
12.                 n2[0]++;
    
13.             }
    
14.         }
    
15.     }
    
16. }
    
17. 
    
18. int main(){
    
19.     int num[2][1005] = {{1, 1}, {1, 1}}, a = 0, b = 1;
    
20.     for(int i = 3; 1; i++){
    
21.         fib(num[a], num[b]);
    
22.         if(num[b][0] >= 1000){
    
23.             cout << i << endl;
    
24.             break;
    
25.         }
    
26. 
    
27.         swap(a, b);
    
28.     }
    
29. 
    
30.     return 0;
    
31. }

复制代码