【面试题】剑指offer09--菲波那切数列中的变态青蛙问题

「爱情、让人受尽委屈。」 2022-06-14 07:57 114阅读 0赞

斐波那契数列中延伸的有变态青蛙的问题

问题是这样的，一只青蛙一次可以跳上一级台阶，也可以跳上两级，  
求该青蛙跳上一个n级的台阶有多少种跳法

先画一个图来看一下这个问题：

![Center][]![Center 1][]![Center 2][]![Center 3][]

下来实现一下代码：

//Q：菲波那切数列中的扩展：变态青蛙问题
    //一只青蛙一次可以跳上一级台阶，也可以跳上两级，
    //求该青蛙跳上一个n级的台阶有多少种跳法
    #include<iostream>
    using namespace std;
    long long Sum(int n)
    {
    	int arr[2] = { 0, 1 };
    	if (n < 2)
    	{
    		return arr[n];
    	}
    	long F1 = 1;
    	long F2 = 0;
    	long ret = 0;
    	for (unsigned int i = 0; i <= n; i++)
    	{
    		ret = F1 + F2;
    		F2 = F1;
    		F1 = ret;
    	}
    	return ret;
    }
    int main()
    {
    	int n = 0;
    	int result = 0;
    	cout << "请输入台阶的阶数：";
    	cin >> n;
    	result = Sum(n);
    	cout << "青蛙跳上" << n << "阶的台阶需要" << result << "种跳法"<<endl;
    	system("pause");
    	return 0;
    }

运行的结果：

![Center 4][]![Center 5][]

[Center]: https://img-blog.csdn.net/20170614124821770?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20170614124826463?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20170614124831880?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: /images/20220614/762d8008e8ae4cf88e5c70554083dc22.png
[Center 4]: https://img-blog.csdn.net/20170614130825006?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: /images/20220614/bfcf62b897014bf79491ca9cb27ce81e.png