首页 > 试题广场 >

某人上楼梯，他一步可以迈一个台阶，两个台阶或三个台阶，共有n

[问答题]
某人上楼梯，他一步可以迈一个台阶，两个台阶或三个台阶，共有n个台阶，编程输出他所有可能上法。
查看答案及解析
添加回答
竹碎怜影头像 竹碎怜影
典型的斐波那契数列的应用 和 青蛙跳台阶一个道理，解决他有两种方法，一个是递归，一个是循环，递归的优点是简单，但是函数的调用是有时间和空间的消耗的，每一次函数的调用都要在内存栈中保存参数、返回地址及临时变量，而且进出栈全需要时间，所以在这里我们不用递归。
long long Fibonacci(unsigned int){
   int result[3]={0,1,1};
   if(n<3)
     return[n];
   long long fibOne = 0;
   long long fibTwo = 1;
   long long fibThird = 1;
  for(unsigned int n=3; i< =n;++i){
    fibN =fibOne+fibTwo+fibThird;
    fibOne=fibTwo;
    fibTwo=fibThird;  
    fibThird=fibN;
   }
  return fibN;
}
发表于 2015-05-14 16:43:55 回复(0)
更多回答
推荐
SunburstRun头像 SunburstRun
中心思想是：假设他已经在最后一层n，那么他前一步可能是n-1,n-2或者n-3；那么n-1前一步又可能是n-2,n-3,n-4，所以一直循环递推，可得出答案.
伪代码：
for(int i=4;i<=target;i++)
a[i]=a[i-1]+a[i-2]+a[i-3];
编辑于 2015-05-19 19:59:51 回复(1)
大城市小葫芦头像 大城市小葫芦
最后一步可以迈了1，2或者3步，分为这三种情况，这三种情况都是一种解，然后向前递归就行
进入递归的条件是n>=4，f(n)=f(n-1)+f(n-2)+f(n-3)，当n<4时跳出循环，f(1)=1,f(2)=2,f(3)=4
发表于 2015-05-14 17:05:06 回复(0)
蓝莲花头像 蓝莲花
package com.ixx.test;

public class OnTheStairs {
    
    public static int all = 0;
    // 某人上楼梯，他一步可以迈一个台阶，两个台阶或三个台阶，共有n个台阶，编程输出他所有可能上法
    /**
     * @param n
     *            n个台阶
     * @param sum
     *            现在在第几个台阶
     * @param i
     *            现在迈i个台阶
     * @param record
     */
    public static void onStairs(int n, int sum, int i, String record) {
        if (sum + i > n) {
            return;
        } else if (sum + i == n) {
            System.out.println("走了" + record.length() + "步，方式是" + record);
            all++;
            return;
        } else {
            onStairs(n, sum + i, 1, record + 1);
            onStairs(n, sum + i, 2, record + 2);
            onStairs(n, sum + i, 3, record + 3);
        }
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println("列举所有上"+n+"台阶的所有方法:");
        onStairs(n, 0, 0, "");
        System.out.println("共"+all+"种方法");
    }
}


发表于 2015-05-14 15:31:48 回复(0)
Newdawn头像 Newdawn
是完全背包吗？或者f[i]= f[i-1]+f[i-2]+f[i-3]，f[n]就是最后结果
发表于 2015-01-05 19:23:49 回复(0)
秃头凡头像 秃头凡
此题为斐波那契数列问题的一个变体。假设dp[n]表示n阶楼梯上楼方式的总数。
首先dp[1] = 1, dp[2] = 2, dp[3] = 4,表示台阶数为1时有一种走法.台阶数为2时有两种走法，台阶数为3时有四种走法。
其次当n大于等于4时，由于有三种上楼的方式，所以它只能是从n-1阶再经过一步走到第n阶，
或者从n-2阶再到n阶，或者从第n-3阶再到n阶。所以dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]; 
#include<iostream>
(720)#include<cstdio>
using namespace std;
int main()
{
    int n;
	scanf("%d", &n);
	long long dp[n + 1]; 
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for(int i = 4; i <= n; i++){
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; 
	}
	printf("%lld", dp[n]);

    return 0;
}


发表于 2020-05-15 15:47:38 回复(0)
zbx21ambition头像 zbx21ambition

public class Test {
public static int getNumber(int n){
if(n<=3){
return n;
}
int f1=1;
int f2=2;
int f3=3;
int f=0;
for(int i=4;i<=n;i++){
f=f1+f2+f3;
f1=f2;
f2=f3;
f3=f;
}
return f;
}
public static void main(String[] args) {
int res=getNumber(10);
System.out.println(res);
}
}

