40 lines
947 B
C++
40 lines
947 B
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 110;
|
||
int a[N];
|
||
int n;
|
||
int ways;
|
||
|
||
/**
|
||
* @param step 走了几次
|
||
* @param level 现在站在第几阶台阶上
|
||
* N阶楼梯上楼问题：一次可以走两阶或一阶，请把所有行走方式打印出来。
|
||
* 测试数据: 5 输出结果 一共有8种走法
|
||
* 测试数据: 15 输出结果 一共有987种走法
|
||
* 方案 ：回溯法+递归
|
||
*/
|
||
void dfs(int level, int step) {
|
||
if (level == n) {
|
||
ways++;
|
||
//输出结果
|
||
for (int i = 0; i < step; i++)printf("%d\t", a[i]);
|
||
printf("\n");
|
||
}
|
||
//2种分枝
|
||
for (int i = 1; i <= 2; i++) {
|
||
//可行
|
||
if (level + i <= n) {
|
||
a[step] = i;//记录解向量
|
||
dfs(level + i, step + 1);
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
cin >> n;
|
||
dfs(0, 0);
|
||
printf("一共 %d 种方法。\n", ways);
|
||
return 0;
|
||
}
|