首页 > 试题广场 > 爬楼梯
[编程题]爬楼梯
  • 热度指数:15701 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
在你面前有一个n阶的楼梯,你一步只能上1阶或2阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯。

输入描述:
一个正整数n(n<=100),表示这个楼梯一共有多少阶


输出描述:
一个正整数,表示有多少种不同的方式爬完这个楼梯
示例1

输入

5

输出

8

考察斐波那契数列
题目要求:只能跳1阶或者2阶。
定义阶有种跳法

  1. 假定第一次跳的是一阶,那么剩下的是 n-1 个台阶,跳法是;
  2. 假定第一次跳的是2阶,那么剩下的是 n-2 个台阶,跳法是
  3. 总跳法为:
  4. .

初次提交这个题会发现通过率只有 50%,是因为没有考虑到整数溢出的问题,用BigInteger处理就Ok了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        if (n < 3) {
            System.out.println(n);
            return;
        }
        BigInteger one = BigInteger.valueOf(1);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger ret = BigInteger.valueOf(0);

        for (int i = 3; i <= n; i++) {
            ret = one.add(two);
            one = two;
            two = ret;
        }
        System.out.println(ret);
    }
}
发表于 2019-07-28 13:59:23 回复(1)
写一个c语言比较简洁的大整数加法
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> dp(n + 5, vector<int> (100, 0));
    dp[1][0] = 1;
    dp[2][0] = 2;
    int len = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < len; j++) {
            dp[i][j] += dp[i - 1][j] + dp[i - 2][j];
            if (dp[i][j] > 9) {
                dp[i][j + 1] += dp[i][j] / 10;
                dp[i][j] %= 10;
                len += (j == len - 1);
            }
        }
    }
    for (int i = 0; i < len; i++) cout << dp[n][len - i - 1];
    cout << endl;
    return 0;
}


编辑于 2020-03-11 19:45:54 回复(2)
首先这个题目的模型是斐波那契数列(参考剑指offer的青蛙跳台阶),思路是很清晰的,但是有一个很棘手的问题:这个题C++没有大整数类,而题目的用例太大了,long long也只能通过55%的用例,所以只能通过字符串来显示。所以整道题的重点就是如何进行字符串相加,手写字符串相加函数、
下面的注释很详细了,可以参考
#include <iostream>
#include <string>
using namespace std;

string BigData(string s1, string s2){
    string res = "";
    int i = s1.size() - 1;
    int j = s2.size() - 1;
    int carry = 0;  //进位
    while (i >= 0 || j >= 0){
        // s2一定大于s1(斐波那契数列的后者 > 前者)
        if(i < 0){
            //当小的字符串先走完时,就剩大字符串了,同理进行逐位添加
            res = to_string((s2[j] - '0') + carry) + res;
            carry = 0;  //只剩一个字符串就不存在进位了,因为都是个位数
        } else{
            //从后往前进行逐位相加,如123+567,从3+7开始往前加,别忘了加上进位
            int tmp = (s1[i] - '0') + (s2[j] - '0') + carry;
            carry = tmp / 10;  //得到进位
            tmp = tmp % 10;    //得到余数
            res = to_string(tmp) + res; //这里顺序记得不能颠倒,不然就错了
        }
        --i; --j;
    }
    //为什么下面还要判定呢?因为比如3+7应该等于10,但是
    //上面的计算出的res只有0(余数),所以这里要考虑周全
    if(carry == 1)
        res = '1' + res;
    return res;
}
int main(){
    int n;
    cin >> n;
    //斐波那契
    if(n == 1){
        cout << 1 << endl;
        return 0;
    } else if(n == 2){
        cout << 2 << endl;
        return 0;
    }
    string i = "1";
    string j = "2";
    string ans = "";
    for(int k = 1; k <= n - 2; ++k){
        ans = BigData(i, j);  // i + j
        i = j;   
        j = ans;
    }
    cout << ans << endl;
    return 0;
}


