斐波那契数列 订阅
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。 展开全文
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。
信息
别    称
黄金分割数列、兔子数列
表达式
F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
提出者
莱昂纳多·斐波那契
C语言中
FIB数列
应用学科
数学
中文名
斐波那契数列
适用领域范围
代数
外文名
Fibonacci sequence
提出时间
1202年
斐波那契数列定义
斐波那契数列指的是这样一个数列: 这个数列从第3项开始,每一项都等于前两项之和。斐波那契数列的定义者,是意大利数学家莱昂纳多·斐波那契(Leonardo Fibonacci),生于公元1170年,卒于1250年,籍贯是比萨。他被人称作“比萨的莱昂纳多”。1202年,他撰写了《算盘全书》(Liber Abacci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事,派驻地点于阿尔及利亚地区,莱昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。另外斐波纳契还在计算机C语言程序题中应用广泛
收起全文
精华内容
参与话题
问答
  • 斐波那契数列

    千次阅读 2014-11-16 21:55:19
    斐波那契数列”的两种算法: 斐波那契数列有个规律:从第三个数开始,每个数是前两个数之和,比如: 1 1 2 3 5 8 13 21 34 55...... 接下来使用两种方法来实现这个算法。 方法1:递归 static void Main...
    “斐波那契数列”的两种算法:
    斐波那契数列有个规律:从第三个数开始,每个数是前两个数之和,比如:

    1 1 2 3 5 8 13 21 34 55......

    接下来使用两种方法来实现这个算法。

    方法1:递归

      static void Main(string[] args)
            {
                Console.WriteLine("Place Input Fibonacci start number:");
                int n = int.Parse(Console.ReadLine());
                Console.WriteLine("递归的结果:" + F(n));
            }
    
            public static int F(int n)
            {
                if (n < 1)//判断开始的数据必须大于一
                {
                    Console.WriteLine(" Place Input a number greater than 1");
                    return 0;
                }
                if (n == 1 || n == 2)
                    return 1;
                else
                    return (F(n - 1) + F(n - 2));
            }

    方法二:循环方式

      static void Main(string[] args)
            {
                Console.WriteLine("Place Input Fibonacci start number:");
                int n = int.Parse(Console.ReadLine());
                Console.WriteLine("循环的结果:" + FC(n));
            }<pre name="code" class="csharp">public static int FC(int n)
            {
                int x1 = 1, x2 = 1;
                int num=0;
                for (int i = 3; i <= n; i++)
                {
                    num = x1 + x2;
                    x1 = x2;
                    x2 = num;
                }
                return num;
            }
    
    

    结果为:


    展开全文
  • 斐波那契数列介绍及Python中五种方法斐波那契数列

    万次阅读 多人点赞 2018-10-31 20:07:28
    Q:斐波那契数列为什么那么重要,所有关于数学的书几乎都会提到? A:因为斐波那契数列在数学和生活以及自然界中都非常有用。 1. 斐波那契数列 概念引入 斐波那契数列(Fibonacci sequence),又称黄金分割数列,...

    Q:斐波那契数列为什么那么重要,所有关于数学的书几乎都会提到?
    A:因为斐波那契数列在数学和生活以及自然界中都非常有用。

    在这里插入图片描述

    1. 斐波那契数列 概念引入

    斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。

    数学上,斐波那契数列以递归的形式进行定义:
    F0=0F1=1Fn=Fn1+Fn2F_{0} = 0\\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2}

    场景

    先来开看看“兔子数列”以及其他数学应用场景!!

    1. 1 兔子数列

    一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?

    在这里插入图片描述

    1.2 排列组合

    有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

    更多数学方面知识,请戳:
    斐波那契数列

    斐波那契数列为什么那么重要,所有关于数学的书几乎都会提到?

    2. 数列数学方法解答

    2.1 兔子繁殖问题

    斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。

    一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?

    我们不妨拿新出生的一对小兔子分析一下:

    第一个月小兔子没有繁殖能力,所以还是一对

    两个月后,生下一对小兔对数共有两对

    三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对

    ------

    依次类推可以列出下表:

    经过月数 1 2 3 4 5 6 7 8 9 10 11 12
    幼仔对数 1 0 1 1 2 3 5 8 13 21 34 55
    成兔对数 0 1 1 2 3 5 8 13 21 34 55 89
    总体对数 1 1 2 3 5 8 13 21 34 55 89 144

    幼仔对数=前月成兔对数

    成兔对数=前月成兔对数+前月幼仔对数

    总体对数=本月成兔对数+本月幼仔对数

    可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:

    前面相邻两项之和,构成了后一项。

    2.2 排列组合
    2.2.1 跨楼梯组合

    有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

    这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法……

    1,2,3,5,8,13……所以,登上十级,有89种走法。

    2.2.2 掷硬币不连续情形

    一枚均匀的硬币掷10次,问不连续出现正面的可能情形有多少种?

    答案是:
    1/5)[(1+5)/2](10+2)[(15)/2](10+2)=144(1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144

    3. Python代码实现斐波那契数列

    时间复杂度

    空间复杂度

    通过时间复杂度空间复杂度评判代码的执行效率。

    • 例如:从规模上来说,如果需要计算F(4)的值,需要进行9次元素操作

      设T(n)为计算n的时间复杂度,那么
      T(n)=T(n1)+T(n2)+O(1)T(n) = T(n-1) + T(n-2)+O(1)
      一般情况,可以得出:T(n)&lt;2T(n1)+O(1)T(n)&lt; 2* T(n-1) + O(1)

      粗略估算,Tn&lt;O2nT(n) &lt; O(2^n),上述代码求解F(n)的计算,它的时间复杂度是$O(2^n)

    3.1 python特有写法

    打印正整数n之内的斐波那契数列

    # Python特有, 常规写法
    def fib(self, n):
    	a = 0
    	b = 1
    	while a <= n:
    		print(a, end=" ", flush=True)
    		a, b = b, a + b  # python不借助变量交换两数的值
    
    fib(100)  # 求n之内的斐波那契数列
    

    O(n)O(1)时间复杂度:O(n), 空间复杂度:O(1)

    3.2 递归

    打印斐波那契数列前10位数字

    # 递归
    def fibonacci(i):
        num_list = [0, 1]
        if i < 2:
            return num_list[i]
        elif i >= 2:
            return (fibonacci(i - 2) + fibonacci(i - 1))
    
    
    print(fibonacci(10))
    

    O(n)O(n)时间复杂度:O(n), 空间复杂度:O(n)

    3.3 类对象
    # 迭代的方式
    class FibIterator(object):
        """斐波那契数列迭代器"""
        def __init__(self, n):
            """
            :param n: int, 指明生成数列的前n个数
            """
            self.n = n
            # current用来保存当前生成到数列中的第几个数了
            self.current = 0
            # num1用来保存前前一个数,初始值为数列中的第一个数0
            self.num1 = 0
            # num2用来保存前一个数,初始值为数列中的第二个数1
            self.num2 = 1
    
        def __next__(self):
            """被next()函数调用来获取下一个数"""
            if self.current < self.n:
                num = self.num1
                self.num1, self.num2 = self.num2, self.num1+self.num2
                self.current += 1
                return num
            else:
                raise StopIteration
    
        def __iter__(self):
            """迭代器的__iter__返回自身即可"""
            return self
    
    
    if __name__ == '__main__':
        fib = FibIterator(10)
        for num in fib:
            print(num, end=" ")
    
    3.4 矩阵解决问题

    从定义开始:
    F0=0F1=1Fn=Fn1+Fn2F_{0} = 0\\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2}
    转化为矩阵形式
    (Fn+1Fn)=(1110)(FnFn1)\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} 1&amp;1\\ 1&amp;0 \end{pmatrix}* \begin{pmatrix} F_{n}\\ F_{n-1} \end{pmatrix}
    可以得出:(Fn+1Fn)(1110)(F1F0)\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}\begin{pmatrix} 1&amp;1\\ 1&amp;0 \end{pmatrix}\begin{pmatrix} F_{1}\\ F_{0} \end{pmatrix}
    我们设定
    A=(1110)A=\begin{pmatrix} 1&amp;1\\ 1&amp;0 \end{pmatrix}
    很显然可以变为如下:
    A=(F2F1F1F0)A=\begin{pmatrix} F_{2}&amp;F_{1}\\ F_{1}&amp;F_{0} \end{pmatrix}
    通过数学归纳法可以推出以下公式:
    An=(Fn+1FnFnFn1)=(1110)nA^{n}=\begin{pmatrix} F_{n+1}&amp;F_{n}\\ F_{n}&amp;F_{n-1} \end{pmatrix}= \begin{pmatrix} 1&amp;1\\ 1&amp;0 \end{pmatrix}^{n}
    很显然计算F(n)的值,只需要进行矩阵的n次幂运算,取出结果矩阵第二行第一个元素值即可
    O(n)O(1)时间复杂度:O(n), 空间复杂度:O(1)

    这里可以利用快速幂运算求解,假设计算A的N次幂,二阶矩阵的乘法满足结合律

    设A,B,C都是任意的二阶矩阵,则
    A(BC)=(AB)CA(BC)=(AB)C

    我们设定:m=[n2]m=[\frac{n}{2}]

    • 当n为偶数: AN=AmAmA^{N}=A^{m}∗A^{m}

    • 当n为奇数: AN=AmAmAA^{N}=A^{m}∗A^{m}∗A

      相当于A6=A3A3A7=A3A3AA^{6}=A^3∗A^3,A^7=A^3∗A^3∗A

    这样可以减少计算次数,因为A6=AAAAAAA6=A∗A∗A∗A∗A∗A这里有5个乘,A6=AAAAAAA6=(A∗A∗A)∗(A∗A∗A) 计算完AAAA*A*A 得到结果A3A^3,再乘以A3A^3 这里用了3个乘

    以下是普通数据的快速幂运算,运算改为矩阵乘法,ret改为单位矩阵即可

    def qpow(base, exp):
        if exp == 0:
            return 1
        ret = 1
        while exp:
            if exp & 1:
                ret = ret * base
            base = base * base
            exp >>= 1
        return ret
    

    3.5 矩阵再推导

    我们可以设定: n=2mn=2m
    那么
    A2m=(F2m+1F2mF2mF2m1)=AmAmA^{2m}=\begin{pmatrix} F_{2m+1}&amp;F_{2m}\\ F_{2m}&amp;F_{2m-1} \end{pmatrix}=A^{m}*A^{m}
    已知
    Am=(Fm+1FmFmFm1) A^{m}=\begin{pmatrix} F_{m+1}&amp;F_{m}\\ F_{m}&amp;F_{m-1} \end{pmatrix}
    所以:
    (Fm+1FmFmFm1)(Fm+1FmFmFm1)=(F2m+1F2mF2mF2m1) \begin{pmatrix} F_{m+1}&amp;F_{m}\\ F_{m}&amp;F_{m-1} \end{pmatrix}* \begin{pmatrix} F_{m+1}&amp;F_{m}\\ F_{m}&amp;F_{m-1} \end{pmatrix}= \begin{pmatrix} F_{2m+1}&amp;F_{2m}\\ F_{2m}&amp;F_{2m-1} \end{pmatrix}
    计算后可以得出:
    (F2m+1F2m)=(Fm+12+Fm2Fm(Fm+1+Fm1)) \begin{pmatrix} F_{2m+1}\\ F_{2m} \end{pmatrix}= \begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(F_{m+1}+F_{m-1}) \end{pmatrix}

    这里需要注意一点 n 需要进行奇偶性判定:

    • 当n为奇数时:m=[n2]n=2m+1m=[\frac{n}{2}],n=2*m+1 此时,(Fn+1Fn)(F2m+2F2m+1)(Fm+1(Fm+2+Fm)Fm+12+Fm2)\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}\begin{pmatrix} F_{2m+2}\\ F_{2m+1} \end{pmatrix}\begin{pmatrix} F_{m+1}*(F_{m+2}+F_{m})\\ F_{m+1}^{2}+F_{m}^{2} \end{pmatrix}
      由于 Fm+2=Fm+1+FmF_{m+2}=F_{m+1}+F_{m} ,因此,可以推导出
      (Fn+1Fn)=(Fm+1(Fm+1+2Fm)Fm+12+Fm2)\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} F_{m+1}*(F_{m+1}+2*F_{m})\\ F_{m+1}^{2}+F_{m}^{2} \end{pmatrix}
    • 当n为偶数时:m=n2n=2mm=\frac{n}{2},n=2*m,此时
      (Fn+1Fn)=(F2m+1F2m)=(Fm+12+Fm2Fm(Fm+1+Fm1))\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} F_{2m+1}\\ F_{2m} \end{pmatrix}= \begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(F_{m+1}+F_{m-1}) \end{pmatrix}
      由于 Fm+2=Fm+1+FmF_{m+2}=F_{m+1}+F_{m},因此,可以推导出:
      (Fn+1Fn)=(Fm+12+Fm2Fm(2Fm+1Fm))\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(2*F_{m+1}-F_{m}) \end{pmatrix}

    所以计算F(N)的值,只需要知道F(n/2+1)和F(n/2)即可

    def fib(n):
        if n < 1:
            return (1, 0)
    
        f_m_1, f_m = fib(n >> 1)
        if n & 1:
            return f_m_1 * (f_m_1 + 2 * f_m), f_m ** 2 + f_m_1 ** 2
        else:
            return f_m_1 ** 2 + f_m ** 2, f_m * (2 * f_m_1 - f_m)
    

    O(log2n)O(1)时间复杂度:O(\log_2 n), 空间复杂度:O(1)

    展开全文
  • Fibonacci数列就形如:0, 1, 1, 2, 3, 5, 8, 13, ...,在Fibonacci数列中的数我们称为Fibonacci数。给你一 个N,你想让其变为一个Fibonacci数,每一步你可以把当前数字X变为X-1或者X+1,现在给你一个数N求最少需要...

    题目描述:

    Fibonacci数列就形如:0, 1, 1, 2, 3, 5, 8, 13, ...,在Fibonacci数列中的数我们称为Fibonacci数。给你一 个N,你想让其变为一个Fibonacci数,每一步你可以把当前数字X变为X-1或者X+1,现在给你一个数N求最少需要多少步可以变为Fibonacci数。 

    输入描述:

    输入为一个正整数N(1 ≤ N ≤ 1,000,000)

    输出描述:

    输出一个最小的步数变为Fibonacci数

    示例:输入 15 输出 2

    代码实现:

    #include<stdlib.h>
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    
    int min(int a, int b){
    	if (a<b) {
    		return a;
    	}
    	else {
    		return b;
    	}
    }
    int main(){
    	int N, f, l = 0, r = 0, f0 = 0, f1 = 1;    
    	cin >> N;    
    	while (1){
    		f = f0 + f1;        
    		f0 = f1;        
    		f1 = f;        
    		//找到比N小且距离N最近的数,求出距离        
    		if(f < N)             
    			l = N-f;        
    		else { 
    			//找到比N大且距离N最近的数,求出距离            
    			r = f - N;            
    			break;        
    		}    
    	} 
    	//取最小距离    
    	cout << min(l,r) << endl;    
    	return 0; 
    } 

     

    展开全文
  • Fibonacci数列 斐波那契数列

    千次阅读 2019-11-21 17:51:57
    Fibonacci数列 Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。 输入格式 输入包含一个整数n。 输出格式 输出一行,包含一个整数,...

    Fibonacci数列

    Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
    当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
    输入格式
    输入包含一个整数n。
    输出格式
    输出一行,包含一个整数,表示Fn除以10007的余数。
    样例输入
    10
    样例输出
    55
    样例输入
    22
    样例输出
    7704
    数据规模与约定
    1 <= n <= 1,000,000。

    首先我们可以定义一个数组F,

    int F[1000000];
    

    由题可知

    F[1]=1;
    F[2]=1;
    

    输入一个N

    int n;
    scanf("%d",&n);
    

    当N<2时输出的就是1,所以

    if(n>2){(数据处理*)}
    

    设定一个循环,因为是从F[3]开始算起,所以for的判定条件为:
    int i=3;i<=n;i++

    Fn的计算就按题目给的Fn=Fn-1+Fn-2来计算。
    对于这部分,我们要想到对于结果的处理不能放到最后,因为int的最大值一定比F1,000,000要小数组100%会炸

    Boom!

    所以我们要在运算时就对每一次的结果进行处理。
    7%4=3
    3%4=3
    可知在运算时我们对斐波那契数列提前取余不会对结果产生影响。
    所以表达式变成了

    F[i]=(F[i-1]+F[i-2])%10007;
    

    以下是完整代码:

    #include<stdio.h>
    #define falg 10007
    main(){
    	int n;
    	scanf("%d",&n);
    	int F[n];
    	F[1]=1;
    	F[2]=1;
    	if(n>2){
    	for(int i=3;i<=n;i++){
    		F[i]=(F[i-1]+F[i-2])%falg;
    		}
    	}
    	printf("%d",F[n]);
    	return 0
    } 
    

    另附两个不同解法:
    这个是我的另一种解法占用空间较小但是算法更复杂

    #include<stdio.h>
    #define falg 10007
    #define M (a1+a2)
    main(){
    	int a1=1,a2=1,ans,n,i;
    	scanf("%d",&n);
    	if(n>2){
    		int bol =n%2;
    		n=(n-2)/2;
    		for(i=0;i<n;i++){
    			a1=M%falg;
    			a2=M%falg;	
    		}
    		if(bol==1){
    			a2=M%falg;
    		}
    	}
    
    	printf("%d\n",a2);
    	return 0; 
    } 
    

    引用自百度知道 殛丿殪 的回答

    #include<stdio.h>
    int main(void)
    {
    int x,y,z,i,n;
    x = 0;
    y = 0;
    z = 1;
    i = 0;
    scanf("%d",&n);
    while(i<n)
    {
    x=y;
    y=z;
    z=x+y;
    z=z%10007;
    i +=1;
    }
    y=y%10007;
    printf("%d",y);
    return 0;
    }
    
    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 23,338
精华内容 9,335
关键字:

斐波那契数列