C/C++教程

第二部分 基础算法——C++一本通:第四章 递归算法:1204:爬楼梯(讲解)

本文主要是介绍第二部分 基础算法——C++一本通:第四章 递归算法:1204:爬楼梯(讲解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1204:爬楼梯

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 18652     通过数: 9894
【题目描述】
树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数。

例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共3种方法。

【输入】
输入包含若干行,每行包含一个正整数N,代表楼梯级数,1≤N≤30。

【输出】
不同的走法数,每一行输入对应一行输出。

【输入样例】
5
8
10
【输出样例】
8
34
89

本题是要使用递归的,但是,要先知道递归的特征。

递归的特征是一个问题的求解需要一系列的计算,这一系列的计算存在着某种关联。

所以,我们要先找到关联。

关联如下:

/*1 台阶数 
  1     方法数     
  2 台阶数 
11 2  方法数 
 3   
111 12 21
   4
1111 112 121 211 22
   5
11111 1112   1121 1211 2111 221 212 122
*/

可得1=1

        2=2

        3=3

        4=5

        5=8

就可以算出关联是:n=(n-1)+(n-2)

第3项方法数=第2项方法数+第1项方法数;

所以我们先定义

long long a[50],i,n;

        a[50]是因为题目说楼梯数,虽然只说30,但保险起见,定大一点。

然后输入n,就是台阶数。再将台阶1和台阶2另外处理;

cin>>n;
	a[1]=1;
	a[2]=2;

之后就从台阶3开始算,并带入关联式:

for(i=3;i<=n;i++){
		a[i]=a[i-1]+a[i-2];
	}

最后再输出a [ n ]就好了,至于输入若干行就你们自己打吧,思路已经说了。

这篇关于第二部分 基础算法——C++一本通:第四章 递归算法:1204:爬楼梯(讲解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!