九度OJ中的变态跳台阶问题解析

你们作高中数学题的时候是否接触过这样一道题：一个青蛙要上一个n阶的台阶，一次能够跳一阶或者是两阶，求得是这只青蛙一共有多少种的跳法。html

首先咱们要对这个问题进行分析，到底该采用什么样的算法思想去进行解决，这里咱们的分析思路能够是以下的：java

假设咱们已经知道了跳上前n-1阶台阶的数目，那么剩下的惟一一个台阶咱们就只有一种跳法，假设咱们知道了前n-2阶的跳法数目，那么剩下的2阶台阶就只有两种跳法，这里咱们是否是已经知道这里我会采用递归的方式进行解决这个问题，下面附上相关代码，这里的代码上我是假设这只青蛙能够跳三阶的，算法思想是和上面同样，只是递归的跳出条件复杂了点而已。算法

public static int ClimbStairs(int n)
	{
		if(n == 3)
			return 4;
		else if(n == 2)
			return 2;
		else if(n == 1)
			return 1;
		else 
		return ClimbStairs(n-1)+ClimbStairs(n-2)+ClimbStairs(n-3);
	}

fibonacci数列分析
spa

分析过这样一个问题，我附上相关fibonacci的代码：code

public static int demo(int n)
	{
		return (n == 1||n ==0)?1:demo(n-1)+demo(n-2);
	}

咱们具体的分析思路以下：htm

若是咱们第一次跳1阶，那次数就是跳n-1阶的数目，若是咱们跳2阶，那么次数就会是跳n-2阶的数目，通过分析咱们会发现：递归

f(n)=f(n-1)+f(n-2)+f(n-3)+......+f(2)+f(1)+f(0)ci

其中咱们知道f(1)=f(0)=1get

下面就是对上面的公式进行算法实现了，具体算法以下：博客

package jiuduOJ;
import java.util.Scanner;
/**
 * 跳n阶台阶，跳的时候能够一次跳1-n个台阶，这里并无采用递归的方法进行
*@author:Mr.wang
*@version:1.0
*@time:2015/11/4
 */
public class JumpStair_n
{
	public static void main(String[] args) 
	{
		System.out.println("请输入要爬的总台阶数目n:");
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		double[] f = new double[n];
		f[0] = 1;
		f[1] = 1;
		double sum = 2;
		for(int i = 2; i <= n-1; i++)
		{
			for(int j = 0; j <= i-1; j++)
			{
				f[i]+=f[j];
			}
			sum+=f[i];
		}
		System.out.println("因此的爬台阶总数为："+sum);
	}
}