数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用C++查找k位数中n位为1的所有组合（1 <= n <= k），并按排序顺序输出。
假设我们有一个数字k。找出k位数中所有可能的组合，其中有n位为1（1 <= n <= k）。结果将首先打印所有只有一位为1的数字，然后是两位为1的数字，以此类推，直到所有位都为1的数字。如果两个数字的1的位数相同，则较小的数字排在前面。因此，如果k = 3，则数字将为[001, 010, 100, 011, 101, 110, 111]
在这里，我们将使用动态规划方法来查找k位数中所有可能的组合，其中n位为1（1 <= n <= k）。这个问题也可以分成两部分。我们将找到长度为k的所有组合，其中n个1可以通过在长度为k-1且有n个1的所有组合前面加0，以及在长度为k-1且有n-1个1的所有组合前面加1来实现。
示例
#include<iostream>
#include<vector>
#define K 16
using namespace std;
vector<string> table[K][K];
void getCombinations(int k) {
string str = "";
for (int bit = 0; bit <= k; bit++) {
table[bit][0].push_back(str);
str = str + "0";
}
for (int bit = 1; bit <= k; bit++) {
for (int n = 1; n <= bit; n++) {
for (string str : table[bit - 1][n])
table[bit][n].push_back("0" + str);
for (string str : table[bit - 1][n - 1])
table[bit][n].push_back("1" + str);
}
}
for (int n = 1; n <= k; n++) {
for (string str : table[k][n])
cout << str << " ";
cout << endl;
}
}
int main() {
int k = 4;
getCombinations(k);
}输出
0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111
更新于：2019年12月18日
355 次浏览
广告