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

输入描述:
一个正整数,表示这个楼梯一共有多少阶


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

输入

100

输出

24382819596721629

备注:
注意时间限制
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        BigInteger[] count = new BigInteger[n];
        count[0] = new BigInteger("1");
        count[1] = new BigInteger("1");
        count[2] = new BigInteger("2");
        for (int i = 3; i < n; i++) {
            count[i] = count[i - 1].add(count[i - 3]);
        }
        System.out.println(count[n - 1]);
    }
}
编辑于 2019-07-15 17:02:40 回复(2)
python的int型无限大(只要内存够) 因此这种题python是最好的选择
简单的动态规划
arr = [0 for i in range(int(input()) + 1)]
arr[0], arr[1], arr[2] = 1, 1, 1
for i in range(3, len(arr)):
    arr[i] = arr[i-1] + arr[i-3]
print(arr[-1])


发表于 2019-12-26 11:59:29 回复(0)
矩阵快速幂
def matmul(A, B):
    C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][j] += (A[i][k] * B[k][j])
    return C

def mat_power(A, count):
    B = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    while (count > 0) :
        if count % 2 == 1:
            B = matmul(B, A)
        A = matmul(A, A)
        count //= 2
    return B

def work():
    n = int(input())
    f = [0 for i in range(n + 1)]
    f[0] = f[1] = f[2] = 1
    f[3] = 2
    if n <= 3:
        print(f[n])
        return
    A = [[f[2], f[0], f[1]], [f[3], f[1], f[2]], [0, 0, 0]]
    B = [[1, 0, 1], [1, 0, 0], [0, 1, 0]]
    count = n - 2 - n % 2
    B = mat_power(B, count)
    B = matmul(A, B)
    if n % 2 == 1:
        print(B[1][0])
    else:
        print(B[0][0])
work()




发表于 2019-11-02 14:13:18 回复(0)
#include <bits/stdc++.h>
using namespace std;
string addstr(string str1,string str2){
    string &longstr=str1.size()>=str2.size()? str1:str2;
    string &shortstr=str1.size()<str2.size()? str1:str2;
    string sum;
    shortstr.insert(0,longstr.size()-shortstr.size(),'0');//对齐位数
    sum.resize(str1.size()+str2.size());    //预留空间
    int up=0,i=shortstr.size()-1,j=longstr.size()-1,k=sum.size()-1;
    while(i>=0){
        int temp=shortstr[i--]-'0'+longstr[j--]-'0';
        sum[k--]=(temp+up)%10+'0'; //只保存个位
        up=(temp+up)/10;    //保存进位
    }
    if(up!=0)
        sum[k--]=up+'0';
    sum=sum.substr(k+1);
    return sum;
}
int main(){
    int n;
    cin>>n;
    vector<string> dp;
    dp.resize(n+1);
    dp[0]=dp[1]=dp[2]="1";
    for(int i=3;i<=n;i++){
        dp[i]=addstr(dp[i-1],dp[i-3]);
        cout<<dp[i]<<endl;
    }
    cout<<dp[n];
}


编辑于 2019-10-21 08:57:10 回复(0)
import sys
def diffroad(n):
    # n<3  索引位置:n-1
    # n>=3  索引位置:(n-1)%3
    res = [1,1,2]
    if n<3:
        return 1
    if n==3:
        return 2
    # f(n) = f(n-1)+f(n-3)
    for i in range(4,n+1):
        res[(i-1)%3] += res[(i+1)%3]
    return res[(n-1)%3]

if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    print(diffroad(n))
    

编辑于 2019-09-07 22:34:25 回复(0)
python做大数据的题和作弊差不多
steps = int(input())
count = [1, 1, 2]
for i in range(4, steps + 1):
    count[(i - 1) % 3] += count[(i + 1) % 3]
print(count[(steps - 1) % 3])


发表于 2019-08-29 15:48:27 回复(0)

【企业真题】【小米】爬楼梯2

思路:

    使用排列组合(杀死脑细胞),考虑一次跳3级,两次跳3级,......以此类推

代码:

    
import sys

