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

举报
墨理学AI 发表于 2022/01/10 23:20:34 2022/01/10
【摘要】 斐波那契数列: [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ...

斐波那契数列:


[ 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])))	

  
 

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;
}

  
 

时间消耗对比如下:

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
  
 

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

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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。