我要招人

去企业版

首页 > 试题广场 >

有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，

[单选题]

有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?()

```
2345
```
```
3261
```
```
5768
```
```
6843
```

查看正确选项

害群之马

假设走n步阶梯的方法总数为f(n)，那么对于n步的阶梯，有三种情况：第一步走一步，第一步走两步，第一步走三步，

走完第一步后剩下的走法分别有f(n-1)，f(n-2)，f(n-3)种走法，

所以有: f(n)=f(n-1)+f(n-2)+f(n-3) (对于n>=4)

同理： f(n-1)=f(n-2)+f(n-3)+f(n-4) (对于n>=5)

前面两式相减可以得到： f(n)=2*f(n-1)-f(n-4) (对于n>=5)

而对于n<=5的情况有：

f(1)=1

f(2)=2

f(3)=4

f(4)=7

于是有：

f(5)=2*7-f(1)=13

(6)=2*13-f(2)=24

f(7)=2*24-f(3)=44

f(8)=88-f(4)=81

f(9)=2*81-f(5)=149 <

f(10)=298-f(6)=274

f(11)=548-f(7)=504

f(12)=1008-f(8)=927

f(13)=1854-f(9)=1854-149=1705

f(14)=3410-f(10)=3410-274=3136

f(15)=6272-f(11)=6272-504=5768

呵呵

编辑于 2018-04-09 16:31:45 回复(21)

zxx2019

类似斐波那契数列的思想，若所求方法表示为f（n），因为当台阶大于3时，可看做是
f(n)=f(n-1)+f(n-2)+f(n-3);//因为踏入最后一节阶梯有三种方法，最后一步是一步，两步，三步。
代码如下：
        public static void main(String[] args) {
		int f1 = 1;
		int f2 = 2;
		int f3 = 4;
		int result = 0;
		for(int i = 4;i<=15;i++){
			result = f1+f2+f3;
			f1 = f2;
			f2 = f3;
			f3 = result;
		}
		System.out.println(result);
	}

发表于 2016-04-18 17:07:52 回复(17)

foreverfruit

假设在第0阶台阶上时，一级台阶时只有一种方法，两级台阶有两种，三级台阶有4种方法，四级台阶有7种，。。。，显然这是斐波那契数列f(n)=f(n-1)+f(n-2)+f(n-3)

编辑于 2016-04-26 21:36:24 回复(0)

牛妹夫

选择题，写程序不现实，可以只考虑个位数的和，毕竟题目答案个位数都不一样。

发表于 2016-08-27 19:17:33 回复(6)

pandanrain

def cnt(n):
	dic = {1: 1, 2: 2, 3: 4}
	if n <= 3:
		return dic[n]
	return cnt(n-1) + cnt(n-2) + cnt(n-3)
print cnt(15)

5768

[Finished in 0.1s]

发表于 2017-01-07 16:31:46 回复(0)

VictoriaZhou

画一个递归数，从树叶节点值往主干上加，如下

发表于 2019-04-04 23:23:41 回复(1)

crisma

只加个位

发表于 2016-09-26 20:37:21 回复(1)

JKinbo

没有数学方法吗？答个选择题还要编程？要是现场考试你们怎么编程啊？

发表于 2016-09-04 13:39:07 回复(3)

WalterCapable

斐波纳吉数列的思想。

public static int calculator(int n){

switch (n) {

case 1:

return 1;

case 2:

return 2;

case 3:

return 4;

}return calculator(n-1)+calculator(n-2)+calculator(n-3);

}

发表于 2016-04-18 12:17:41 回复(0)

张大力

道理我都懂，但是怎么算？一个一个手动迭代？

发表于 2016-09-26 14:24:17 回复(1)

林大大

这道题是利用f(n)=f(n-1)+f(n-2)+f(n-3)一直从4台阶算到15台阶吗？（其中f(1)=1,f(2)=2,f(3)=4)。有没有简便的算法？

发表于 2016-07-30 09:16:22 回复(0)

QTZCY

#include <iostream>

#include <vector>

using namespace std;

