剑指Offer面试题:7.斐波那契数列

一题目:斐波那契数列二效率很低的解法很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心上述递归的解法有很严重的效

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:7.斐波那契数列此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:斐波那契数列

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下:


剑指Offer面试题:7.斐波那契数列

二 效率很低的解法

  很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心

#include "stdio.h"
#include <iostream>
using namespace std;

int Fibs(int n)
{
    if (0 == n)
    {
        return 0;
    }
    else if (1 == n)
    {
        return 1;
    }
   return Fibs(n-1) + Fibs(n-2);
}

void main()
{
    cout << "斐波那契数列:" << endl;
    cout <<Fibs(0)<<" ";
    cout <<Fibs(1)<<" ";
    cout <<Fibs(2)<<" ";
    cout <<Fibs(3)<<" ";
    cout <<Fibs(4)<<" ";
    cout <<Fibs(5)<<" ";
    cout <<Fibs(6)<<" ";
    cout <<Fibs(7)<<" ";
    cout <<Fibs(8)<<" " << endl;
    return;
}

剑指Offer面试题:7.斐波那契数列

  上述递归的解法有很严重的效率问题,通过求解第10项的调用过程图来分析:

  剑指Offer面试题:7.斐波那契数列

  从上图中不难发现:在这棵树中有很多结点是重复的,而且重复的结点数会随着n的增大而急剧增加,这意味计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的

三 时间复杂度为O(n)的解法

  改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多,我们只要想办法避免重复计算就行了。这里的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是O(n)

#include "stdio.h"
#include <iostream>
using namespace std;

int Fibs(int n)
{
    int nFibs = 0;
    if (0 == n)
    {
        return 0;
    }
    else if(1 == n)
    {
        return 1;
    }
    int nSubOne = 1;  // Fibs(n-1)
    int nSubTwo = 0;  // Fibs(n-2)
    for (int i = 2; i <= n; i ++)
    {
        nFibs = nSubOne + nSubTwo;
        nSubTwo = nSubOne;
        nSubOne = nFibs;
    }

    return nFibs;
}

void main()
{
    cout << "斐波那契数列:" << endl;
    cout <<Fibs(0)<<" ";
    cout <<Fibs(1)<<" ";
    cout <<Fibs(2)<<" ";
    cout <<Fibs(3)<<" ";
    cout <<Fibs(4)<<" ";
    cout <<Fibs(5)<<" ";
    cout <<Fibs(6)<<" ";
    cout <<Fibs(7)<<" ";
    cout <<Fibs(8)<<" " << endl;
    return;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120168.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 开启c盘默认共享(c++内存管理机制)

    不建议关闭---默认共享是系统安装完毕后就自动开启的共享,也叫管理共享,常被管理员用于远程管理计算机。在Windows2000/XP及其以上版本中,默认开启的共享有“c$”、“d$”、“admin$”、“ipc$”等,我们可以在“运行”对话框中输入“\\计算机名\盘符$”对这些资源进行访问,以上这些共享就叫做默认共享。但你可曾想过这些默认共享与普通共享在访问上有哪些区别呢?默认共享有哪些特权…

  • 大数据平台数据权限管理设计

    大数据平台数据权限管理设计背景和范围当前大数据团队没有一个统一的操作权限控制和管理平台,对于分析师在服务器上的权限,目前都是给予对应分析节点的EC2机器账号,且为了方便操作和管理都是给予的管理员权限,因此安全性风险较大;对于数据开发者,主要通过分配IAM控制AWS的操作权限;对于team的所有人都是通过分配aws的ak,sk在本地进行操作赋权;随着数据平台的不断的丰富和完善,需要在各组件之上做认证,鉴权和审计等管理,数…

  • 数组和集合的相互转换「建议收藏」

    数组和集合的相互转换「建议收藏」数组和集合的相互转换

  • kafka 认证和鉴权方式_kafka实际应用

    kafka 认证和鉴权方式_kafka实际应用前言kafka官网关于sasl_scram鉴权Kafka消费端配置创建SCRAMCredentials依赖zk,需要先启动zk,然后在zk中创建存储SCRAM凭证:cdkafkacluster/kafka_2.11-1.1.1bin/kafka-configs.sh–zookeeperzkIP1:2181,zkIP2:2181,zkIP3:2181/lxgkafka–alter–add-config’SCRAM-SHA-256=[password=admin-secr

    2022年10月29日
  • 生活小感慨

    生活琐事开一篇文来记录生活2021/12/9阻挡我使我停滞不前的,是浮躁的心2021/8/16我也并不希望我的生活是一成不变的.2021/8/13挑战软肋2021/8/5感谢每一个编

    2021年12月13日
  • C#的WinForm窗体程序中如何设置TextBox为密码文本框

    C#的WinForm窗体程序中如何设置TextBox为密码文本框C#的WinForm窗体程序中如何设置TextBox为密码文本框-2019-08-0323:59在C#的WinForm窗体程序开发过程中,TextBox是常用的文本框控件,默认的TextBox

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号