发表于 2017-03-26 20:14:34 回复(0)
IT小菜头像 IT小菜 
#include<stdio.h>
#include<stdlib.h>
void main(){
int stepNum,sum；
scanf("%d",&stepNum);
sum=stepToN(stepNum);
printf("total methods:"+sum);
}
int stepToN(int stepNum){
 int totalmeth=0
 if(stepNum<0)
  return 0;
 if(stepNum==1)
  totalmeth=1;
 if(stepNum==2)
  totalmeth=2;
if(stepNum==3)
  totalmeth=4;
else
 totalmeth=stepToN(stepNum-1)+stepToN(stepNum-2)+stepToN(stepNum-3);
return totalmeth;
}

发表于 2015-06-12 14:57:15 回复(0)
CrazyHSF头像 CrazyHSF
#include<stdio.h>
#include<stdlib.h>
int PLT(int N)
{
    static int sum=0;
    if (N==1)
    {
        sum+=1;
        return sum;
    }
    if(N==2)
    {
        sum+=2;
        return sum;
    }
    if(N==3)
    {
        sum+=4;
        return sum;
    }
    PLT(N-1);
    PLT(N-2);
    PLT(N-3);
    return sum;
}

int main()
{
    int sum,n;
    scanf("%d",&n);
    sum=PLT(n);
    printf("sum=%d\n",sum);
    system("pause");
    return 0;
}
走法数量
递归~
发表于 2015-05-20 15:12:15 回复(0)
玄郎之印头像 玄郎之印
费波拉契数列的思想
#include<iostream>
using namespace std;

int Steps(int n)
{
if(n==1)
return 1;
if(n==2)
return 2;
if(n==3)
return 4;
return Steps(n-1)+Steps(n-2)+Steps(n-3);
}

int main(int argv,char** argc)
{
int n;
cout<<"请输入台结数："<<endl;
cin>>n;
cout<<"共有 "<<Steps(n)<<" 种走法"<<endl;
return 0;
}
发表于 2015-05-19 21:42:08 回复(0)
不是一个响亮的名字头像 不是一个响亮的名字
斐波那契数列问题。
f（n）= f(n-1) + f(n-2) + f(n-3)
f(1) = 1,f(2) = 2,f(3) = 3 
long long fibonacci(int n){
    if(n <= 3){
         return n;
    }
    int f1 = 1,f2 = 2, f3 = 3;
    long long fn = 0;
    for(int i = 4; i<= n;i++){
        fn = f1 + f2 +f3;
        f1 = f2;
        f2 = f3;
        f3 = fn;
    }
    return fn;
}

发表于 2015-05-14 22:17:21 回复(0)
陈朝阳_karl头像 陈朝阳_karl
if (1==n)
   f(n) = 1;
if (2==n)
   f(n) = 2;
if (3==n)
   f(n) = 3;
if(n >=4)
   f(n) = f(n-1) + f(n-2) + f(n-3)+....+f(0) 




发表于 2015-05-14 21:52:09 回复(0)
天空中的云彩头像 天空中的云彩
当 n=1时 f(n)=1;
当 n=2时 f(n)=2;
当 n=3时 f(n)=3;
当 n>4时 f(n)=f(n-1)+f(n-2)+f(n-3)

