首页 > 试题广场 >

N阶楼梯上楼问题

[编程题]N阶楼梯上楼问题
  • 热度指数:21504 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
N阶楼梯上楼问题:一次可以走两阶或一阶,问有多少种上楼方式。(要求采用非递归)

输入描述:
输入包括一个整数N,(1<=N<90)。


输出描述:
可能有多组测试数据,对于每组数据,
输出当楼梯阶数是N时的上楼方式个数。
示例1

输入

4

输出

5
#include<stdio.h> #include<string.h> //排列组合,阶梯总数为1和2的组合
int zuhe(int n,int m){     int t,i,r=1;     if(n==0||m==0)         return 1;     if(n>m){         t=n;         n=m;         m=t;     }     for(i=n;i>0;i--){         r*=(m+i);     }     for(i=1;i<=n;i++){         r/=i;     }     return r; }
int main(){     int m,n,N,d;     long long c;     while(scanf("%d",&N)!=EOF){         m=N;//1的个数         n=0;//2的个数         c=0;//总方案数         d=0;//每种情况的方案数         while(m>1){             d=zuhe(n,m);//组合数             c+=d;             m-=2;             n++;         }         d=zuhe(n,m);         c+=d;         printf("%lld\n",c);
}
}

编辑于 2019-02-17 16:39:39 回复(0)
#include<stdio.h>
int main()
{
    int n,i;
    long long f1,f2,a;//定义long long int解决大数相加
    while(scanf("%d",&n)!=EOF)
    {
        f1=1;f2=2;
        if(n==1)
        printf("%d\n",f1);
        else if(n==2)
            printf("%d\n",f2);
        else
        {
            for(i=3;i<=n;i++)
        {
            a=f1+f2;
            f1=f2;
            f2=a;
        }
        printf("%lld\n",f2);//输出 格式应该为“%lld”
        }
    }
    return 0;
}
发表于 2018-01-14 17:32:19 回复(0)
import java.util.*; public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            long[] fab = new long[n+1];
            fab[0] = 0;
            if(n > 0){
                fab[1] = 1;
            }
            if(n > 1){
                fab[2] = 2;
            }
            for(int i = 3; i <= n; i++){
                fab[i] = fab[i-1] + fab[i-2];
            }
            System.out.println(fab[n]);
        }
    }
}

编辑于 2017-05-20 19:04:26 回复(0)
#include<stdio.h>//递推关系式 1阶:1 2阶:2 3阶:3 4阶:5 
int main()//关系式a[n]=a[n-1]+a[n-2];
{
    int n,a[90],i;
    scanf("%d",&n);
    a[1]=1;a[2]=2;
    for(i=3;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    printf("%d",a[n]);
}

编辑于 2020-03-30 17:51:08 回复(0)
Java 解法
import java.util.Scanner;

public class Main {
    // 使用动态规划解法
    // 状态转移方程 dp[i]=dp[i-1]+dp[i-2]
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // n+2 是为了防止数组下标越界,如输入1时
        int[] dp = new int[n+2];
        dp[1]= 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i]=dp[i-1]+dp[i-2];
        System.out.println(dp[n]);

    }
}


发表于 2020-03-18 10:09:52 回复(0)
#include<stdio.h>

int main(){
    int n;
    int dp[90];
    dp[1] = 1;
    dp[2] = 2;
    for(int i=3; i<90; i++)
        dp[i] = dp[i-1] + dp[i-2];
    
    while(scanf("%d",&n)!=EOF)
        printf("%d\n",dp[n]);
    return 0;
}