编辑于 2020-06-03 21:22:49 回复(0)
递推公式很简单,f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2.
值得注意的是本题还有大整数问题,所以使用转化为字符串形式,额外写一个大整数相加函数
#include<iostream>
using namespace std;
//大整数相加函数
string add(string a,string b)
{
    int i=a.size()-1;
    int j=b.size()-1;
    string res="";
    int carry=0;
    while(i>=0&&j>=0)
    {
        char tmp;
        int num;
        num=(a[i]-48)+(b[j]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        i--;
        j--;
    }
    while(i>=0)
    {
        char tmp;
        int num;
        num=(a[i]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        i--;
    }
    while(j>=0)
    {
        char tmp;
        int num;
        num=(b[j]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        j--;
    }
    if(carry>0)
    {
        res=char(carry+48)+res;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    string a[n+1];
    for(int i=0;i<n+1;i++)
    {
        a[i]='0';
    }
    a[0]='1';
    a[1]='1';
    for(int i=2;i<n+1;i++)
    {
        a[i]=add(a[i-1],a[i-2]);
    }
    cout<<a[n];
}

发表于 2019-10-28 12:14:22 回复(0)
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<BigInteger> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            BigInteger temp = (i <= 2) ? BigInteger.valueOf(i) : list.get(i - 2).add(list.get(i - 3));
            list.add(temp);
        }
        System.out.println(list.get(list.size() - 1));
    }
}
发表于 2019-07-08 16:16:43 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int num[103][30] = {0};
    num[1][29] = 1;//第一项
    num[2][29] = 2;//第二项 
    for (int i = 3; i <= n; i++)
    {
        for (int j = 29; j >= 0; j--)//循环,数组行是从1开始,列是从0开始
        {
            if ((num[i - 1][j] + num[i - 2][j]+num[i][j]) >= 10)//进位,占多一个元素
                num[i][j - 1] += 1;
            num[i][j] = (num[i - 1][j] + num[i - 2][j] + num[i][j]) % 10;
        }
    }
    int j = 0;
    while (num[n][j] == 0)
        j++;
    for (int i = j; i < 30; i++)
        cout << num[n][i];
    return 0;
}

发表于 2019-07-03 22:07:12 回复(2)
import sys
def diffroad(n):
    res =[1,2]
    if n<3:
        return res[n-1]
    for i in range(3,n+1):
        res[(i-1)%2] += res[i%2]
    return res[(i-1)%2]
    
if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    print(diffroad(n))

发表于 2019-09-07 22:41:08 回复(0)
import java.util.*;
import java.math.*;
public class Main{
    static BigInteger func(int n){
        if(n==0)
            return new BigInteger("0");
        if(n==1)
            return new BigInteger("1");
        BigInteger[] ll=new BigInteger[n];
        ll[0]=new BigInteger("1");
        ll[1]=new BigInteger("2");
        for(int i=2;i<n;i++){
            ll[i]=ll[i-1].add(ll[i-2]);
        }
        return ll[n-1];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(func(n));
    }
}

发表于 2020-08-25 00:09:06 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[101][30] = {0};
    a[1][29] = 1;
    a[2][29] = 2;
    for(int i=3;i<=n;i++)
        for(int j=29;j>=0;j--){
            int t = a[i-1][j]+a[i-2][j]+a[i][j];
            if(t >= 10)
                a[i][j-1] += 1;
            a[i][j] = t%10;
        }
    bool zero = true;
    for(int j=0;j<30;j++){
        if(zero && a[n][j]!=0)
            zero = false;
        if(!zero)
            cout<<a[n][j];
    }
    cout<<endl;
    return 0;
}

发表于 2019-12-30 00:56:26 回复(1)

这里有一个超大数,CPP会溢出。直接用递归 cpp会超时,引入滚动数组,从低位开始计算,避免重复运算

if __name__ == "__main__":
    n = int(input().strip())
    dp = [1,2,0]
    if n<=2:
        print(n)
    else:
        for i in range(3, n+1):
            dp[-1]= dp[0]+dp[1]
            dp[0] = dp[1]
            dp[1]=dp[2]
        print(dp[2])

发表于 2019-07-22 11:05:42 回复(0)
""""
台阶问题,考虑动态规划
设dp[n]为n阶台阶的方法数,
每次只能上1、2阶台阶,要想到达n,则只能由n-1,n-2到达
dp[n] = dp[n-1] + dp[n-2]
边界 dp[0] = dp[1] = 1
"""

if __name__ == "__main__":
    n = int(input().strip())
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])

发表于 2019-07-13 14:54:55 回复(0)
本题结果用long类型存放也会超出范围,只能使用字符串存放。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] dp = new String[101]; // 楼梯的台阶数小于等于100
        dp[1] = String.valueOf(1);
        dp[2] = String.valueOf(2);
        for (int i = 3; i <= 100; i++) {
            dp[i] = add(dp[i - 1], dp[i - 2]); // 两个字符串相加
        }

        int n = sc.nextInt();
        System.out.println(dp[n]);
    }

    public static String add(String s1, String s2) {
        int n1 = s1.length() - 1;
        int n2 = s2.length() - 1;
        int add = 0; // 记录进位
        StringBuffer sb = new StringBuffer(); // 存放结果
        while (n1 >= 0 || n2 >= 0) {
            int x = (n1 >= 0) ? s1.charAt(n1) - '0' : 0;
            int y = (n2 >= 0) ? s2.charAt(n2) - '0' : 0;
            int sum = x + y + add;
            if (sum > 9) {
                sb.insert(0, sum % 10);
                add = 1;
            } else {
                sb.insert(0, sum);
                add = 0;
            }
            n1--;
            n2--;
        }
        if (add == 1) sb.insert(0, 1); // 最后查看是否有进位
        return sb.toString();
    }
}


