Day6 DFS

一、跳台阶

一个楼梯共有 nn 级台阶，每次可以走一级或者两级，问从第 00 级台阶走到第 nn 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 nn。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

1≤n≤15
 

#include<iostream>
using namespace std;int n;int fibonaci(int x){switch(x){case 1: return 1;break;case 2: return 2;break;default:return fibonaci(x - 1) + fibonaci(x - 2);}
}int main(){scanf("%d",&n);int ans = fibonaci(n);printf("%d\n",ans);return 0;
}

二、递归实现指数型枚举

从 1∼n1∼n 这 nn 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 nn。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

 

#include <bits/stdc++.h> 
using namespace std;const int N = 20;int n;
int st[N]; // 0: 未处理，1: 选中，2: 未选void dfs(int x) {if (x > n) {for (int i = 1; i <= n; i++) { // 保持原循环范围
//值得注意的是因为题目要求n的取值范围是1-15，所以i应该从1开始遍历if (st[i] == 1) {printf("%d ", i);}}printf("\n");return ;}// 不选分支st[x] = 2;dfs(x + 1);st[x] = 0; // 修正此处恢复状态// 选分支st[x] = 1;dfs(x + 1);st[x] = 0; // 恢复状态
}int main() {scanf("%d", &n);dfs(1);return 0;
} 

 

三、全排列问题

题目描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由 1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。