走楼梯问题_哥白尼_的博客-程序员宝宝_走楼梯问题

技术标签: JAVA基础  算法很美  

问题:有一个小孩在上楼梯,楼梯有n阶,小孩一次可以上1阶、2阶、3阶,请实现一个方法,计算小孩有多少种上楼的方式

 

package 递归;
import java.util.Scanner;
/**
 * 
 * 
 * 如果有1个台阶,走法有一种(一步走1个台阶) 即f(1)=1
 * 如果有2个台阶,走法有2种(一种是上1阶,再上1阶,另一种是一步上2阶) 即f(2)=2
 * 如果有3个台阶,走法有3种(f(1)+f(2)),就是在走了2阶了,然后最后一阶该怎么走 那就加上f(1)呗
 * 当有n个台阶(n>3)时,我们缩小问题规模,可以这样想:最后是还剩1个台阶了,之前已经走了(n-1)个台阶 有f(n-1)种走法
 * 如果最后还剩2个台阶,之前走了(n-2)个台阶,那就有f(n-2)种走法
 * 
 * 
 * @author Ad
 *
 */
public class 走阶梯1 {
	private static int num;
	static int mod=1000000007;
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int num=input.nextInt();
//		method(num);
		System.out.println(method(num,mod));
	}

	private static int  method(int num,int mod) {
		if (num==1) {
			return 1;
		}
		if(num==2){
			return 2;
		}
		return method(num-1,mod)%mod+method(num-2,mod)%mod;
	}

}
package 递归;
import java.util.Scanner;
/**
 *有一个小孩在上楼梯,楼梯有n阶,小孩一次可以上1阶、2阶、3阶
 *请实现一个方法,计算小孩有多少种上楼的方式
 * 
 * @author Ad
 *
 */
public class 走阶梯2 {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int num=input.nextInt();
//		method(num);
		System.out.println(method(num));
	}
	private static int  method(int num) {
		int mod=1000000007;  //为了防止溢出,结果求模 mod 1000000007
		if(num==1) return 1;
		if(num==2) return 2;
		if(num==3) return 4;
		int x1=1;
		int x2=2;
		int x3=4;
		for (int i = 4; i <=num; i++) {
			int x_1=x1;
			x1=x2;
			x2=x3;
			x3=(((x1+x2)%mod)+x_1)%mod;
		}
		return x3;
	}

}


//
// num: 1	2	3	4	5	x6
// 		x1  x2  x3
//          x1  x2  x3
//          	x1  x2   x3
		

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45039471/article/details/92801014

智能推荐

CSDN超级实习生是指CSDN在招实习生吗?还是别的意思?_计算机考研的博客-程序员宝宝

近期多位用户反馈以为我们CSDN在招实习生,实际上CSDN也在招超级实习生,其他百度、阿里、腾讯都在招,超级实习生计划实习企业不限CSDN,达到用人标准可进各类互联网大厂,为了避免造成用户理解,下文小编将针对“CSDN超级实习生”做个简要介绍。

消息队列(MSMQ)学习_weixin_30715523的博客-程序员宝宝

直到今天才知道,在我们每天都在用的Window系统里还有这么好用的一个编程组件:消息队列.它能够解决在大数据量交换的情况下的性能问题,特别是BS系统的数据库性能.而且它的异步处理方式能给程序员最大的便利与最好的用户体验. 1.首先在需要进行消息队列的服务器上安装MSMQ,我的系统是win2003+iis6,所以这个安装选项在添加删除程序-&gt;windows组件-&gt;应用程序...

Navicat获取注册码_weixin_30767921的博客-程序员宝宝

产品适用:Navcat产品+中文版+64位注册机百度网盘链接: https://pan.baidu.com/s/1H49nNga9h0WHWKGWAGy18g 提取码: ri5d1、cmd进入注册机目录执行命令navicat-patcher.exe "D:\Program Files\PremiumSoft\Navicat Premium 12"(navicate的目录)2、执行...