int main(){

vector<int> floor;

floor.push_back(1);

floor.push_back(2);

floor.push_back(4);

for(int i = 3; i < 15; i++){

int tt = floor[i - 3] + floor[i - 2] + floor[i - 1];

floor.push_back(tt);

}

cout<<floor[14]<<endl;

return 0;

发表于 2016-04-18 14:25:57 回复(0)

牛客290136415号

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
int f(int x)
{
   if (x <= 1)
       return 1;
   else if (x >= 3)
       return f(x - 1) + f(x - 2) + f(x - 3);
   else
       return f(x - 1) + f(x - 2);
}
int main()
{
   int step = 15;
   cout << f(step);
   system("pause");
   return 0;
}

发表于 2021-08-07 16:32:15 回复(0)

寒炎

我的思路

f1=1;f2=2；f3=4；（无明显规律）

f4:先跨一步剩下的和f3相同

先跨两步剩下的和f2相同

先跨三步剩下的和f1相同

三种情况相加得f4=f1+f2+f3;

f5同理先跨一步剩下的和f4相同

先跨两步剩下的和f3相同

先跨三步剩下的和f2相同

三种情况相加得f5=f2+f3+f4;

由此规律

fn：先跨一步剩下的和f(n-1)相同

先跨两步剩下的和f(n-2)相同

先跨三步剩下的和f(n-3)相同

即fn=f(n-1)+f(n-2)+f(n-3);

编辑于 2019-11-08 15:31:23 回复(0)

Co小冷

/*
* 解题思想：设总走法为f(n)，第一步有三种走法：走一步、走两步、走三步，
* 走一步后剩余走法为 f(n-1)，走两步剩余走法为f(n-2)....
* 所以可以得到f(n) = f(n-1) + f(n-2) + f(n-3),然后就可以用递归或者迭代实现
*/

function methods(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  if (n === 3) return 4;
  return methods(n-1) + methods(n-2) + methods(n-3)
}

function methods2(n, x = 1, y = 2, z = 4) {
  if (n <= 1) return x;
  if (n <= 2) return y;
  if (n <= 3) return z;
  return methods2(n - 1, y, z, x + y + z)
}

function methods3(n) {
  let [x, y, z] = [1, 2, 4];
  if (n === 1) return x;
  if (n === 2) return y;
  if (n === 3) return z;
  for (let i = 4; i <= n; i ++) {
    [x, y, z] = [y, z, x + y + z];
  }
  return z;
}
console.log(methods3(15))

发表于 2018-07-07 00:39:34 回复(0)

龙升九天

public class Bag {
    public static void main(String[] args) {
        int i;
        i=f(15);
        System.out.println(i);
    }
    public static int f(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        if(n==3)
            return 4;
        else
            return f(n-1)+f(n-2)+f(n-3);
    }
}

发表于 2018-04-13 16:31:11 回复(0)

请叫我帅帅

写个小程序啦~

#include<iostream>
using namespace std;
int f(int n);
int main()
{
    int n;
    cin>>n;
    int count=f(n);
    cout<<count<<endl;
    return 0;
}
int f(int n)
{
    if(n==1)
        return 1;
    if(n==2)
        return 2;
    if(n==3)
        return 4;
    return (f(n-1)+f(n-2)+f(n-3));
}

发表于 2018-03-29 17:22:59 回复(0)

湛湛的天空

存粹为了选答案的话不需要递归所有，只需要考虑个位数就行。首先，f(n)=f(n-1)+f(n-2)+f(n-3) 前3项分别为： 1, 2, 4 接着，后面各项个数分别为 7, 3, 4, 4, 1, 9, 4, 4, 7, 5, 6, 8 故选……

发表于 2017-08-19 21:54:35 回复(0)

轮


	
	
		
	




	int step(int totalStep) {

 int *steps = new int[totalStep + 1];
    steps[1] = 1; steps[2] = 2; steps[3] = 4;
    for (int i = 4; i <= totalStep; i++) {
        steps[i] = steps[i - 3] + steps[i - 2] + steps[i - 1];
    }
    int result = steps[totalStep];
    delete[] steps;
    return steps[totalStep];
}

忍不住试下用数组写个代码

PS：有个答案说只需要考虑个位数，这个想法真是6爆了

发表于 2016-09-13 12:59:58 回复(0)

演绎极致

使用数学方法公式为（f(1)+f(2)+f(3)）*2^(n-3+1);n为总的台阶数，3为一次能走的最大台阶数。

发表于 2016-09-13 12:40:33 回复(1)

提交观点

问题信息

算法工程师京东 2016 运营递归

来自：京东2016算法工程师笔试题

难度：

59条回答 1479收藏 31436浏览

有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，

问题信息

热门推荐

相关试题