【Html.js——算法题】小兔子爬楼梯（蓝桥杯真题-1770）【合集】

Rossy Yan

发布于 2025-01-24 11:21:12

3030

文章被收录于专栏：【Educoder实训】头歌实践教学平台【Educoder实训】头歌实践教学平台

背景介绍

小兔子想去月球上旅行，假设小兔子拥有一个 n 阶梯子，当你爬完 n 层就可以到达月球，小兔子每次可以跳 1 或者 2 个台阶，小兔子有多少种跳法可以到达月球呢？给定 n 是一个正整数，代表梯子的阶数，当 n=2 时，小兔子有 2 种跳法到达月球；当 n=3 时，小兔子有 3 种跳法跳到月球，以此类推，解释如下图所示：

思路提示

这里为同学提供以下两种解题思路。 1. 递归 可以使用递归来实现，具体思路如下：

当阶梯数为 0 时，只有 0 种方法；当阶梯数为 1 时，只有 1 种方法；当阶梯数为 2 时，只有 2 种方法，所以当阶梯数 n 小于等于 2 时，可以直接返回值。
如果阶梯数大于 2，就递归。

2. 动态规划 可以使用动态规划来实现，具体思路如下：

当阶梯数 n 为 0 时，直接返回 0。
当阶梯数 n 为 1 时，直接返回 1。
当阶梯数大于 1 时，假设有 i 阶梯子需要爬，就有 dp[i] 中方法。
3 阶以上的梯子，都满足一个规律：dp[i] = dp[i-1] + dp[i-2]。

解题思路不只这两种，同学们可以自由发挥。

准备步骤

本题已经内置了初始代码，打开实验环境，目录结构如下：

├── js
│   └── index.js
└── index.html

其中：

js/index.js 是实现函数的 js 代码文件。
index.html 是显示结果的页面。

选中 index.html 右键启动 Web Server 服务（Open with Live Server），让项目运行起来。打开环境右侧的【Web 服务】，当前页面显示如下。

目标要求

请完善 index.js 文件中的代码，页面显示结果如下：

要求规定

请严格按照考试步骤操作，切勿修改考试默认提供项目中的文件名称、文件夹路径等。
满足题目需求后，保持 Web 服务处于可以正常访问状态，点击「提交检测」系统会自动判分。

通关代码✔️

思路1：递归

//思路1：递归
const climbStairs = (n) => {
 if(n === 0){
    return 0;
 }else if(n === 1){
    return 1;
 }else if(n === 2){
    return 2;
 }else{
    return climbStairs(n - 1) + climbStairs(n - 2);
 }
};
module.exports = climbStairs;

思路2：动态规划

