算法 | 斐波那契数列

柔情只为你懂 2022-12-10 08:42 181阅读 0赞

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  具体实现
 *   *   *  循环法
         *  递归法
         *  Go 语言循环实现
         *  使用数据公式计算

--------------------

# 前言 #

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

# 具体实现 #

### 循环法 ###

#include <iostream>
    
    using namespace std;
    
    int fib(int N) {
        if(N < 2) {
            return N;
        }
        if(N == 2) {
            return 1;
        }
        int a = 0, b = 1, result=0;
        for(int i=2; i<=N; ++i) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }

### 递归法 ###

int fibRecursion(int N) {
        if (N < 2) {
            return N;
        } else if (N == 2) {
            return 1;
        } else {
            return fibRecursion(N - 1) + fibRecursion(N-2);
        }
    }

### Go 语言循环实现 ###

> 其实循环的方法是一样的，不过 `Go`、`Python` 有个更好的赋值用法，所以单独写一下

func Fib(N int) int { 
    	if N < 2 { 
    		return N
    	}
    	if N == 2 { 
    		return 1
    	}
    	var a = 0
    	var b = 1
    	for i := 2; i <= N; i++ { 
    		a, b = b, a+b
    	}
    	return b
    }

### 使用数据公式计算 ###

![在这里插入图片描述][20200924231247328.png_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5bmRldg_size_16_color_FFFFFF_t_70_pic_center]

[20200924231247328.png_pic_center]: /images/20221123/88c201218ff14e7da469a1ba8e3fd8cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5bmRldg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/4dec207ca10f4c36b83a71cbed32be85.png