精华内容
下载资源
问答
  • 斐波那契在很多题目里都会出现,解法也是有很多种,这里面列出三种用于加深对非递归,递归(函数式编程),尾递归的理解。 #! /usr/bin/env python #coding=utf-8 def Fib(n): a=1 b=1 n=n-1 while ...

    斐波那契在很多题目里都会出现,解法也是有很多种,这里面列出三种用于加深对 非递归递归(函数式编程),尾递归的理解。

    #! /usr/bin/env python
    #coding=utf-8
    def Fib(n):
        a=1
        b=1
        n=n-1
        while n>0:
            temp=a
            a=a+b
            b=temp
            n=n-1
        return a
    
    def Fib2(a):
        if a== 0 or a==1:
            return 1
        else:
            return Fib2(a-2)+Fib2(a-1)
        
    def Fib3(a,b,n):
        if n == 1:
            return b
        else:
            return Fib3(b,a+b,n-1)
    
    print Fib(5),Fib2(5),Fib3(1,1,5)

    结果如下:

    > "C:\Python27\pythonw.exe" -u "G:\P\fib.py" 
    8 8 8

    Fib,Fib2,Fib3分别对应上面三种方式。

     

    转载于:https://my.oschina.net/hebianxizao/blog/62328

    展开全文
  • * 斐波那契函数的递归实现 * * 1 1 2 3 5 8 13 21 */ public class FibonacciTest { private int []data; public FibonacciTest(int n) { data = new int[n]; } public static void main(String[] args)...
    /**
     * 斐波那契函数的递归实现
     *
     * 1 1 2 3 5 8 13 21
     */
    public class FibonacciTest {
    
        private int []data;
    
        public FibonacciTest(int n) {
            data = new int[n];
        }
    
        public static void main(String[] args) {
            FibonacciTest fib = new FibonacciTest(100);
            long startTime = System.currentTimeMillis();
            System.out.println(fib.fibonacci_1(30));
            long endTime = System.currentTimeMillis();
            System.out.println("fibonacci_1 cost " + (endTime - startTime) + "ms");
            System.out.println(fib.fibonacci_2(30));
            long endTime1 = System.currentTimeMillis();
            System.out.println("fibonacci_2 cost " + (endTime1 - endTime) + "ms");
            System.out.println(fib.fibonacci_3(1,1,30));
            long endTime2 = System.currentTimeMillis();
            System.out.println("fibonacci_3 cost " + (endTime2 - endTime1) + "ms");
        }
    
        /**
         * 递归函数,时间复杂度O(n^2)
         * @param n
         * @return
         */
        public int fibonacci_1(int n) {
            if (n <= 2) {
                return 1;
            }
            return fibonacci_1(n-1) + fibonacci_1(n-2);
        }
    
        /**
         * 采用缓存进行递归 时间复杂度O(n)
         * @param n
         * @return
         */
        public int fibonacci_2(int n) {
            if (n <= 2) {
                return 1;
            }
            int num = data[n];
            if (num > 0)
                return num;
            int res =  fibonacci_2(n-1) + fibonacci_2(n-2);
            data[n] = res;
            return res;
        }
    
        /**
         * 采用尾递归 时间复杂度O(n)
         * n的长度需要大于2
         * 计算是从前往后累加
         * @param n
         * @return
         */
        public int fibonacci_3(int pre, int pre_next, int n) {
            if (n <= 2) {
                return pre;
            }
            int new_pre_next = pre;
            int new_pre = pre_next +pre;
            return fibonacci_3(new_pre, new_pre_next, n-1);
        }
    
    }
    

     

    展开全文
  • 尾递归与斐波那契三种解法

    千次阅读 2018-04-08 23:00:57
    常规的斐波那契数列解法 int fib(int n) { if (n &lt;= 2) { return 1; } else return fib(n - 1) + fib(n - 2); } 要求第n个斐波那契数,子问题就是求每一个斐波那契数的前一项和前二项之和,典型的...

    常规的斐波那契数列解法

    int fib(int n) {
        if (n <= 2) {
            return 1;
        }
        else
            return fib(n - 1) + fib(n - 2);
    }

    要求第n个斐波那契数,子问题就是求每一个斐波那契数的前一项和前二项之和,典型的递归思想。

    这个算法的时间复杂度怎么算呢?

    递归的时间复杂度:递归次数*一次递归的基本语句执行次数

    递归的空间复杂度:在栈空间最大的临时变量个数

    如果求f(5),画出调用过程就是

                  f(5)
           f(4)          f(3)
        f(3)  f(2)      f(2) f(1)
    f(2) f(1)

    一个树状结构,先从f5->f4->f3-f2->f1->f2左子树就递归完了。每一个结点都是一次递归,每一个递归里只有一个基本语句,而结点书大约等与2^(N-2)常数忽略也就是2^N次递归调用,所以时间复杂度O(2^n).

    空间复杂度由图可以看出f5->f2之后递归f1,之后归值给f3,这时f2和f1的空间已经回收了,所以最大的空间占用也只是f5->f1, 即O(n)。

    循环优化斐波那契

    int fib(int n) {
        int pre = 1;
        int ppre = 0;
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            ret = pre + ppre;
            ppre = pre;
            pre = ret;
        }
        return ret;
    }

    循环迭代的精髓是每次计算的结果参与下次的计算,这种解法也是最优的,时间O(n),空间O(1).

    尾递归优化斐波那契

    int fib(int n, int ppre, int pre) {
        if (n <= 1)
            return ppre;
        return fib(n - 1, pre, ppre + pre);
    }
    int main()
    {
        int ret = fib(5, 1, 1);
    }

    递归调用返回的结果总被直接返回,则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言,而且从编译器角度来说,亦容易优化成为普通循环。这是因为从电脑的基本面来说,所有的循环都是利用重复移跳到代码的开头来实现的。

    尾递归的精髓就是吸取循环的精华——把每次计算的结果当作参数传递给下一次计算。

    调用过程如图,时间复杂度就是O(n),如果编译器优化空间复杂度O(1).
    这里写图片描述

    展开全文
  • 今天初夏将为大家带来计算斐波那契数列第n位的三种方法 第一种利用递归的方法计算,代码相当简单,但其重复计算率太高,导致其时间复杂度比指数还要爆炸式增长。不推荐此方法。但递归的思想却相当的重要还是要理解...

    斐波那契数列(Fibonaccisequnce),又称黄金分割数列。研究斐波那契数列有相当重要的价值,例在现代物理、准晶体结构、化学等领域都有直接的应用。因此研究斐波那契数列也是很有必要的。

    今天初夏将为大家带来计算斐波那契数列第n位的三种方法

    第一种利用递归的方法计算,代码相当简单,但其重复计算率太高,导致其时间复杂度比指数还要爆炸式增长。不推荐此方法。但递归的思想却相当的重要还是要理解并掌握。

    #include<Aventador_SQ.h>
    
    int  Fibonacci(int n)
    {
    	if (1 == n|| 2 == n)
    	{
    		return 1;
    	}
    	else
    	{
    		return Fibonacci(n - 1) + Fibonacci(n - 2);
    	}
    }
    int main()
    {
    	int n = 0;//求取第n个数
    	int	a = 0;//所求的数
    	scanf("%d", &n);
    	a=Fibonacci(n);
    	printf("第%d个数是%d\n",n,a);
    	system("pause");
    	return 0;
    }

    第二种是利用循环的方法,借助三个变量进行交换。其时间复杂度是O(n)

    #include<Aventador_SQ.h>
    
    void Fibonacci(int x)
    {
    	if (x < 1)
    	{
    		printf("输入错误!!!\n");
    	}
    	else if (x < 3)
    	{
    		printf("第%d个数是1\n", x );
    	}
    	else
    	{
    		int FiboOne = 1;
    		int FiboTwo = 1;
    		int FiboN = 0;
    		int i=0;
    		for (i = 3; i <= x; i++)
    		{
    			FiboN = FiboOne + FiboTwo;
    			FiboOne = FiboTwo;
    			FiboTwo = FiboN;
    			//printf("%d\t%d\n", i, FiboN);
    		}
    		printf("第%d个数是%d\n", x, FiboN);
    	}
    }
    int main()
    {
    	int n;
    	scanf("%d", &n);
    	Fibonacci(n);
    	system("pause");
    	return 0;
    }

    第三种到了最伤脑子的算法即矩阵,但运行速度大大提高。

    #include<Aventador_SQ.h>
    
    void Fibonacci(int x)
    {
    	int FFiboZero = 0, FiboZero = 0;
    	int FFiboOne = 1, FiboOne = 1;
    	int FFiboTwo = 1, FiboTwo = 1;
    	int FiboN = 0;
    
    	int i = 0;
    	for (i = 2; i <= (x / 2); i++)
    	{
    		FiboN = FFiboTwo * FiboTwo + FFiboOne * FiboOne;//利用矩阵求出待求得数字
    		//进行交换达到移动中间变量
    		FFiboZero = FFiboOne;
    		FFiboOne = FFiboTwo;
    		FFiboTwo = FiboN;
    	}
    	FiboN = FFiboTwo * FFiboTwo + FFiboOne * FFiboOne;//得到最终的所求取得数
    	printf("%d\t%d\n", x, FiboN);
    }
    
    void JFibonacci(int x)
    {
    	int FFiboZero = 0, FiboZero = 0;
    	int FFiboOne = 1, FiboOne = 1;
    	int FFiboTwo = 1, FiboTwo = 1;
    	int FiboN = 0;
    
    	int i = 0;
    	for (i = 2; i <= ((x - 1) / 2); i++)
    	{
    		FiboN = FFiboTwo * FiboTwo + FFiboOne * FiboOne;
    		FFiboZero = FFiboOne;
    		FFiboOne = FFiboTwo;
    		FFiboTwo = FiboN;
    	}
    	//当所求的位数是奇数时要另外计算第三种情况
    	FiboN = FFiboTwo * FFiboTwo + FFiboOne * FFiboOne;
    	FFiboTwo = FFiboTwo * FFiboOne + FFiboOne * FFiboZero;
    	FiboN = FiboN * FiboTwo + FFiboTwo * FiboOne;
    	printf("%d\t%d\n", x, FiboN);
    }
    
    int main()
    {
    	int n = 0;
    	printf("n位数:");
    	scanf("%d", &n);
    	if (n % 2 == 0)
    	{
    		JFibonacci(n);//n可以被2整除
    	}
    	else
    	{
    		Fibonacci(n);//n不能被2整除
    	}
    	system("pause");
    	return 0;
    }
    

    与君共享,如果有更好的建议或意见欢迎留言。

    QQ2630420233

                                                                                                                                                                                                    珍&源码

    展开全文
  • 方法一:public class Fibonacci1{  //定义个变量方法  public static void main(String[] args) {  int a=1, b=1, c=0;  System.out.println("斐波那契数列前20项为:");  System.out.
  • 1. 列表输出 def Fibonacci_li(num): a = 0 b = 0 li = [] for i in range(num): li.append(a) a, b = b, a + b return li print(fibonacci(10)) # 输出结果:[0, 1, 1, 2, 3, 5, 8, 1...
  • 第一:我们最熟悉的递推式: F(0) = 0 , F(1) = 1, F(n) = F(n-1)+F(n-2)long long F[10000]={0,1}; long long Fib(int n) //求斐波那契数列的第n项 { if(n==0)return 0; else if(n==1)return 1; ...
  • 所谓Fibonacci数列是指这样一数列,它的前两项均为1,从第项开始各项均为前两项之和。用数学公式表示出来就是:  1 (n=1,2) fib(n)=  fib(n-1)+fib(n-2) (n>2) 可以证明斐波那契数列的通项公式为fib(n) ...
  • 斐波那契数列(Fibonacci sequence)Python实现的三种方案 列表 递归 生成器
  • 提起斐波那契数列,首先想到的大概都是递归,但是其时间复杂度并非最优,其时间复杂度为O(2^N)。具体分析可以参考:Fibonacci 方法二 循环 递归之所以效率低下,是因为需要重复的计算一些中间变量。而利用循环可以...
  • 斐波那契数列的三种方法

    万次阅读 多人点赞 2018-07-05 21:49:00
    什么是斐波那契数列,1,1,2,3,5,8,13...这样一个数列就是斐波那契数列,求第n项的值。 一、经典求法 观察数列可得,除了第一项和第二项,所有的数列的值都是前一项和前一项的前一项的加和,转换成函数也就是f(n) =...
  •  class Program  {  static void Main(string[] args)  {  ArryFunc(10);  LoopFunc(10);  int a;... a = Convert.ToInt32(Console.ReadLine());... return Fibonacci(n - 1) + Fibonacci(n - 2);  }  }
  • 斐波那契数列: 第一个数是0,第二个数是1,从此以后,每一个数都是前两个数的和。 输入一个整数n,返回斐波那契数列的第n个数。 样例输入: n = 2 样例输出: 1 样例输入: n = 6 样例输出: 5 Solution 1: def ...
  • Fibonacci三种算法

    2010-10-06 16:54:59
    Fibonacci 斐波拉契 数列 三种算法 递归, 普通, 数组 有人痴迷于递归,其实递归写的简单,但效率最差.不信的话,你把这段程序的数设置为50以上看一下递归的运行时间!!所以, 我用了三种算法. 有兴趣大家交流
  • java实现斐波那契数列的三种方法

    万次阅读 多人点赞 2018-11-15 16:15:03
    Java实现斐波那契数列的三种方法 什么是斐波那契数列 这里借用一下度娘的一段话:斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而...
  • 转载:斐波那契数列三种写法:c# 转载:斐波那契数列三种写法:c#
  • 斐波那契数列的概念 斐波那契数列(Fibonacci sequence),又称黄金分割]数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为兔子数列...斐波那契数列的三种解法 public class
  • 二、斐波那契数列的三种实现方法1.递归2.简单循环,无数组3.数组三、完整代码 前言 C++ 得到斐波那契数列三种方法 一、斐波那契数列是什么? 斐波那契数列(Fibonacci sequence) 又称黄金分割数列,因数学家...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,259
精华内容 19,703
关键字:

斐波那契三种