// 思路2：动态规划实现
const climbStairs = (n) => {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else if (n === 2) {
        return 2;
    }
    let dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
module.exports = climbStairs;

代码解析📑

1. HTML 部分

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <div>
        <p id="result1"></p>
        <p id="result2"></p>
        <p id="result3"></p>
    </div>
    <script src="./js/index.js"></script>
    <script>
        let r1 = document.getElementById("result1");
        let r2 = document.getElementById("result2");
        let r3 = document.getElementById("result3");
        r1.innerHTML = `2 阶梯子，兔子有 ${climbStairs(2)} 种跳法到达月球。`;
        r2.innerHTML = `3 阶梯子，兔子有 ${climbStairs(3)} 种跳法到达月球。`;
        r3.innerHTML = `4 阶梯子，兔子有 ${climbStairs(4)} 种跳法到达月球。`;
    </script>
</body>

</html>

文档类型声明和 HTML 结构基础：

<!DOCTYPE html>：声明这是一个 HTML5 文档。
<html lang="en">：指定文档的语言为英语。
<head> 部分：
- <meta charset="UTF-8">：使用 UTF-8 字符编码，确保页面可以正确显示各种字符。
- <meta name="viewport" content="width=device-width, initial-scale=1.0">：设置视口，使页面在不同设备上有较好的显示效果，width=device-width 表示视口宽度等于设备宽度，initial-scale=1.0 表示初始缩放比例为 1。
- <title>Document</title>：设置页面的标题。
<body> 部分：
- <div> 元素包含了三个段落元素 <p>，分别具有 id 为 result1、result2 和 result3。这些元素将用于显示小兔子跳不同阶梯数的跳法结果。
- <script src="./js/index.js"></script>：引入外部的 JavaScript 文件，该文件应该包含 climbStairs 函数的实现。
- 内部的 <script> 块：
  - 通过 document.getElementById() 方法获取到三个段落元素，并存储在变量 r1、r2 和 r3 中。
  - 使用 innerHTML 属性将结果显示在相应的段落元素中，调用 climbStairs 函数并将结果插入到相应的段落中。例如，r1.innerHTML = 2 阶梯子，兔子有 ${climbStairs (2)} 种跳法到达月球。; 会调用 climbStairs(2) 并将结果显示在 id 为 result1 的段落中。

2. JavaScript（递归实现）

//思路1：递归
const climbStairs = (n) => {
 if(n === 0){
    return 0;
 }else if(n === 1){
    return 1;
 }else if(n === 2){
    return 2;
 }else{
    return climbStairs(n - 1) + climbStairs(n - 2);
 }
};
module.exports = climbStairs;

函数 climbStairs：

这是一个使用递归实现的函数，用于计算小兔子跳 n 阶梯子的跳法数量。
当 n 等于 0 时，返回 0，因为没有阶梯可跳，所以跳法为 0。
当 n 等于 1 时，返回 1，因为只有一种跳法，即一次跳 1 级台阶。
当 n 等于 2 时，返回 2，因为可以一次跳 2 级台阶或分两次每次跳 1 级台阶。
对于 n 大于 2 的情况，根据递推关系 f(n) = f(n - 1) + f(n - 2) 进行计算。这里调用 climbStairs(n - 1) 表示从 n - 1 级台阶跳到 n 级台阶的跳法数量，调用 climbStairs(n - 2) 表示从 n - 2 级台阶跳到 n 级台阶的跳法数量。
注意：这种递归实现对于较大的 n 会有性能问题，因为存在大量的重复计算，例如计算 climbStairs(5) 时会多次计算 climbStairs(3) 和 climbStairs(2) 等。

3. JavaScript 部分（动态规划实现）：

// 思路2：动态规划实现
const climbStairs = (n) => {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else if (n === 2) {
        return 2;
    }
    let dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
module.exports = climbStairs;

函数 climbStairs：

首先，处理 n 等于 0、1、2 的基本情况，与递归实现相同。
创建一个长度为 n + 1 的数组 dp，用于存储到达每一级台阶的跳法数量。
初始化 dp[0] = 0，dp[1] = 1，dp[2] = 2，这是前面讨论过的基础情况。
使用 for 循环从第 3 级台阶开始，根据递推公式 dp[i] = dp[i - 1] + dp[i - 2] 计算到达第 i 级台阶的跳法数量。
对于每一个 i，dp[i] 的值等于 dp[i - 1]（表示从 i - 1 级台阶跳 1 级到达 i 级的跳法数量）加上 dp[i - 2]（表示从 i - 2 级台阶跳 2 级到达 i 级的跳法数量）。
最后返回 dp[n]，即到达第 n 级台阶的跳法数量。
这个实现避免了递归中的重复计算，通过存储中间结果提高了性能，对于较大的 n 更有效率。

4. 工作流程 ▶️ （1）整体工作流程概览：

首先，浏览器加载 HTML 页面，解析页面结构，设置页面元数据和视口信息。
当解析到 <script src="./js/index.js"></script> 时，加载并执行外部 JavaScript 代码。
内联的 <script> 部分调用 climbStairs 函数计算跳法数量，根据不同的 n 值得到不同的结果。
对于递归实现，通过不断调用自身并利用 n - 1 和 n - 2 的结果计算当前 n 的跳法数量。
对于动态规划实现，创建数组 dp 存储中间结果，从基础情况开始，通过循环和递推公式 dp[i] = dp[i - 1] + dp[i - 2] 计算后续的跳法数量。
最终将计算结果显示在 HTML 的 <p> 元素中，使用 innerHTML 插入结果字符串。

（2）具体工作流程详述：

页面加载阶段：
- 浏览器解析 <!DOCTYPE html>，识别为 HTML5 文档，开始加载页面。
- 解析 <head> 元素，根据 <meta charset="UTF-8"> 设定字符编码，使用 UTF-8 编码方式解析页面中的字符。
- 根据 <meta name="viewport" content="width=device-width, initial-scale=1.0"> 设定视口，确保页面在不同设备上能正常显示，视口宽度等于设备宽度，初始缩放比例为 1.0。
- 解析 <title>Document</title>，将页面的标题设为 "Document"。
内容渲染阶段：
- 进入 <body> 元素，开始渲染页面主体。
- 浏览器渲染 <div> 元素，包含三个 <p> 元素，此时这些元素的内容为空，因为 id 为 result1、result2 和 result3 的 <p> 元素的 innerHTML 尚未设置。
- 遇到 <script src="./js/index.js"></script>，浏览器暂停页面渲染，开始下载并执行 ./js/index.js 中的 JavaScript 代码。
- 继续执行内联的 <script> 代码：
  - 通过 document.getElementById() 方法分别获取 id 为 result1、result2 和 result3 的 <p> 元素，并存储在变量 r1、r2 和 r3 中。
  - 调用 climbStairs(2)、climbStairs(3) 和 climbStairs(4) 函数，计算小兔子跳不同阶梯数的跳法数量。
  - 将计算结果使用模板字符串拼接，更新相应 <p> 元素的 innerHTML，将结果显示在页面上。
函数调用阶段：
- 当 HTML 中的内联脚本调用 climbStairs(2) 时：
  - 函数首先检查 n 是否为 0、1 或 2，因为 n = 2，所以返回 2。
- 当调用 climbStairs(3) 时：
  - 检查 n，不满足 n === 0、n === 1 或 n === 2 的条件。
  - 创建长度为 4 的数组 dp，初始化 dp[0] = 0，dp[1] = 1，dp[2] = 2。
  - 进入 for 循环，当 i = 3 时，dp[3] = dp[2] + dp[1] = 2 + 1 = 3。
  - 最终返回 dp[3]，结果为 3。
- 当调用 climbStairs(4) 时：
  - 检查 n，不满足 n === 0、n === 1 或 n === 2 的条件。
  - 创建长度为 5 的数组 dp，初始化 dp[0] = 0，dp[1] = 1，dp[2] = 2。
  - 进入 for 循环，当 i = 3 时，dp[3] = dp[2] + dp[1] = 2 + 1 = 3；当 i = 4 时，dp[4] = dp[3] + dp[2] = 3 + 2 = 5。
  - 最终返回 dp[4]，结果为 5。