鱼C论坛

 找回密码
 立即注册
查看: 4878|回复: 20

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

[复制链接]
发表于 2015-4-23 16:37:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 欧拉计划 于 2015-4-23 21:23 编辑
1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

BaiduShurufa_2015-4-23_21-19-42.png

Hence the first 12 terms will be:

BaiduShurufa_2015-4-23_21-20-8.png

The 12th term, BaiduShurufa_2015-4-23_21-20-34.png , is the first term to contain three digits.

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

题目:

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

BaiduShurufa_2015-4-23_21-19-42.png

那么其 12 项为:

BaiduShurufa_2015-4-23_21-20-8.png

因此第 12 项, BaiduShurufa_2015-4-23_21-20-34.png ,是第一个包含三位数字的项。

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

评分

参与人数 1贡献 +1 收起 理由
cwhsmile + 1 这题简单

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-6-19 10:04:55 | 显示全部楼层
  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. print(i,z)
复制代码


4782
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-27 20:25:42 | 显示全部楼层

  1. class Fibo():
  2.     def __init__(self):
  3.         self.x = 0
  4.         self.y = 1
  5.     def __iter__(self):
  6.         return self
  7.     def __next__(self):
  8.         self.x,self.y = self.y,self.x+self.y
  9.         return self.x

  10. value = 0
  11. number = 1
  12. a = Fibo()
  13. it = iter(a)

  14. while len(str(value)) < 1000:
  15.     value = next(it)
  16.     number += 1

  17. print(number)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-29 22:45:47 | 显示全部楼层
  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
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-9-20 17:44:38 | 显示全部楼层
  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()
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-12 14:41:03 | 显示全部楼层
本帖最后由 芒果加黄桃 于 2017-1-12 14:44 编辑
  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))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-22 13:30:33 | 显示全部楼层
此代码使用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
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-10 14:35:41 | 显示全部楼层
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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-15 15:44:42 | 显示全部楼层
本帖最后由 99592938 于 2017-3-15 15:51 编辑
  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]))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-17 19:20:40 | 显示全部楼层
  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
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-24 09:38:22 | 显示全部楼层
  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
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-6-12 09:42:30 | 显示全部楼层
第一个超过1000项的是第:4782
  1. def Fab():
  2.     a, b = 1, 0
  3.     while True:
  4.         yield a
  5.         a, b = a+b, a

  6. if __name__ == "__main__":
  7.     count = 1
  8.     for i in Fab():
  9.         if len(str(i)) >= 1000:
  10.             print("第一个超过1000项的是第:{}项".format(count))
  11.             break
  12.         else:
  13.             count += 1
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-9-11 13:50:38 | 显示全部楼层
  1. count = 1
  2. a = 0
  3. b = 1


  4. while len(str(b)) < 1000:
  5.     a, b = b, a + b
  6.     count += 1


  7. print(count)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-9-19 21:38:06 | 显示全部楼层
  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.    
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-10-21 16:12:44 | 显示全部楼层
  1. '''斐波那契数列中第一个包含 1000 位数字的项是第几项?'''

  2. start = time.time()

  3. f1 = 1
  4. f2 = 1
  5. fn = 0
  6. n = 2
  7. while len(str(fn)) < 1000:
  8.     if n % 2 == 0:
  9.         n += 1
  10.         f1 = f1 + f2
  11.         fn = f1
  12.     elif n % 2 == 1:
  13.         n += 1
  14.         f2 = f1 + f2
  15.         fn = f2
  16. print("第一个包含1000为数字的项是第%d项" %n)
  17. #print("这个项的值为: %d" %fn)

  18. end = time.time()
  19. print("共用时%f秒" %(end - start))
复制代码


第一个包含1000为数字的项是第4782项
共用时0.031272秒
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-3-12 10:47:37 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <string.h>

  3. main()
  4. {
  5.         char num1[1100] = "1", num2[1100] = "1", temp[1100];
  6.        
  7.         int i, j;
  8.         int a, b, c, d, e = 0, f, count = 0;
  9.         while (strlen(num2) < 1000)
  10.         {
  11.                 strcpy(temp, num2);
  12.                 j = strlen(num1);
  13.                 for (i = 0; i < j; i++)//让num1和num2相加并存到num2中
  14.                 {
  15.                         a = num1[i] - '0';
  16.                         b = num2[i] - '0';
  17.                         c = a + b;
  18.                         d = (c + e) % 10;

  19.                         num2[i] = d + '0';
  20.                         e = (c + e)/ 10;
  21.                 }
  22.                 while (e)//此时还有进位
  23.                 {
  24.                         if (num2[i] != NULL)
  25.                         {
  26.                                 f = num2[i] - '0';
  27.                                 f += e;
  28.                                 num2[i] = f + '0';
  29.                
  30.                         }
  31.                         else
  32.                         {
  33.                                 num2[i] = e + '0';
  34.                         }
  35.                         e /= 10;
  36.                         i++;
  37.                 }
  38.                 if (num2[i] == NULL)//添加结束符
  39.                 {
  40.                         num2[i] = '\0';
  41.                 }
  42.                 else
  43.                 {
  44.                         num2[i + 1] = '\0';
  45.                 }


  46.                 strcpy(num1, temp);//将上一个num2的值给num1
  47.                
  48.                 count++;//记录项数
  49.         }
  50.        
  51.         printf("\n%d\n", count + 2);
  52. }
