斐波那契数列 | Fibonacci sequence | Python实现

斐波那契数列：

[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 … ]

这个数列从第3项开始，每一项都等于前两项之和

Python实现

import sys


#循环 返回第 n 个 数
def loop(n):
	first,second = 0,1
	for i in range(n):
		first,second = second,first+second
	return first
	
#循环，返回斐波那契数列
def fib(n):
	v = [0, 1]
	for i in range(2,n+1):
		v.append(v[i-1] + v[i-2])
	return v
	# return v[n]

if __name__ == '__main__':
    print(fib(int(sys.argv[1])))	
    print("loop = %d " % loop(int(sys.argv[1])))	

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

C语言实现

递归 相对于循环而言，有非常大的函数时间消耗

#include <stdio.h>
#include <time.h>

//递归计算斐波那契数
long fib_recursion(int n) {
    if (n <= 2) {
        return 1;
    }
    else {
        return fib_recursion(n - 1) + fib_recursion(n - 2);
    }
}

//迭代计算斐波那契数
long fib_iteration(int n){
    long result;
    long previous_result;
    long next_older_result;
    result = previous_result = 1;
    while (n > 2) {
        n -= 1;
        next_older_result = previous_result;
        previous_result = result;
        result = previous_result + next_older_result;
    }
    return result;
}

int main() {
    int a;
    clock_t time_start_recursion, time_end_recursion;
    clock_t time_start_iteration, time_end_iteration;

    printf("Input a number: ");
    scanf("%d", &a);

    //递归的时间
    time_start_recursion = clock();
    printf("Fib_recursion(%d) = %ld\n", a, fib_recursion(a));
    time_end_recursion = clock();
    printf("run time with recursion: %lfs\n", (double)(time_end_recursion - time_start_recursion)/ CLOCKS_PER_SEC );

    //迭代的时间
    time_start_iteration = clock();
    printf("Fib_iteration(%d) = %ld\n", a, fib_iteration(a));
    time_end_iteration = clock();
    printf("run time with iteration: %lfs\n", (double)(time_end_iteration - time_start_iteration) / CLOCKS_PER_SEC);

    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

时间消耗对比如下：

gcc loop.c 

./a.out 

Input a number: 45
Fib_recursion(45) = 1134903170
run time with recursion: 5.449947s

Fib_iteration(45) = 1134903170
run time with iteration: 0.000003s



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

文章来源: positive.blog.csdn.net，作者：墨理学AI，版权归原作者所有，如需转载，请联系作者。

原文链接：positive.blog.csdn.net/article/details/117222932