PTA《 2016 级算法设计期末考试模拟 》
题目
找出从自然数 1,2,... ,n(0<n<=30) 中任取 r(0<r<=n) 个数的组合, 输出其中前 t 个组合结果.
输入格式:
在一行中输入 n,r,t(1<=t<=C(n,r)).
输出格式:
按特定顺序输出前 t 个组合结果, 每一个组合结果占一行, 含第一个整数在内的每一个整数前面都用一个空格, 最后一个整数后面没有空格. 特定顺序: 每一个组合结果中的值从大到小排列, 组合之间按逆字典序排列.
输入样例:
在这里给出一组输入. 例如:
5 3 10 6 4 8
输出样例:
在这里给出相应的输出. 例如:
- 5 4 3
- 5 4 2
- 5 4 1
- 5 3 2
- 5 3 1
- 5 2 1
- 4 3 2
- 4 3 1
- 4 2 1
- 3 2 1
- 6 5 4 3
- 6 5 4 2
- 6 5 4 1
- 6 5 3 2
- 6 5 3 1
- 6 5 2 1
- 6 4 3 2
- 6 4 3 1
历程
是期末模拟的题目, 写代码的时候, 感觉自己应该写的出来, 结果高估了自己┭┮﹏┭┮. 百度一下, 只有两个相关的, 点开发现第二篇是转载第一篇的. 下面题解的代码就是第一篇的代码.(20191109)
题解
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int X[31], used[31];
- int n, r, t, count;
- void output()
- {
- for (int i = 1; i <= r; ++i)// 输出 r 个
- {
- printf("%d", X[i]);
- }
- putchar('\n');
- }
- int pruning(int i)
- {
- if (used[i]) return 0;
- return 1;
- }
- void f(int k, int i)
- {
- if (t == count) return ;
- if (k - 1 == r)// 只组合 r 个
- {
- ++count;
- output();
- }
- else
- {
- for (;i>= 1; --i)
- {
- if (pruning(i))
- {
- X[k] = i;
- used[i] = 1;
- f(k + 1, i - 1);
- used[i] = 0;
- }
- }
- }
- }
- int main()
- {
- scanf("%d %d %d", &n, &r, &t);
- f(1, n);
- return 0;
- }
参考博客
来源: http://www.bubuko.com/infodetail-3279966.html