学习用品

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M

只是空行用

题目分析

对于本题,每次只有跳1阶或者跳2阶的跳法

1)假定第一次跳1阶,那么就剩下n-1个台阶,有f (n-1) 种跳法;

2)假定第一次跳2阶,那么剩下的是n-2个台阶,有f (n-2) 种跳法;

由上述可知,总共有f (n) = f (n-1) + f (n-2)种跳法。

熟悉吗?是的,就是斐波那契序列。

这道题考的并不是如何去递归,或是如何去排列组合。虽然这两种方法确实可以解决问题,但解答的手法上就没有那么高效。这一题主要考察的能力就是对题目的建模分析和对已知模型的运用。如果能意识到这是一个斐波那契序列模型,作答就会得心应手。

只是空行用

代码

int jumpFloor(int number) {
    int f = 1, g = 2; //第1项和第2项
    number--;
	while (number--)
	{
		g += f; //后项=前项+前前项 
		f = g - f; //前项=后项-前前项
		//由于f默认是第0项,所以在这里f比g滞后一项
	}
	return f;
}

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注