資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告