HTML,CSS,font-family:中文字体的英文名称_F12578626的博客-程序员宝宝

宋体SimSun黑体SimHei微软雅黑Microsoft YaHei微软正黑体Microsoft JhengHei新宋体NSimSun新细明体PMingLiU细明体MingLiU标楷体DFKai-SB仿宋FangSong楷体KaiTi仿宋

随便推点

LuoguP2759奇怪的函数_hhuhao的博客-程序员宝宝_奇怪的函数 xx.cpp 数据

先来推一下: ∵log10xx>n−2∵log_{10}x^x>n-2 ∴x∗log10x>n−2∴x*log_{10}x>n-2 ∵x,log10x∵x,log_{10}x都是单调递增的 ∴x∗log10x∴x*log_{10}x是单调递增的

Windows界面编程第五篇 静态控件背景透明化_Fields_Of_Gold的博客-程序员宝宝

上一篇《Windows界面编程第三篇 异形窗体 普通版》和《Windows界面编程第四篇异形窗体 高富帅版》介绍了异形窗口(异形窗体)的创建,并总结出了异形窗口的“三要素”:1.WS_EX_LAYERED属性2.指定透明色3.以位图为窗口背景    本篇文章将主要介绍Windows编程中如何实现静态控件背景的透明化,这将进一步的美化界面。下面先看一张没有做静态控件背景透

lora终端连接云服务器_一种LoRa服务器及其数据传输方法与流程_weixin_39746382的博客-程序员宝宝

本发明涉及Lora技术领域:,尤其涉及一种LoRa服务器及其数据传输方法。背景技术::LoRaWAN是为LoRa远距离通信网络设计的一套通讯协议和系统架构。Lora通信系统通常包含终端、基站、网络服务器、应用服务器这四个部分。基站和终端之间采用星型网络拓扑,由于LoRa的长距离特性,它们之间得以使用单跳传输。终端节点可以同时发给多个基站,基站则对网络服务器和终端之间的LoRaWAN协议数据做转发处...

嵌入式系统学习-------1.什么是嵌入式系统?_迎着黎明那道光的博客-程序员宝宝_什么是嵌入式系统

什么是嵌入式系统?我们在日常的生活当中经常会听说到嵌入式应用,而在物联网的发展下,嵌入式的应用也变得更加多样起来,我们不禁会有一个疑问,什么是嵌入式系统,下面我们一起学习一下。嵌入式系统定义简单的讲,嵌入式系统就是嵌入到对象体中的专用计算机系统。它包含了嵌入、专用、计算机这三个要素。而广义的讲,嵌入式系统也就是具备某些功能的软硬件结合体。以应用为中心、以计算机技术为技术、软件硬件可裁剪、适...

idea创建maven项目中文乱码_代码搬运工呀的博客-程序员宝宝_idea maven乱码

IDEA创建maven项目时控制台输出中文乱码?在网上找了很多方法,搞了好一会才解决(我自己粗心造成的),现在来总结一下:1.IDEA-Help-Edit Custom VM Options-粘贴一句话:-Dfile.encoding=utf-8然后重启。2.File-Settings-Editor-FileEncodings中的三个选项都设置为UTF-8:3.找到IDEA安装路径下的bin目录中的idea.exe.vmoptions和idea64.exe.vmoptions文件,打开并在末

字符串表情替换_麻豆_matou的博客-程序员宝宝

博主最近在研究IM的实现,不想直接使用第三方的界面,于是就开始了自己的作死之路。今天把包含表情格式的文本转换成相应的富文本贴一下吧。首先,博主的表情格式是现在常用的中括号+标志符,类似[11]就是一个表情格式的字符。 我们需要实现的功能就是把形如: 你好[11] 这样的字符串变成: 你好 这样的字符串,具体的步骤就不再叙述了,注释已经很详细了/// 将字符串转换为含有表情的富文本...

推荐文章

热门文章

相关标签