栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

AcWing 3643. 上楼梯(Java)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

AcWing 3643. 上楼梯(Java)

题目描述

一个楼梯共有 n 级台阶,每次可以走一级或者两级或者三级,问从第 0 级台阶走到第 n 级台阶一共有多少种方案。


输入

一个整数 N。

输出

一个整数,表示方案总数。

输入样例:

4

输出样例:

7

算法1

使用递归算法,比较慢,而且在一些情况下可能会超时。建议看算法2。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
    	//使用缓冲流和打印流,快读快写
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        int n = Integer.parseInt(reader.readLine());
        out.print(func(n));
        out.close();//这句话必须有,否则不会输出
    }

    private static int func(int n) {
        if (n == 0) return 1;
        if (n>0) return func(n-1)+func(n-2)+func(n-3);
        return 0;
    }
}
算法2

使用for循环,效率贼高~~~,如果栈内存溢出了就别用大整数了

import java.io.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int x = Integer.parseInt(reader.readLine());
        BigInteger p = new BigInteger("0");
        BigInteger q = new BigInteger("0");
        BigInteger m = new BigInteger("0");
        BigInteger n = new BigInteger("1");
        for (int i = 1; i <= x; i++) {
            m = p;//m表示跳到第i-3级台阶的方案数
            p = q;//p表示跳到第i-2级台阶的方案数
            q = n;//q表示跳到第i-1级台阶的方案数
            n = q.add(p).add(m);//n表示跳到第i级台阶的方案数
        }
        out.print(n);
        out.close();//这句必须有,没有不会输出
    }
}

总结

由此来看递归并不是万能的,在一些情况下会有超时和溢出,推荐还是优先选择第二种算法。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963550.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号