发表于 2020-03-09 20:00:02 回复(0)
#include<stdio.h>
int stair(int,int);
int main(){
    int num;
    int n2;
    int i2,i1;
    int sum,ways=0;
    while(scanf("%d",&num)!=EOF){
    n2=num/2;
    for(i2=0;i2<=n2;i2++){
        i1=num-i2*2;
        sum=stair(i2,i1);
        ways=ways+sum;
    }
    printf("%d",ways);
    }
}
int stair(int a,int b){
    int i,j;
    int sum=1;
    int c=1;
    for(i=a+b;i>b;i--){
        sum=sum*i;
    }
    for(i=1;i<=a;i++){
        c=c*i;
    }
    sum=sum/c;
    return sum;
}
发表于 2020-01-07 23:46:03 回复(0)
/*
更快更强?RH
@L W Q
time@2019/9/817:09
为什么return bool?
*/
#include <stdio.h>
#include <string.h>
using namespace std;

int lwq[91];

bool get(){
    memset(lwq,0,sizeof(lwq));
    lwq[1] = 1;
    lwq[2] = 2;
    for(int i = 3;i<91;i++)
        lwq[i] = lwq[i-1]+lwq[i-2];
    return true;
}

int main(){
    int n;
    get();
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",lwq[n]);
    }
    return 0;
}

发表于 2019-09-08 17:07:30 回复(0)
#include<bits/stdc++.h>
int main(){
    int n,a[90];
    a[1]=1;a[2]=2;
    for(int i=3;i<90;i++)
        a[i]=a[i-1]+a[i-2];
    while(scanf("%d",&n)!=EOF)
        printf("%d\n",a[n]);
}
发表于 2019-03-28 11:39:11 回复(0)
#include<stdio.h>
int stair(int n)
{
 if(n==1) return 1;
 else if(n==2) return 2;
 else return(stair(n-1)+stair(n-2));
}
int main()
{
 int n;
 scanf("%d",&n);
 printf("%d",stair(n));
 return 0;
}
还是递归比较简单……
发表于 2018-11-12 10:31:27 回复(0)
//迭代
#include<stdio.h>

int main(){
    int N;
    int a[91];
    int i;
    a[0]=0;
    a[1]=1;
    a[2]=2;
    i=3;
    scanf("%d",&N);
    while(i<=N){
        a[i]=a[i-1]+a[i-2];
        i++;
    }
    printf("%d",a[N]);
    return 0;
}
发表于 2018-06-03 16:48:24 回复(0)

#include <iostream>

using namespace std;

long long F[100];

int main() {

    F[1] = 1;

    F[2] = 2;

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

        F[i] = F[i - 1] + F[i - 2];

    }

    int n;

    while (cin >> n) {

        cout << F[n] << endl;

    }

    return 0;

}


发表于 2018-02-18 11:19:32 回复(0)
#include <iostream>
using namespace std;
int main()
{
    int N;
    long long total = 1;
    long long  f = 0;
    
    while(cin >> N)
    {
          for(int i = 0; i < N; i++)
          {
         total = total + f;
         f = total - f;
          }
          cout << total << endl;
          total = 1;
          f = 0;
    }
    return 0;
}

编辑于 2017-06-08 21:51:44 回复(2)
斐波那契数列实现简单,但存在溢出的问题。推荐使用java的大数类。
import java.math.BigInteger;
大数类的操作:
1.valueOf(parament); 将参数转换为制定的类型
2.add(); 大整数相加
    a.add(b);
3.subtract(); 相减
4.multiply(); 相乘
5.divide(); 相除取整
6.remainder(); 取余
7.pow();
    a.pow(b)=a^b
8.gcd();   最大公约数
9.abs(); 绝对值
10.negate(); 取反数
11.mod(); 
    a.mod(b)=a%b=a.remainder(b);
12.max(); min();
13.punlic int comareTo();
14.boolean equals(); 是否相等

代码如下:
BigInteger t1 = new BigInteger("1"); BigInteger t2 = new BigInteger("2"); BigInteger result = new BigInteger("0"); for(int i = 3;i<=N;i++){ result = t1.add(t2); t1 = t2; t2 = result; } System.out.println(result);

发表于 2017-05-21 20:38:01 回复(0)
第一个问题,要注意溢出,所以选用long型,第二个问题,可以采用将数据存放在一个数组当中,来解决非递归的方法
发表于 2017-04-03 13:37:50 回复(0)
#include <iostream>

