数据结构与算法（递归与循环） --javascript语言描述

nanfeiyan 发布于2019-08-26 11:44 / 3299人阅读

摘要：斐波那契数列大家都知道斐波那契数列，现在要求输入一个整数，请你输出斐波那契数列的第项。这样的计算是以的次方在增长的。我们不难看出这实际上就是斐波那契数列了。用表示跳上阶台阶的跳法数。所以，种跳法。

斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

递归解法：

  function Fibonacci(n)
  {
    if(n<=0) {
      return 0;
    }
    if(n==1) {
      return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
  }
  console.log(Fibonacci(10));

由于使用递归时，其执行步骤是：要得到后一个数之前必须先计算出之前的两个数，即在每个递归调用时都会触发另外两个递归调用，例如：要得到F(10)之前得先得到F(9)、F(8)，那么得到F(9)之前得先得到F(8)、F(7)......如此递归下去。这样的计算是以 2 的次方在增长的。除此之外，我们也可以看到，F(8)和F(7)的值都被多次计算，如果递归的深度越深，那么F(8)和F(7)的值会被计算更多次，但是这样计算的结果都是一样的，除了其中之一外，其余的都是浪费，可想而知，这样的开销是非常恐怖的！

所以，如果在时间复杂度和空间复杂度都有要求的话，我们可以用以下循环算法来实现：

  function Fibonacci(n)
  {
    if (n == 0 || n == 1) {
        return n;
    }
    let num1 = 0;
    let num2 = 1;
    let numN = 0;
    for (let i = 2; i <= n; i++) {
      numN = num1 + num2;
      num1 = num2;
      num2 =  numN;
    }
    return numN;
  }
  console.log(Fibonacci(10));

时间复杂度为O(N)。

青蛙跳台阶问题

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

思路:登上n阶台阶问题可以转换成登上n-2个台阶方式加上登上n-1个台阶加上登上n-3个台阶....加到登上1个台阶方式之和再加上一次登上总台阶和的问题
即有公式 f(n)=f(n-1)+f(n-2) +f(n-3)+......+f(3)+f(2)+(1)+1 。

我们不难看出这实际上就是斐波那契数列了。

  function jumpFloor(n)
  {
    if (n == 0 || n == 1) {
      return n;
    }
    if(n == 2) {
      return 2;
    }
    let num1 = 1;
    let num2 = 2;
    let numN = 0;
    for (let i = 3; i <= n; i++) {
      numN = num1 + num2;
      num1 = num2;
      num2 =  numN;
    }
    return numN;
  }
  console.log(jumpFloor(10))

{{BANNED}}跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

用Fib(n)表示跳上n阶台阶的跳法数。
当n = 1 时，只有一种跳法，即1阶跳：Fib(1) = 1;
当n = 2 时，有两种跳的方式，一阶跳和二阶跳：Fib(2) = 2;
到这里为止，和普通跳台阶是一样的。
当n = 3 时，有三种跳的方式，第一次跳出一阶后，对应Fib(3-1)种跳法；第一次跳出二阶后，对应Fib(3-2)种跳法；第一次跳出三阶后，只有这一种跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;
当n = 4时，有四种方式：第一次跳出一阶，对应Fib(4-1)种跳法；第一次跳出二阶，对应Fib(4-2)种跳法；第一次跳出三阶，对应Fib(4-3)种跳法；第一次跳出四阶，只有这一种跳法。所以，Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 种跳法。
当n = n 时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法；第一次跳出二阶后，后面还有Fib(n-2)中跳法..........................第一次跳出n阶后，后面还有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。
通过上述分析，我们就得到了通项公式：

             Fib(n) =  Fib(0)+Fib(1)+Fib(2)+.......+ Fib(n-2) + Fib(n-1)

因此，有

Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

两式相减得：

Fib(n)-Fib(n-1) = Fib(n-1)         =====》  Fib(n) = 2*Fib(n-1)     n >= 3

这就是我们需要的递推公式：Fib(n) = 2*Fib(n-1) n >= 3

  function jumpFloorII(n)
  {
    if (n == 0 || n == 1) {
      return n;
    }
    if(n == 2) {
      return 2;
    }
    let num2 = 2;
    let numN = 0;
    for (let i = 3; i <= n; i++) {
      numN =  2 * num2;
      num2 = numN;
    }
    return numN;
  }
  console.log(jumpFloorII(10))

云服务器混合云算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107481.html

数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

Carson 2019-08-26 11:32 评论0 收藏0
Javascript 深入学习循环

摘要：递归函数还会受到浏览器调用栈的大小的限制。虽然迭代也会导致性能问题，但是使用优化的循环就可以代替长时间运行的递归函数，可以提高新能，因为运行一个循环比反复调用一个函数的开销要小。本文章记录本人在深入学习js循环中看书理解到的一些东西，加深记忆和并且整理记录下来，方便之后的复习。选择正确的循环体在大部分编程语言中，代码执行的时间多数消耗在循环的执行上。 js定义了4种...

Cristalven 2019-08-22 10:57 评论0 收藏0
[翻译] JS的递归与TCO尾调用优化

这两天搜了下JS递归的相关文章，觉得这篇文章很不错，就顺手翻译了下，也算给自己做个笔记，题目是我自己加的。原文很长，写得也很详尽，这里并非逐字翻译，而是作者所讲的主要概念加上我自己的一些理解，本文中解决方案的实际意义并不是特别大，但算法的逻辑挺有意思，不过也略抽象，理解需要花点时间（囧，估计我太闲了）文中的用例?全部来自原文：原文链接：（原题为：理解JS函数式编程中的递归）Underst...

pekonchan 2019-08-21 10:49 评论0 收藏0
对于递归的傲慢与偏见

摘要：对于函数调用开销，可以利用尾递归来解决，不过目前的引擎并没有实现对尾递归的优化，所以最开始我以为递归没有理由比非递归更快。递归与堆栈非递归的算法使用一个堆栈来实现。最近刷leetcode 79题 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用递归，影响效率，于是利用stack完成。之后又利用递归（使用cache）实现了一次，结果竟然是递归的算法比非递归...

Labradors 2019-08-23 12:58 评论0 收藏0