2023华为OD机试真题 JavaScript 实现【猴子爬山】

淡淡的烟草味﹌ 2023-10-13 16:58 76阅读 0赞

**目录**

题目

思路

考点

Code

--------------------

## 题目 ##

> 一天一只顽猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：
> 
> 每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？
> 
> **输入描述**
> 
> 输入只有一个整数N（0<N<=50）此阶梯有多少个台阶。
> 
> **输出描述**
> 
> 输出有多少种跳跃方式（解决方案数）。
> 
> **示例1** 输入输出示例仅供调试，后台判题数据一般不包含示例
> 
> **输入**
> 
> `50`
> 
> **输出**
> 
> `122106097`
> 
> **示例2** 输入输出示例仅供调试，后台判题数据一般不包含示例
> 
> **输入**
> 
> `3`
> 
> **输出**
> 
> `2`
> 
> ``

## 思路 ##

> 1：明显的斐波那契数列问题，可以通过递归来实现，但是**注意这里不能通过函数的递归来实现，可能会爆栈**。
> 
> 假设：k=100;
> 
> 上山最后一步到达第100级台阶，完成上山，共有f（100）种不同的爬法，到第100级之前位于哪一级呢？无非是位于第99级（上跳1级即到），有f（99）种；
> 
> 或位于第97级（上跳3级即到），有f（97）种，于是：
> 
>  *  f（100）=f（99）+f（97）
> 
>  *  f（99）= f（98）+f（96）
>  *  f（97）= f（96）+f（94）
>  *  依次类推
> 
> 以此类推，一般地有递推关系：
> 
>  *  f（k）=f（k-1）+f（k-3） （k>3）
> 
> **初始条件**：
> 
>  *  f（1）=1，即1=1；
>  *  f（2）=1，即2=1+1（注意：跳法中不允许直接跳2级）；
>  *  f（3）=2，即3=1+1+1，3=3；
> 
> 根据以上递推关系与初始条件设置一重k（4~n）循环，循环外确定初始条件，循环内实施递推：
> 
>  *  f\[k\]=f\[k-1\]+f\[k-3\]，即可求出f（n）；//与斐波那契数列的求解一样
> 
> 此具体案例的递推设计比较简单，时间复杂度为O（n）；

## 考点 ##

> 1：递归

## Code ##

function main(n){
        let step1 = 1, step2 = 1, step3 = 2;
        let step4 = n == 1 || n == 2 ? 1 : 2;
        for (let i = 4; i <= n; i++) {
            step4 = step3 + step1;
            step1 = step2;
            step2 = step3;
            step3 = step4;
        }
    
        console.log(step4);
    }
    
    main(50)

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

语言限定：  
C（clang11）, C++（clang++11）, Pascal（fpc 3.0.2）, Java（javac 1.8）, Python2（2.7.3）,  
PHP(7.4.7), C\#(mcs5.4), ObjC(gcc 5.4), Pythen3(3.9), JavaScript Node(12.18.2), JavaScript V8(6.0.0),  
Sqlite(3.7.9), R(4.0.3), Go(1.14.4), Ruby(2.7.1), Swift(5.3), matlab(Octave 5.2), Pypy2(pypy2.7.13),  
Pypy3(pypy3.6.1), Rust(1.44), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2), Mysql(8.0)