int main(){

    int a;
    while(std::cin >> a){
        if(1 == a){
            std::cout << 1 << std::endl;
        }else{
            long long f1 = 1, f2 = 2;
            for(int i = 3; i <= a; ++i){    //斐波那契数列;
                f2 += f1;
                f1 = f2 - f1;
            }
            std::cout << f2 << std::endl;
        }
    }

    return 0;
}
	
	

编辑于 2016-12-12 02:06:11 回复(0)
//注意int型的数据会溢出,定义成long long类型;
#include<iostream>
using namespace std;

long long  upper(int N)
{
    if(N<=0) return 0;
    if(N==1) return 1;
    if(N==2) return 2;
    long long  a=1;
    long long  b=2;
    long long  temp;
    for(int i=3;i<=N;i++)
    {
        temp=a+b;
        a=b;
        b=temp;
    }
    return temp;
}
int main()
{
    int N;
    while(cin>>N)
    {
        cout<<upper(N)<<endl;
    }
    return 0;
}

发表于 2016-08-12 16:30:42 回复(1)
/*解题思路, 如果去推一下就会发现是斐波那契, 但是, 靠规律解题, 是不齿的^^,
    所以就认真想了一下, 发现,
    1,两步阶梯,是有2种走法
    2,三步阶梯有3种走法
    1   2   3
    12      3
    1   23
    3,四种阶梯有5种走法,

    1    2    3    4   (在三步的基础上
    1    2    34

    12        3    4
    12        34

    1     23        4

     那好,这5种走法是怎么来的呢,
    嗯, 就是在三步阶梯的走法上的基础上多了两种走法,
    第一个就是一二种步法其实是一种,只不过是第四步联合了第三步或者不联合而已,
    而要联合第三步, 就必须要第三步是联合的, 嗯,问题就来了,必须要第三步是独立的,方可联合,
    而第三步独立, 就说明只需要看第一步和第二步就行了,嗯 ,就是一个递归的过程
    当然, 将递归转化为递推, 这道题还是很容易的,
    由于有多组数据, 可以用一个数组将运算过的数据保存, 就可以提高效率啦,

    程序到这儿,结果发现,到46的时候,int型数据会爆炸, c语言处理大数,我的天,自己写了一个大数加法,
*/

#include <stdio.h>
#include <string.h>

int main()
{
    int N;
    char fblq[101][100]= {0};
    fblq[1][1]=1;
    fblq[2][1]=2;
    int i,j;


    for(i=3; i<=100; i++)
    {
        for(j = 1; j<100; j++)
        {
            fblq[i][j] = fblq[i-1][j] + fblq[i-2][j];
        }

        for(j = 1; j<100-1; j++)//处理进位
        {
            fblq[i][j+1] += fblq[i][j]/10;
            fblq[i][j] %= 10;
        }

    }

    while(scanf("%d",&N)!=EOF)
    {
        for(j=99; j>0; j--)
        {
            if(fblq[N][j]!=0)
                break;
        }

        for(i=j; i>0; i--)
        {
            printf("%d",fblq[N][i]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2017-02-24 00:49:03 回复(0)
//走到第n阶时可能是从第n-1阶走一步到的,也可能是从n-2阶走两阶到的,设F(n)为走到n阶的种数,则F(n)=F(n-1)+F(n-2).
//这是一个动态规划的问题,其实就是一个斐波那契数列。
#include<iostream>
#include<stack>
using namespace std;

int main(){
    long a[90];
    int N;
    while(cin>>N){
        a[1]=1;a[2]=2;
        for(int i=3;i<=N;i++){
            a[i]=a[i-1]+a[i-2];
        }
        cout<<a[N]<<endl;
    }
    return 0;
}
发表于 2017-01-07 15:56:10 回复(6)

python solution:

while True:
    try:
        a,arr=int(input()),[1,2]
        while len(arr)<a:
            arr.append(arr[-1]+arr[-2])
        print(arr[a-1])

    except:
        break
发表于 2017-10-01 16:58:27 回复(0)