发表于 2021-09-09 21:45:39 回复(0)
import java.util.*;
import java.math.BigInteger;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        BigInteger[] a = new BigInteger[n+1];
        if(n<3) System.out.println(n);
        if(n>=3){
            a[1]=new BigInteger("1");
            a[2]=new BigInteger("2");
            for(int i = 3;i<=n;i++){
                a[i]=a[i-1].add(a[i-2]);
                }
            System.out.println(a[n]);
        }
    }
}
发表于 2021-09-07 20:52:59 回复(0)
n=int(input())
a,b = 1,1
for _ in range(n):
    a,b=b,a+b
print(a)    

发表于 2021-03-31 20:33:51 回复(0)
package newcoder;

import java.math.BigInteger;// 这个有大整数问题,long也不行,只能采用BigInteger。其实也可以用字符串按位置相加,但是得额外写程序。
import java.util.Scanner;
import java.util.function.BiConsumer;

public class 小米爬楼梯 {
    static BigInteger JumpFloor(int number) {

        if(number == 0) return new BigInteger(String.valueOf(0));
        // 注意,这里的number == 1和number == 2都要写上,是因为下面已经用到了number[1]和number[2]
        if(number == 1) return new BigInteger(String.valueOf(1));
        if(number == 2) return new BigInteger(String.valueOf(2));
        BigInteger[] times = new BigInteger[number+1];
        times[0] = new BigInteger(String.valueOf(0));//第0级台阶
        times[1] = new BigInteger(String.valueOf(1));
        times[2] = new BigInteger(String.valueOf(2));
        for (int i = 3; i < times.length; i++) {
            times[i] = times[i-1] .add(times[i-2]);// 注意大整数相加是调用方法相加的,不是直接用+号的。
        }
        return times[number];
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        System.out.println(JumpFloor(number));// 竟然大整数的输出是和普通整数一样的,可以直接println。
    }
}

发表于 2020-05-20 20:53:56 回复(0)
#include<iostream>
(720)#include<string>
#include<vector>

using namespace std;

string add(std::string num1, std::string num2)//+
{
	int size = num1.size() > num2.size() ? num1.size() : num2.size();
	std::string add(size, '0');
	if (num1.size() > num2.size())
	{
		num2.insert(0, size - num2.size(), '0');
	}
	else if (num1.size() < num2.size())
	{
		num1.insert(0, size - num1.size(), '0');
	}

	int carry = 0;
	for (int i = size - 1; i >= 0; i--)
	{
		add[i] = (num1[i] - '0') + (num2[i] - '0') + '0' + carry;
		if (add[i] > '9')
		{
			carry = 1;
			add[i] -= 10;
		}
		else
		{
			carry = 0;
		}
	}
	if (carry == 1)
	{
		add.insert(0, 1, '1');
	}

	return add;
}

int main()
{
	int n;
	cin >> n;
	vector<string> v(n, "0");
    if(n == 1)
    {
        cout << "1" << endl;
        return 0;
    }
	v[0] = "1";
	v[1] = "2";
	for (int i = 2; i < n; i++)
	{
		v[i] = add(v[i - 1], v[i - 2]);
	}
	cout << v[n - 1] << endl;
	return 0;
}


发表于 2020-04-24 12:39:52 回复(0)
c++写的,用的vector
#include<iostream>
(720)#include<vector>
using namespace std;
void jumpFloor(int number) {
        if(number==0 || number==1)
        {
            cout<<1<<endl;
            return;
        }
        vector<int> dp,dp1,dp2;
        dp1.push_back(1);
        dp2.push_back(1);
        for(int i=2;i<=number;i++)
        {
            int tmp_sum,c=0,l_dp1,l_dp2;
            l_dp1=dp1.size();
            l_dp2=dp2.size();
            vector<int> tmp_dp;
            for(int i=0;i<l_dp1;i++)
            {
                tmp_sum=dp1[i]+dp2[i]+c;
                tmp_dp.push_back(tmp_sum%10);
                c=tmp_sum/10;
            }
            if(l_dp1==l_dp2 && c!=0)
                tmp_dp.push_back(c);
            else
                for(int i=l_dp1;i<l_dp2;i++)
                {
                    tmp_sum=dp2[i]+c;
                    tmp_dp.push_back(tmp_sum%10);
                    c=tmp_sum/10;
                }
            dp.assign(tmp_dp.begin(), tmp_dp.end());
            dp1.assign(dp2.begin(), dp2.end());
            dp2.assign(dp.begin(), dp.end());
        }
        for(int i=dp.size()-1;i>=0;i--)
            cout<<dp[i];
        cout<<endl;
}
int main()
{
    int n;
    cin>>n;
    jumpFloor(n);
    return 0;
}

