爬楼梯问题

致自己:我不知道怎样才能成为大神,但是如果你不开始行动,永远不会有进步

有这样一个问题,总共有6个台阶,一次可以迈出1步或者2步,有多少种方式爬完楼梯?

问题分析如下图:

爬楼梯分析图

从开始直到走完整个楼梯,每一次都可以选择迈出1步或者2步,因此我们解决问题采用递归的思想,编程实现如下

php版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?php

$way = 0;

function mul_road_search($steps, &$way, array $choices, $current = 0)
{
if ($steps == $current) {
$way += 1;
}

if ($current < $steps) {
foreach ($choices as $choice) {
mul_road_search($steps, $way, $choices, $current + $choice);
}
}
}

mul_road_search(6, $way, [1, 2], 0);

print_r($way);

python 版本:

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
#!/usr/local/python3/bin/python3

# encoding: utf-8

all_ways = 0


def mul_road_search(steps, choices, current=0):
"""
多路搜索算法描述
:param step int 总共要走的楼梯数目
:param choices list 一次可以迈出的步数
:param current 当前已经走完的楼梯数
"""
global all_ways

if steps == current:
all_ways += 1

if current < steps:
for each_step in choices:
mul_road_search(steps, choices, current + each_step)

mul_road_search(6, [2, 1])

print(all_ways)

C++版本:

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
#include <iostream>

using namespace std;

void mul_road_search(int, long long *, int [], int current = 0);

int main()
{
long long all_ways = 0;
int choices[2] {1, 2};
mul_road_search(50, &all_ways, choices);
cout << all_ways;
return 0 ;
}

void mul_road_search(int steps, long long * all_way, int choices[], int current)
{
if (current == steps) {
*all_way += 1;
}

if (current < steps) {
for (int i = 0; i < 2; i++) {
mul_road_search(steps, all_way, choices, current + choices[i]);
}
}
}