发表于 2015-05-14 21:39:05 回复(0)
流氓、头像 流氓、
斐波那契数列  当前数=前一个数+前一个数的前一个数
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(0);
发表于 2015-05-14 21:28:57 回复(0)
baike21头像 baike21
int jump(vector<int> num){
int n = num.size();
int f[n];
if(n==0)return f[0]=0;
if(n==1)return f[1]=1;
if(n==2)return f[2]=2;
if(n==3)return f[3]=4;

for(int i=4; i<=n; i++){
    f[i] = f[i-1]+f[i-2]+f[i-3];
}
return f[n]
}
发表于 2015-05-14 20:46:06 回复(0)
迈杰头像 迈杰
int fun(int n)
{
    if(n<0)
     return 0;
    if(n==0||n==1){return 1;}
if(n==2){return 1+fun(1);}
    return fun(n-1)+fun(n-2)+fun(n-3);
}
发表于 2015-05-14 19:55:11 回复(0)
手机用户3091285952头像 手机用户3091285952 
int taijie(int n,std::list<std::list<int>> & o) {
    o.clear();
    std::list<int> l;
    if ( n<=0 ) {
        return 0;
    }
    else if ( n==1 ) {
        l.push_back(1);
        o.push_back(l);
        return 1;
    }
    
    std::list<std::list<int>> & o1;
    taijie(n-1,o1);
    for ( std::list<std::list<int>>::iterator it=o1.begin();it!=o1.end();++it ) {
        (*it).push_front(1);
        o.push_back(*it);
    }
    taijie(n-2,o1);
    for ( std::list<std::list<int>>::iterator it=o1.begin();it!=o1.end();++it ) {
        (*it).push_front(2);
        o.push_back(*it);
    }
    taijie(n-3,o1);
    for ( std::list<std::list<int>>::iterator it=o1.begin();it!=o1.end();++it ) {
        (*it).push_front(3);
        o.push_back(*it);
    }
    return o.size();
}
发表于 2015-05-14 17:47:54 回复(0)
零机头像 零机
  1. package  first;  
  2.   
  3. import  java.util.Stack;  
  4.   
  5. public   class  first {  
  6.   
  7.     /** 
  8.      * 一个人爬楼梯，一步可以迈一级，二级，三级台阶， 如果楼梯有N级，编写程序，输出所有走法。java实现。 
  9.      *  
  10.      * @param args 
  11.      */   
  12.     public   static   void  main(String[] args) {  
  13.         // TODO Auto-generated method stub   
  14.         Stack<Integer> stt=new  Stack<Integer>();  
  15.         buileT(stt,6 );  
  16.     }  
  17.   
  18.     public   static   void  buileT(Stack<Integer> stt, int  N) {  
  19.         if  (N >=  1 ) {  
  20.             // System.out.println("某人走了1个楼梯");   
  21.             stt.push(1 );  
  22.             buileT(stt,N - 1 );  
  23.             stt.pop();  
  24.         }  
  25.         if  (N >=  2 ) {  
  26.             // System.out.println("某人走了2个楼梯");   
  27.             stt.push(2 );  
  28.             buileT(stt,N - 2 );  
  29.             stt.pop();  
  30.         }  
  31.         if  (N >=  3 ) {  
  32.             // System.out.println("某人走了3个楼梯");   
  33.             stt.push(3 );  
  34.             buileT(stt,N - 3 );  
  35.             stt.pop();  
  36.         }  
  37.         if  (N ==  0 ) {  
  38.             for ( int  i:stt)  
  39.             {  
  40.                 System.out.print("由" +i+ "--" );  
  41.             }  
  42.             System.out.println("完成" );  
  43.             System.out.println("" );  
  44.         }  
  45.     }  
  46. }  
发表于 2015-05-14 16:29:18 回复(0)
geeker头像 geeker 
fnum(int n){
 if(n==1){
  return 1
 }
 if(n==2){
 return 2;
 }
 if(n==3){
 return 4;//111,12,21,3
 }
 if(n>3){
  return fnum(n-1)+fnum(n-2)+fnum(n-3);
 }
}

发表于 2015-05-14 15:02:57 回复(0)
joshua317头像 joshua317
n 为1，2，3 时
f(1) = 1;
f(2) = 2;
f(3) = 4;

n 大于3时
f(n)=f(n-1)+f(n-2)+f(n-3)；

<?php
//递归的方法，当n很大时，服务器会受不了啊，所以不建议使用该方法，只是一种思路
function ways($n){
$way = 0;
if($n==1){
$way = 1;
}elseif($n==2){
$way = 2;
}elseif($n==3){
$way = 4;
}elseif($n>=4){
$way = ways($n-1)+ways($n-2)+ways($n-3);
}
return $way;
}

$n = 5;//给定n的值
$way = ways($n);
echo $way;

?>



给出另外一种方法

<?php
//递归的方法，当n很大时，服务器会受不了啊，所以可以先把值存起来，这样计算机计算起来就会毫无压力啊
 function ways($n){
     $wayarr = array();
     $wayarr[1] = 1;
     $wayarr[2] = 2;
     $wayarr[3] = 4;
     if($n==1){
         $wayarr[$n] = 1;
     }elseif($n==2){
         $wayarr[$n] = 2;
     }elseif($n==3){
         $wayarr[$n] = 4;
     }elseif($n>=4){
         for($i=4;$i<=$n;$i++){
             $wayarr[$i] = $wayarr[$i-1]+$wayarr[$i-2]+$wayarr[$i-3];
         }
     }
     return $wayarr[$n];
 }

 $n = $_GET['n'];//给定n的值
 $way = ways($n);
 echo $way;

?>



编辑于 2015-05-14 15:20:40 回复(0)
如果大雄没有机器猫头像 如果大雄没有机器猫
2^(n-1)
发表于 2015-05-14 12:08:44 回复(0)
提交观点

问题信息

动态规划 迅雷
上传者：TurtlefisH
难度：
22条回答 20333浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号