首页 > 试题广场 >

有一段楼梯台阶有11级台阶,以友友的脚力一步最多只能跨3级,

[单选题]
  1. 有一段楼梯台阶有11级台阶,以友友的脚力一步最多只能跨3级,请问友友登上这段楼梯有多少种不同的走法?
  • 476
  • 504
  • 924
  • 271
链接:https://www.nowcoder.com/questionTerminal/360069ca7225478380ffdcfb7e4b2a2b?orderByHotValue=0&questionTypes=100101&done=0&pos=13&onlyReference=false
来源:牛客网
类似斐波那契数列的思想,若所求方法表示为f(n),因为当台阶大于3时,可看做是
f(n)=f(n-1)+f(n-2)+f(n-3);//因为踏入最后一节阶梯有三种方法,最后一步是一步,两步,三步。
代码如下:
        publicstaticvoidmain(String[] args) {
        intf1 =1;
        intf2 =2;
        intf3 =4;
        intresult =0;
        for(inti =4;i<=15;i++){
            result = f1+f2+f3;
            f1 = f2;
            f2 = f3;
            f3 = result;
        }
        System.out.println(result);
    }
发表于 2019-07-26 23:36:48 回复(2)
如果用n表示台阶的级数,a n表示某人走到第n级台阶时,所有可能不同的走法,容易得到:

① 当 n=1时,显然只要1种跨法,即a 1=1。

② 当 n=2时,可以一步一级跨,也可以一步跨二级上楼,因此,共有2种不同的
跨法,即a 2=2。

③ 当 n=3时,可以一步一级跨,也可以一步三级跨,还可以第一步跨一级,第二步跨二级或第一步跨二级,第二步跨一级上楼,因此,共有4种不同的跨法,即a 3=4。

④ 当 n=4时, 分三种情况分别讨论跨法:

如果第一步跨一级台阶,那么还剩下三级台阶,由③可知有a3 =4(种)跨法。

如果第一步跨二级台阶,那么还剩下二级台阶,由②可知有a2 =2(种)跨法。

如果第一步跨三级台阶,那么还剩下一级台阶,由①可知有a1 =1(种)跨法。

根据加法原理,有a 4= a1 +a2 +a3 =1+2+4=7

类推 ,有

a5= a2 +a3+a4 =2+4+7=13

a6= a3 +a4+a5 =4+7+13=24

a7= a4 +a5+a6=7+13+24=44

a8= a5 +a6 +a7 =13+24+44=81

a9= a6+a7+a8 =24+44+81=149

a10= a7 +a8 +a9=44+81+149=274

a11=a8+a9+a10=81+149+274=504
一般地,有an=an-1+an-2+an-3
发表于 2019-11-02 08:36:27 回复(8)
let f1 = 1, f2 = 2, f3 = 4, result = 0; for (let i = 4; i <= 11; i++) {
    result = f1 + f2 + f3;  f1 = f2;  f2 = f3;  f3 = result; }
console.log(result); 


发表于 2019-06-17 10:51:28 回复(0)
我是英语系的,快七年都没碰过数学了,这个真的太难为我了,这次蒙对只是侥幸😥
发表于 2020-03-08 15:33:35 回复(5)
友友已累倒在台阶上
发表于 2020-10-22 16:26:08 回复(0)
可用“动态规划”法:
到达1阶可能性:f(1)=1 ;到达2阶:f(2)=2;到达3阶f(3)=4
到达4阶有可以从第1、2、3阶梯出发,所以可能性:f(4)=f(3)+f(2)+f(1)
f(5)=f(4)+f(3)+f(2)
...以此类推
f(11)=f(10)+f(9)+f(8)=507
发表于 2021-08-07 17:19:06 回复(1)

本题建议采用递归求解,当台阶数为1,有1种方法上台阶,当台阶数为2,有2种方法,当台阶数为3时,有4种方法上台阶,当台阶数比3大时,因为我们一次性可以跳一阶两阶或者三阶,所以方法数应该是跳一阶之后所有可能+跳两阶之后所有可能+跳三阶之后所有可能,既jump(n) = jump(n-1)+jump(n-2)+jump(n-3)。

本方法采用java求解。

public int jump(int n){

if(n == 1 || n == 2) return n;

if(n == 3) return 4;

return jump(n-1)+jump(n-2)+jump(n-3);

}

发表于 2019-10-13 09:07:08 回复(1)
手算可以从10到1倒着算,计算量小

编辑于 2020-01-17 17:39:15 回复(1)
如果整个台阶只有1级,则显然只有一种跳法。如果台阶有2级,则有两种跳法:一种是分两次跳,每次跳1级;另一种是一次跳2级。如果台阶有3级,则有4种跳法:一种是分3次跳,每次跳1级;一种是第一次跳1级,第二次跳2级;一种是第一次跳2级,第二次跳1级;最后一种是直接跳3级。
推广到一般情况。则可以把n级台阶时的跳法看成是n的函数,记为f(n)。当n > 2时,第一次跳一级还是两级,决定了后面剩下的台阶的跳法数目的不同:如果第一次只跳一级,则后面剩下的n-1级台阶的跳法数目为f(n-1);如果第一次跳两级,则后面剩下的n-2级台阶的跳法数目为f(n-2)。如果第一次跳三级,则后面剩下的n-2级台阶的跳法数目为f(n-3)。因此,当n > 3时,n级台阶的不同跳法的总数f(n) = f(n-1) + f(n-2)+f(n-3)。其中f(1) = 1,f(2) = 2,f(3)=4。

