剑指Offer - 面试题10:斐波那契数列

简介: 剑指Offer - 面试题10:斐波那契数列

题目一 求斐波那契数列的第n项

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


分析

递归法

给出的公式用递归是最简单的,但是也是效率很低的。

C

#include<stdio.h>
long long Fibonacci(int n)
{
  if (n <= 0)
  {
    return 0;
  }
  if (n == 1)
  {
    return 1;
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
  long long int value = Fibonacci(10);
  printf("value:%lld\n", value);
  return 0;
}


我们来讨论为什么说递归实现斐波那契数列效率低。看下图

仅仅列举了几行就可以看到同一个数字被重复计算多次,用递归方法计算时间复杂度是以n的指数增长。所以我们一般不推荐用这种方法。


下图是n=30的执行时间为3s,可想而知速度多慢

记忆化递归法

上面的递归效率低的问题关键所在是计算重复的。所以我们可以用一个n大小的数组来存储之前的结果。时间复杂度O(n),空间复杂度O(n)。

测试数据n=100,是秒出结果(这里不考虑溢出问题)

C

#include<stdio.h>
#include<stdlib.h>
long long Fibonacci(int n)
{
  if (n < 2)
  {
    return n;
  }
  long long * a = (long long*)malloc(sizeof(long long) * n);
  if (NULL == a)
  {
    perror("申请空间失败!");
  }
  for (int i = 2; i <= n; i++)
  {
    a[i] = a[i - 1] + a[i - 2];
  }
  return a[n - 1];
}
int main()
{
  long long int value = Fibonacci(100);
  printf("value:%lld\n", value);
  return 0;
}


动态规律

分析上面那种方法,我们可以看到构造出来的数组实际有用的只是最近的俩个值,其他的值都可以不用,那么我们可以设计一个动态的,以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。

时间复杂度O(n),空间复杂度O(1)。

C

long long Fibonacci(int n)
{
  long long first = 0;
  long long second = 1;
  long long sum = 0;
  if (n < 2)
  {
    return n;
  }
  for (int i = 2; i <= n; i++)
  {
    sum = first + second;
    first = second;
    second = sum;
  }
  return sum;
}
int main()
{
  long long int value = Fibonacci(10);
  printf("value:%lld\n", value);
  return 0;
}


题目二 青蛙跳台阶问题

一只青蛙一次可以跳上一级台阶,也可以跳上俩级台阶。求该青蛙跳完上一个n级的台阶总共有多少种跳法。

分析

我们可以找到一个规律:

上一个n级的台阶总数=上一个n-1级台阶总数+上一个n-2级台阶总数

有0个台阶时候:1种方法

有一个台阶时候:1种方法

有二个台阶时候:2种方法

有三个台阶时候:3种方法


1 1 2 3 5 8 13 … 实际就是斐波那契数列,解法和上面如出一辙,不再赘述。


相关题目

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形,请问用8个21的小矩形无重叠的覆盖一个2*8的大矩形时。总共有多少种方法?

分析

我们将2*8的覆盖方法设为f(8)。假设小矩形竖着放,剩下的即为f(7)。小矩形横着放在左下角那么上面也必须横着放,剩下的即为f(6);因此f(8)=f(7)+f(6); 本质还是斐波那契数列。解法和上面如出一辙,不再赘述。

本章完

目录
相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面