admin 管理员组

文章数量: 887031

练习题

问题描述

有一楼梯共m级，刚开始时你在第0级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

注：规定从一级到一级有0种走法。

 

输入

输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40), 表示楼梯的级数。

 

输出

对于每个测试实例，请输出不同走法的数量。

样例输入

2

2

3

样例输出

2

3

思路

用迭代法计算出上台阶的种类，例如一共有m阶，第一步上一阶台阶，后面还有m-1阶要走；第一步上两阶台阶，后面还有m-2阶要走

代码

import java.util.*;
/*** 上台阶问题，假设有m节台阶，现在在第0节台阶上，一次可上1节或2节台阶。输入样例个数n，再输入每个样例（台阶的个数），输出对应的上台阶的方法* n属于1-100，m属于1-40* 使用迭代法* @author yangc_cong**/
public class UpSteps {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int i = 0; i<n; i++) {int m = sc.nextInt();System.out.println(Compute(m));}sc.close();}/*** 迭代法计算上台阶的种类* @param steps 台阶数* @return 返回种类个数*/public static int Compute(int steps) {if(steps==1)return 1;if(steps==2)return 2;return Compute(steps-1)+Compute(steps-2);}
}

别人的解答

用了两种方法，迭代和递归，迭代的时间开销较少，推荐使用

  • 迭代的思路是：上n阶的种类是，n-1的种类加上n-2的种类，使用for循环来算。
  • 迭代看起来跟递归的思路是一样的，但迭代是从1到n，递归是从n到1
int a = 1;//1个台阶的种类是1int b = 2;//2个台阶的种类是2int result = 0;for(int step = 3; step<=n; step++){result = a+b; a = b;        //下一轮循环中step-2的种类b = reslut;    //下一轮循环中step-1的种类
}
return result;

延伸 变态跳台阶

问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路

  • 思路1：插板法，有n个台阶，那么就有n-1个空隙，每个空隙都有插板和不插板两种选择，则情况个数为2^(n - 1)

  • 思路2：易知 f(n)=f(n-1)+f(n-2)+……f(1) ；f(n-1)=f(n-2)+……f(1) ；两式相减得f(n)=2f(n-1)  思路2

public class Solution {public int JumpFloorII(int target) {if(target==0)return 0;return (int)Math.pow(2, target-1);}
}

 

本文标签： 练习题

版权声明：本文标题：练习题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686566885h11210.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。