网站制作实验报告,福州绿光网站建设工作室,在阿里云做视频网站需要什么条件,常德网站开发哪家好没没没没没没没错#xff0c;这是一道简单的递归#xff08;其实是深搜加回溯)
我不管#xff0c;我说是递归就是递归。
上题干#xff1a; 题目描述 排列与组合是常用的数学方法#xff0c;其中组合就是从 n 个元素中抽出 r个元素#xff08;不分顺序且 r≤n#x…没没没没没没没错这是一道简单的递归其实是深搜加回溯)
我不管我说是递归就是递归。
上题干 题目描述 排列与组合是常用的数学方法其中组合就是从 n 个元素中抽出 r个元素不分顺序且 r≤n我们可以简单地将 n 个元素理解为自然数 1,2,…,n从中任取 r 个数。 现要求你输出所有组合。 例如 n5,r3所有组合为 123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。 输入格式 一行两个自然数n,r(1n21,0≤r≤n)。 输出格式 所有的组合每一个组合占一行且其中的元素按由小到大的顺序排列每个元素占三个字符的位置所有的组合也按字典顺序。 注意哦输出时每个数字需要 3 个场宽。以 C 为例你可以使用下列代码 cout setw(3) x;输出占 3 个场宽的数 x。注意你需要头文件 iomanip。 输入输出样例 输入 #1复制 5 3 输出 #1复制 1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5 我现在再次重复一遍写递归请你放空你的脑袋然后用样例画出一个草图然后用最简单的最暴力的思路去想。不要想太细太复杂。等你把递归的框架搭建完了再去思考边界。
认真看题目啊喂由于题目要求每一组数必须是从小到大的排列所以当第二个数是5的时候后面没有比5更大的所以这种组合就不存在。
第一步让我们轻轻画一个草图 这个就是以1为开头的所有排列组合
再说一遍递归题不要想太多画出一个例子就可以了想太多越想越乱。
第二步根据图像想一个巨巨巨巨巨朴素的思路最暴力的
我们从1开始往下找一共要找3个数字.
先找下一层最左边的是2此时序列就是12。
由于我们要字典序不知道字典序是什么的看一下样例给的答案。也就是 1 2 3 必须要在 1 2 4 前面 2 3 4 必须 要在 2 3 5前面这样的排序不过多解释从小到大
所以我们直接递归到下一层从下一层的最左边开始最左边最小
此时的序列就是123。
打印序列向逐渐增大移动序列变为124 继续移动序列变成125
当没有数了之后回到上一层
当 2的下一层都找完了继续向2这一层数字增大的方向走也就是12变成13。
重复此过程。 ok思路非常简单我想你们应该也能想到这样做如果大体能看懂那也很不错了相信阅读完本栏目之后你能不害怕递归。 直接上代码就完事了
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
#includenumeric
#includeiomanip
using namespace std;
const int N 30;
int t[N];
int flag[N];
int n, r;
void dfs(int x,int y) {if (y r ) { 当前序列里面的数字个数大于r的时候就停止for (int i 1; i r; i) { 打印答案cout setw(3) t[i];}cout endl;return;}for (int i x ; i n; i) 从x开始保证后面存进来的每一个数都大于xif (flag[i] 0 ) { 如果i被标记过了那么我们就不管i如果没有就把i加入到序列里面flag[i] 1; 标记it[y] i; 把i加入到序列里面dfs(i 1, y 1); 递归下一个数flag[i] 0; 递归结束之后恢复标记}
}
int main() {cin nr;dfs(1, 1); //递归从1开始第二个1代表序列里面只有1个数字
}
多么简单的一道递归啊。
