【递归】楼梯的走法

65 阅读 0 评论 43 点赞

我是靠谱客的博主无奈草丛，这篇文章主要介绍【递归】楼梯的走法，现在分享给大家，希望可以做个参考。

题目描述

假设有n阶楼梯，小明一次可以选择走1阶，也可以选择走2阶，问多少种走法。比如有5阶台阶，共有8种走法。

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1

1 2 2

2 1 1 1

2 1 2

2 2 1

要求使用递归解法。

输入描述

输入n，表示n阶楼梯，1<=n<=40

输出描述

输出楼梯的走法总数。

样例输入

复制代码

1
5

样例输出

复制代码

1
8

分析：找递推，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5 ——> f(n) = f(n - 1) + f(n - 2)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "pch.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int ways(int n);

int main()
{
	int n;
	cin >> n;
	if (n >= 1 && n <= 40)
	{
		cout << ways(n) << endl;
	}
	return 0;
}

int ways(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else
	{
		return ways(n - 1) + ways(n - 2);
	}
}