try:
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break
        n=int(line)
        if 100<=n<500:
            sum=0
            for i in range(1,n//3):
                res=1
                for j in range(2*i,3*i):
                    res*=(n-j)
                for k in range(1,i+1):
                    res//=k
                sum+=res
            if n%3==0:
                sum+=2
            elif n%3==1:
                sum+=n//3+2
            else:
                res=1
                for i in range(1,n//3+1):
                    res=res*(n//3+3-i)//i
                sum+=res+1
            print(sum)
except:
    pass


参考评论区的思路:

    找规律,发现:f(n)=f(n-1)+f(n-3)

代码:

    
line = input()
if line == '':
    print(None)
n = int(line)
if 100 <= n < 500:
    a = [1, 1, 2]
    for _ in range(n-3):
        a = [a[1], a[2], a[0] + a[2]]
    print(a[2])


发表于 2019-08-22 17:20:32 回复(0)
#include<bits/stdc++.h>
using namespace std;
string dp[500];
// dp,用字符串就好
string add(string a,string b)
{
    while(a.size()<b.size())
        a = '0' + a;
    while(b.size()<a.size())
        b = '0' + b;
    int len = a.size();
    int carry = 0;
    string res = "";
    for(int i=len-1;i>=0;i--)
    {
        int temp = carry + a[i] - '0' + b[i] - '0';
        res = to_string(temp%10) + res;
        carry = temp/10;
    }
    while(carry)
    {
        res = to_string(carry%10) + res;
        carry/=10;
    }
    return res;
}
int main()
{
    //memset(dp,0,sizeof(dp));
    dp[0]="1";
    dp[1]="1";
    dp[2]="1";
    int n;
    cin>>n;
    for(int i=3;i<=n;i++)
        dp[i]=add(dp[i-3],dp[i-1]);
    cout<<dp[n]<<endl;
    return 0;
}

发表于 2019-08-16 18:39:05 回复(0)

大数题用python很犯规,引入滚动数组

steps = int(input())

count = [1,1,2]
for i in range(4,steps+1):
    temp = count[0]+count[2]
    count[0] = count[1]
    count[1] = count[2]
    count[2] = temp

print(count[-1])
发表于 2019-08-07 15:07:51 回复(0)
n = int(input())
a = [0]*(n+1)
for i in range(3):
    a[i] = 1
for i in range(3, n+1):
    a[i] = a[i-1] + a[i-3]
print(a[n])

发表于 2019-07-31 23:22:53 回复(0)
"""
台阶问题考虑动态规划
每次仅可往上爬1或3级台阶
当前台阶方法数 = 所有一次可到达当前台阶方法数的和
dp[n] = dp[n-1]+dp[n-3]  ( n-t>=0,dp[0]=1 )
"""
if __name__ == "__main__":
    n = int(input().strip())
    dp = [1, 1, 1]
    for i in range(3, n + 1):
        dp.append(dp[i - 1] + dp[i - 3])
    print(dp[n])

发表于 2019-07-16 11:54:47 回复(1)
n = int(input())
res = [0]*(n+1)
res[1],res[2],res[3] = 1,1,2
for i in range(4,n+1):
    res[i] = res[i-1]+res[i-3]
print(res[n])

发表于 2019-07-13 10:20:45 回复(0)
C++ 用long 保存返回结果,n=499时,还是溢出了,应该怎么保存比64位数还大的数呢?
发表于 2020-02-20 19:30:39 回复(0)
C++就必须用字符串加法,哎,难受

#include<iostream>
#include<string>
using namespace std;
string cal2(string a, string b) {
    int m = a.size(), n = b.size(), index = 0, temp = 0;
    if (m < n) { string c = a; a = b; b = c; temp = m; m = n; n = temp; }
    for (int i = 1; i <= n; ++i) {
        temp = a[m - i] - '0' + b[n - i] - '0'+index;
        if (temp >= 10) { a[m - i] = a[m - i] + b[n - i] - '0' + index - 10; index = 1; }
        else { a[m - i] = a[m - i] + b[n - i] - '0' + index; index = 0; }
    }
    for (int i = n + 1; i <= m; ++i) {
        temp = a[m - i] - '0' + index;
        if (temp >= 10) { a[m - i] = a[m - i] + index - 10; index = 1; }
        else { a[m - i] = a[m - i] + index; index = 0; break; }
    }
    if (index == 1)a = "1" + a;
    return a;
}
string cal(int n) {
    if (n <= 0)return "0";
    if (n <= 2)return "1";
    if (n == 3)return "2";
    string* a = new string[n];
    a[0] = "1";
    a[1] = "1";
    a[2] = "2";
    int i = 3;
    string sum = "";
    for (; i<n; ++i) {
        sum = "";
        sum = cal2(sum, a[i - 1]);
        sum = cal2(sum, a[i - 3]);
        a[i] = sum;
    }
    sum = a[i - 1];
    delete[] a;
    a = NULL;
    return sum;
}
int main() {
    int* a, n;
    while (cin >> n) {
        cout << cal(n) << endl;
    }
    return 0;
}
发表于 2020-02-03 20:10:12 回复(0)
import sys #n = int(input("输入楼梯阶数:")) n = int(sys.stdin.readline())
m = n // 3 result =0 def jc(w): if w<=1: return 1  else: return w*jc(w-1) for i in range(1,m+1):
    t = n-2*i
    result += jc(t)/(jc(t-i)*jc(i)) print(int(result+1))大佬 我这个是哪里错了
发表于 2019-10-26 10:57:22 回复(0)

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

public class Main{

    public static void main(String []args){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = 100;
        try{
            input = Integer.parseInt(br.readLine());
        }catch(IOException e){
            e.printStackTrace();
        }
        BigInteger first = BigInteger.valueOf(1);
        BigInteger second = BigInteger.valueOf(1);
        BigInteger third = BigInteger.valueOf(2);
        BigInteger result = BigInteger.valueOf(0);
        for(int i=4;i<=input;i++){
            result = first.add(third);
            first = second;
            second = third;
            third = result;
        }
        
        System.out.println(result);
    }
}
通过找规律得来的,不知道是不是用递归怎么弄,递归是不是一定会超时

发表于 2019-10-25 16:37:15 回复(0)
import java.util.Scanner;
import java.math.BigInteger;
import java.util.Arrays;

public class Main {
   static BigInteger[] a;
    public static BigInteger getRes(int k) {
        if(k==2 ||k==1||k==0){
            return new BigInteger("1");
        }
        if(k>2){
            if(0==a[k-3].compareTo(new BigInteger("0"))){
                a[k-3]=getRes(k-3);
                return getRes(k-1).add(getRes(k-3));
            }
            return getRes(k-1).add(a[k-3]);
           }
        return new BigInteger("0");
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        a = new BigInteger[q];
        Arrays.fill(a,BigInteger.ZERO);
        BigInteger count = getRes(q);
        System.out.print(count);
    }
}
发表于 2019-09-17 14:43:40 回复(0)
#include <bits/stdc++.h>
using namespace std;

void StrAdd(string& sum, string &a, string &b){
    int carry = 0;
    int a_num, b_num;
    string::iterator a_iter, b_iter;
    for(a_iter = a.begin(), b_iter = b.begin(); a_iter != a.end() && b_iter != b.end(); ++a_iter, ++b_iter){
        a_num = *a_iter - '0';
        b_num = *b_iter - '0';
        sum.append(1, '0'+(a_num + b_num + carry)%10);
        carry = (a_num + b_num + carry) / 10;
    }
    while(a_iter != a.end()){
        a_num = *a_iter - '0';
        sum.append(1, '0'+(a_num + carry)%10);
        carry = (a_num + carry) / 10;
        ++a_iter;
    }
    while(b_iter != b.end()){
        b_num = *b_iter - '0';
        sum.append(1, '0'+(b_num + carry)%10);
        carry = (b_num + carry) / 10;
        ++b_iter;
    }
    if(carry)
        sum.append(1, '1');
    return;
}

int main(void){
    int x;
    vector<string> dp(501);
    dp[0] = "1";
    dp[1] = "1";
    dp[2] = "1";
    cin>>x;
    for(int i =3; i < 501; ++i)
        StrAdd(dp[i], dp[i-1], dp[i-3]);
    reverse(dp[x].begin(), dp[x].end());
    cout<<dp[x]<<endl;
    return 0;
}
字符串实现的大数相加
发表于 2019-09-06 20:37:14 回复(0)
python 3
tmp=[1,1,1]
N=int(input())
for i in range(N-2):
    tt=tmp[0]+tmp[2]
    tmp[0]=tmp[1]
    tmp[1]=tmp[2]
    tmp[2]=tt

print(tmp[2])


发表于 2019-09-03 10:59:44 回复(0)
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int number;
    cin >> number;
    int a = 0, b = 1, c = 2;
    vector<vector<char>> vvData(3, vector<char>{1});

    for(int curNum = 3; curNum <= number; curNum++)
    {
        int d = (c+1)%3;
        a = b;
        b = c;
        c = d;

        int carry = 0;
        for(size_t i=0; i < vvData[c].size() || i < vvData[b].size() || carry!=0; i++)
        {
            if(i >= vvData[c].size())
                vvData[c].push_back(0);
            vvData[c][i] += ((i < vvData[b].size())?vvData[b][i]:0) + carry;
            carry = vvData[c][i]/10;
            vvData[c][i] = vvData[c][i]%10;
        }
    }

    for(auto iter = vvData[c].rbegin(); iter!=vvData[c].rend(); iter++)
        cout << (int)(*iter);
    cout << endl;
    
    return 0;
}

发表于 2019-09-02 16:54:55 回复(0)