发表于 2020-04-18 14:56:56 回复(0)
吐了,一直报错,原来是因为js除法不是自动取整的...C++写多了...一直找bug
另外pop前一定要判断长度,否则undefined
parseInt把字符,字符串,浮点数转成整数,只从头开始保留整数部分
字符串加法,注意临界值,即结果的最前面一位数字,有可能是进位的,所以
while(aa.length||bb.length||c)
let n =readline()
		function add(a,b){
			a=a+""
			b=b+""
			let aa = a.split('')
			let bb = b.split('')
			let c = 0
			let res = ""
			while(aa.length||bb.length||c){
				var a1=0,b1=0
				a1= aa.length?parseInt(aa.pop()):0
				b1 = bb.length?parseInt(bb.pop()):0
				c = c + a1 + b1
				res = c%10 + res
				c = parseInt(c/10)
			}
			return res
		}
		function f(n){
			if(n==1||n==2)
				return n
			if(n>2){
				let n1="1";
				let n2="2";
				
				let n3=""
				for(let i=3;i<=n;i++){
					n3=add(n1,n2);
					n1=n2;
					n2=n3;
					
				}
				return n3
			}
		}
		print(f(n))


发表于 2020-03-03 11:23:53 回复(0)
#include <iostream>
#include <vector>
#include <string>

using namespace std;
string sum(string a, string b){
    string ans = "";
    int i = (int)a.length() - 1, j = (int)b.length() - 1;
    int carry = 0;
    while(i>=0 || j>=0 || carry){
        int x = (i>=0)?(a[i]-'0'):(0);
        int y = (j>=0)?(b[j]-'0'):(0);
        int p = x + y + carry;
        carry = p / 10;
        ans.insert(ans.begin(), (p % 10) + '0');
        i--;
        j--;
    } 
    if(carry)
        ans.insert(ans.begin(), carry + '0');
    return ans;
}
int main(){
    int n;
    while(cin >> n){
        vector<string> dp(n+1);
        dp[0] = "1";
        dp[1] = "1";
        for(int i = 2; i <= n; i++){
            dp[i] = sum(dp[i-1], dp[i-2]);
        }
        cout<<dp[n]<<endl;
    }
}

编辑于 2020-02-27 21:45:25 回复(0)
//#include "utils.cpp"
#include <bits/stdc++.h>
//freopen("temp.in","r",stdin);
using namespace std;
#include <bits/stdc++.h>
//freopen("temp.in","r",stdin);
using namespace std;

//大数加法  注意进位

struct BigInteger{
    vector<int> data;
    int size;
    BigInteger(){}
    BigInteger(int val){
		data.resize(0);
        size = 0;
        while(val){
            data.push_back(val%10);
            val/=10;
            size++;
        }
    }
    BigInteger(const BigInteger &b){
        size = b.size;
        data.assign(b.data.begin(),b.data.end());
    }
    friend ostream& operator<<(ostream &out,const BigInteger &b){
        for(int i=b.size-1;i>=0;i--){
            out<<b.data[i];
        }
        return out;
    }
    
};

BigInteger add(BigInteger a,const BigInteger b){
    for(int i=0;i<b.size;i++){
        if(i==a.size){
            a.size+=1;
            a.data.push_back(b.data[i]);
        }else{
            a.data[i]+=b.data[i];
            if(a.data[i]>9){
                if((i+1)==a.size){
                    a.size+=1;
                    a.data.push_back(1);
                }else{
                    a.data[i+1]+=1;
                }
                a.data[i]%=10;
            }
        }
    }
    if(a.data[a.size-1]>9){
        a.data.push_back(1);
        a.data[a.size-1]%=10;
        a.size++;
    }
    return a;
}
int main(){
	//freopen("temp.in","r",stdin);
    int n;
    cin>>n;
    vector<BigInteger> dp(n+5);
    dp[1] = BigInteger(1);
    dp[2] = BigInteger(2);
	//PR(dp[1],dp[2]);
    for(int i=3;i<=n;i++){
        dp[i] = add(dp[i-1],dp[i-2]);
		//PR(i,dp[i]);
    }
    cout<<dp[n]<<endl;
    return 0;
}

发表于 2020-02-19 22:37:12 回复(0)