追本溯源,上述问题的本质就是斐波那契数问题。


编辑于 2020-02-14 23:37:45 回复(0)
怎么做行测也能遇到dp!!!
发表于 2021-05-17 21:57:03 回复(0)
给大家一个比较清晰的思路,这个人最多每次只能跨三级台阶,那么,假设当前为n,那么,走到当前台阶有多少种走法?三种,从n-1跨1步上来到n,从n-2跨两步上来到n,从n-3跨3步到n。这样,计算当前的次数,只需要知道n-1,n-2,n-3的走法,相加起来就可以了。如果你有幸,会一点点编程,那么,可以非常迅速得到是507.
第一个是1种,第2个台阶是2种,第3个台阶4种。开个数组,就可以了。
public class Main{
    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        int nums[]=new int[1000];
        nums[1]=1;
        nums[2]=2;
        nums[3]=4;
        for(int i=4;i<=11;++i)
            nums[i]=nums[i-1]+nums[i-2]+nums[i-3];
        System.out.println(nums[11]);
        reader.close();//关闭输入流
    }
}

发表于 2020-12-29 16:12:14 回复(0)

C11 4 +C11 5+……+C11 11排列组合不知道有没有看得懂

发表于 2020-03-06 18:57:11 回复(0)
F(n) = F(n-3)+F(n-2)+F(n-1),F(1)=1, F(2)=2, F(3)=4 ,后面就加加加
发表于 2022-09-16 17:44:02 回复(0)
相当于有1,2,3这三个数字,任意组合,使得其和为11。分为如下几种情况:
(一) 只有一种数字,显然只能是纯1的组合(纯2的和、纯3的和不满足和为11)。
            显然,只有1种情况
(二)同时包含两种数字
1、数字{1,2}的组合
形式:1+2+1+1+1……+1
相当于将原来的两个1,合并成了1个2,从而求和,其中2可以出现在任意位置。
例如只包含1个2时,只有10个数字,这1个2可以出现在10个数字的任意位置,即C(10,1)。因此需要具体讨论2的个数,即分情况如下:
情况1:只包含1个2:C(10,1)种
情况1:只包含2个2: C(9,2)种
情况1:只包含3个2: C(8,3)种
情况1:只包含4个2: C(7,4)种
情况1:只包含5个2: C(6,5)种
2、数字{2,3}的组合:
情况1:1个2+3个3:C(4,1)
情况2:4个2+1个3:C(5,4)
3、数字{1,3}的组合:
情况1:只包含1个3:C(9,1)种
情况1:只包含2个3: C(7,2)种
情况1:只包含3个3: C(5,3)种
(三)同时包含三种数字
数字{1,2,3}的组合:
情况1:1个3+1个2+6个1:C(8,1)*C(7,1)种
情况2:1个3+2个2+4个1:C(7,1)*C(6,2)种
情况3:1个3+3个2+2个1:C(6,1)*C(5,3)种
情况4:2个3+1个2+3个1:C(6,4)*C(4,1)种
情况5:2个3+2个2+1个1:C(5,1)*C(3,2)种



发表于 2021-09-22 20:08:46 回复(0)
一般地,有an=an-1+an-2+an-3
走到第1级台阶:只有1种走法
走到第2级台阶:有2种走法 1,1 /2
走到第3级台阶:有4种走法 1,2/2,1/3/1,1,1
走到第4级台阶:有7种走法
走到第5级台阶:有13种走法
走到第6级台阶:有24种走法
走到第7级台阶:有44种走法
走到第8级台阶:有81种走法
走到第9级台阶:有149种走法
走到第10级台阶:有274种走法
走到第11级台阶:有504种走法


发表于 2021-04-24 14:45:25 回复(0)
做完这个题,时间已经过去了一大半
发表于 2022-09-14 22:09:07 回复(0)
大部分的测试,一题只有一分钟~~凭感觉多一点
发表于 2022-09-03 19:56:16 回复(0)
斐波那契数列变式 假设台阶数为1,则有1种跨法。 假设台阶数为2,则有2种跨法。 假设台阶数为3,则有1+2+1=4种跨法。 假设台阶数为4,则有1+4+2=7种跨法 假设台阶数为5,则有1+4+3+3=11种跨法 易知:F(n)=F(n-1)+F(n-2)+F(n-3)
发表于 2020-09-25 04:32:09 回复(0)
还是要分而治之
发表于 2020-09-05 22:01:27 回复(0)
斐波那契数列
发表于 2020-07-24 18:02:43 回复(0)