复制代码


大佬帮我看看还有没有可以优化的地方,谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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))
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-1-2 21:13:29 | 显示全部楼层
本帖最后由 guosl 于 2022-1-2 21:15 编辑
  1. /*
  2. 答案:4782
  3. 耗时:0.0103192秒
  4. */
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstring>
  8. using namespace std;

  9. struct stBigInt//高精度数字类
  10. {
  11.   unsigned char a[1100];//存放具体的各位数字
  12.   int nBits;//该高精度数的位数
  13.   stBigInt(void)//构造函数
  14.   {
  15.     memset(a, 0, sizeof(a));
  16.     nBits = 0;
  17.   }
  18.   stBigInt(const stBigInt& x)//复制构造函数
  19.   {
  20.     memcpy(a, x.a, sizeof(a));
  21.     nBits = x.nBits;
  22.   }
  23.   const stBigInt& operator=(const stBigInt& x)//重载=运算符
  24.   {
  25.     memcpy(a, x.a, sizeof(a));
  26.     nBits = x.nBits;
  27.     return *this;
  28.   }
  29.   stBigInt operator+(const stBigInt x) const//重载+运算符
  30.   {
  31.     int bs = max(nBits, x.nBits);
  32.     stBigInt y;
  33.     unsigned char s = 0;
  34.     for (int i = 0; i < bs; ++i)
  35.     {
  36.       s += a[i] + x.a[i];
  37.       y.a[i] = s % 10;
  38.       s = s / 10;
  39.     }
  40.     if (s > 0)
  41.       y.a[bs++] = s;
  42.     y.nBits = bs;
  43.     return y;
  44.   }
  45. };

  46. int main(void)
  47. {
  48.   stBigInt f0, f1, f2;
  49.   f0.a[0] = 1;
  50.   f0.nBits = 1;
  51.   f1.a[0] = 1;
  52.   f1.nBits = 1;
  53.   int k = 2;
  54.   while (true)
  55.   {
  56.     f2 = f0 + f1;//依次计算斐波那契数列的各项
  57.     ++k;
  58.     if (f2.nBits >= 1000)//首次出现位数大于等于1000的项
  59.       break;
  60.     f0 = f1;
  61.     f1 = f2;
  62.   }
  63.   cout << k << endl;
  64.   return 0;
  65. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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)决定,所以就有下面的代码:
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;

  4. int main(void)
  5. {
  6.   double t = 999.0 + 0.5 * log10(5.0);
  7.   t /= log10(sqrt(5.0) + 1.0) - log10(2.0);
  8.   int k = int(t);
  9.   if ((k & 1) == 1)
  10.     cout << ceil(t) << endl;
  11.   else
  12.     cout << floor(t) << endl;
  13.   return 0;
  14. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-5-27 18:33:00 | 显示全部楼层
  1. #include<iostream>
  2. using namespace std;

  3. void fib(int *n1, int *n2){
  4.     n2[0] = n1[0];
  5.     for(int i = 1; i <= n2[0]; i++){
  6.         n2[i] += n1[i];
  7.         if(n2[i] > 9) {
  8.             n2[i + 1]++;
  9.             n2[i] -= 10;
  10.             if(i == n2[0]){
  11.                 n2[0]++;
  12.             }
  13.         }
  14.     }
  15. }

  16. int main(){
  17.     int num[2][1005] = {{1, 1}, {1, 1}}, a = 0, b = 1;
  18.     for(int i = 3; 1; i++){
  19.         fib(num[a], num[b]);
  20.         if(num[b][0] >= 1000){
  21.             cout << i << endl;
  22.             break;
  23.         }

  24.         swap(a, b);
  25.     }

  26.     return 0;
  27. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表