在做一些回溯練習時，卡在這里：
撰寫一個遞回演算法，生成給定 n 個數字的所有磁區。在僅成員順序不同的磁區中，我們只需要列出一個，從字典的角度來看是最后一個。按字典順序按升序寫出解決方案。1 <= n <= 100
n = 5 將是：
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5
我在網上搜索了解決方案并找到了這個，但它不太正確，我不知道如何完善它。首先，它不是按字典順序排列的，也不包括實際數字。
所以對于 5 它輸出：
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
這是我的代碼，我試圖糾正它，它更好，但仍然不完全是示例的方式..
#include <iostream>
#include <vector>
using namespace std;
void print(const vector<vector<int>>& output)
{
for(int i = 0; i < output.size(); i){
for(int j = output[i].size()-1; j >= 0; --j){
cout << output[i][j] << " ";
}
cout << endl;
}
}
void iteration(int n, int current_sum, int start, vector<vector<int>>& output, vector<int>& result)
{
if (n == current_sum) {
output.push_back(result);
}
for (int i = start; i < n; i ) {
int temp = current_sum i;
if (temp <= n) {
result.push_back(i);
iteration(n, temp, i, output, result);
result.pop_back();
}
else {
return ;
}
}
}
void decompose(int n)
{
vector<vector<int>> output;
vector<int> result;
iteration(n, 0, 1, output, result);
print(output);
cout << n << endl;
return ;
}
int main()
{
int n = 5;
decompose(n);
return 0;
}
所以，現在的輸出是：
1 1 1 1 1
2 1 1 1
3 1 1
2 2 1
4 1
3 2
5
所以，2 2 1 和 3 2 放錯了位置。“n”數字越大，混亂越大。
有人可以幫忙嗎？
uj5u.com熱心網友回復：
當您獲得更多練習編程時，您將學習如何保持簡單：
#include <iostream>
#include <vector>
void decompose(int n, std::vector<int> prefix = {}) {
if (n == 0) {
for (int a : prefix) { std::cout << a << ' '; }
std::cout << std::endl;
}
else {
int max = prefix.size() ? std::min(prefix.back(), n) : n;
prefix.push_back(1);
for (int i = 1; i <= max; i ) {
prefix.back() = i;
decompose(n - i, prefix);
}
}
}
int main() {
decompose(5);
}
uj5u.com熱心網友回復：
如果您只是想要答案...這里是我幾年前從 Python 翻譯成 C# 的一些代碼，剛剛翻譯成 C 以獲得這個答案。
#include <iostream>
#include <vector>
std::vector<int> join(int val, const std::vector<int>& vec) {
std::vector<int> joined;
joined.reserve(vec.size() 1);
joined.push_back(val);
std::copy(vec.begin(), vec.end(), std::back_inserter(joined));
return joined;
}
std::vector<int> tail(const std::vector<int>& v) {
std::vector<int> t(v.size() - 1);
std::copy(std::next(v.begin()), v.end(), t.begin());
return t;
}
std::vector<std::vector<int>> partitions(int n) {
if (n == 0) {
return { {} };
}
auto partitions_n_minus_1 = partitions(n - 1);
std::vector<std::vector<int>> partitions_n;
for (const auto& p: partitions_n_minus_1) {
partitions_n.push_back( join({ 1 }, p) );
if (!p.empty() && (p.size() < 2 || p[1] > p[0])) {
partitions_n.push_back(join({ p[0] 1 }, tail(p)));
}
}
return partitions_n;
}
int main()
{
auto partions = partitions( 6 );
for (const auto& p : partions) {
for (int i : p) {
std::cout << i << " ";
}
std::cout << "\n";
}
return 0;
}
來自這里的 Python 代碼，整數磁區生成器（Python 配方），作者在評論中進行了一些解釋。
在我的 C# 代碼中，我能夠保留 Python 版本中使用的生成器/yield 習慣用法，但恐怕我目前還不知道如何使用 C 協程，所以我已將其移至標準函式實作，這將更少高效，因為它需要大量復制。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/425216.html
上一篇：二叉搜索樹字符實作C