練習如下：
生成每個可能的序列，其元素來自集合 {0,1,2}，其中 0 出現 m 次，1 出現 p 次，2 出現 q 次。輸入檔案包含三個用空格分隔的自然數，最大值為 100。解必須按字典順序逐行寫入輸出檔案。每行應包含由空格分隔的系列元素。
If input is:
1 0 2
Output should be:
0 2 2
2 0 2
2 2 0
還說，我必須使用遞回，輸入和輸出應該是.txt檔案。
所以，我發現了一個流行的遞回遞回，它發生在多個站點上（像這樣），但由于一些奇怪的原因，它對我來說不能正常作業..
我嘗試做這個練習的方法（可能有更聰明的方法）是從輸入生成一個向量，并使用它的置換函式。但我的輸出是這樣的：
0 2 2
0 2 2
2 0 2
2 2 0
2 2 0
2 0 2
可以看到，每一個結果都會出現兩次，這顯然是不好的。。
代碼如下：
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
void input(int& m, int& p, int& q)
{
ifstream fin("input.txt");
fin >> m >> p >> q;
fin.close();
}
void fillVec(vector <int>& elements, int m, int p, int q)
{
fill_n(elements.begin() m, p, 1); // filling the vectors with correct amount of numbers. The 0's all already there, so I only put the 1's, and the 2's in.
fill_n(elements.begin() m p, q, 2);
}
void print(const vector<int>& nums, ofstream& fout)
{
for (int a : nums) { fout << a << ' '; }
fout << endl;
}
void permute(vector<int>& nums, int n, ofstream& fout)
{
if (n == nums.size())
{
print(nums, fout);
}
else
{
for (int i = n; i < nums.size(); i )
{
swap(nums[n], nums[i]);
permute(nums, n 1, fout);
swap(nums[n], nums[i]);
}
}
}
int main()
{
int m, p, q;
input(m, p, q);
vector <int> elements(m p q);
fillVec(elements, m, p, q);
ofstream fout("output.txt");
permute(elements, 0, fout);
fout.close();
return 0;
}
我嘗試除錯，也多次查看以檢查我是否正確復制了演算法，但無法找出問題所在。這可能很簡單，我不確定..
uj5u.com熱心網友回復：
這就是我想出的。每個遞回步驟都將嘗試將“0”、“1”或“2”附加到正在構建的字串中，直到沒有可用的數字可供添加。
它最終在每個輸出行上列印一個尾隨空格。如果這是相關的，我會把它作為小錯誤留給你修復。
#include <iostream>
#include <string>
using namespace std;
void GeneratePermutations(int zeros, int ones, int twos, const string& leading)
{
if ((zeros <= 0) && (ones <= 0) && (twos <= 0))
{
std::cout << leading << endl;
return;
}
if (zeros > 0)
{
GeneratePermutations(zeros - 1, ones, twos, leading " 0");
}
if (ones > 0)
{
GeneratePermutations(zeros, ones-1, twos, leading " 1");
}
if (twos > 0)
{
GeneratePermutations(zeros, ones, twos-1, leading " 2");
}
}
int main()
{
int zeros, ones, twos;
cin >> zeros;
cin >> ones;
cin >> twos;
GeneratePermutations(zeros, ones, twos, "");
return 0;
}
幾個示例運行：
輸入 ：1 0 2
輸出：
0 2 2
2 0 2
2 2 0
另一個輸入：3 1 1
輸出：
0 0 0 1 2
0 0 0 2 1
0 0 1 0 2
0 0 1 2 0
0 0 2 0 1
0 0 2 1 0
0 1 0 0 2
0 1 0 2 0
0 1 2 0 0
0 2 0 0 1
0 2 0 1 0
0 2 1 0 0
1 0 0 0 2
1 0 0 2 0
1 0 2 0 0
1 2 0 0 0
2 0 0 0 1
2 0 0 1 0
2 0 1 0 0
2 1 0 0 0
uj5u.com熱心網友回復：
正如您自己所見和所說，您只需生成陣列的所有可能排列0 2 2。長度為 3 的陣列有 6 個排列，你正確地得到了它們，但是因為有兩個相等的數字，所以其中一些排列是相等的。
但是，顯然您需要做的是只生成不同的排列。基本上，這意味著您需要一個新演算法。
一個簡單的解決方案可能是找到一種去除重復排列的方法。可能有很多方法，首先簡單地存盤所有排列并檢查您是否已經生成了給定的排列，或者使用每個數字存盤原始陣列索引并要求相同數字的索引按升序排列，等等。或者你可以用不同的方式組織你的遞回（這就是我會做的）。顯然，每種方法的復雜性會有所不同。
uj5u.com熱心網友回復：
使用std::next_permutation（處理重復），非遞回方式將是：
void permute(std::vector<int>& nums, std::ostream& out)
{
assert(std::is_sorted(nums.begin(), nums.end()));
do {
print(nums, out);
} while (std::next_permutation(nums.begin(), nums.end()));
}
演示
您仍然可以以遞回方式轉換上面的代碼：
void permute(std::vector<int>& nums, std::ostream& out)
{
print(nums, out);
if (std::next_permutation(nums.begin(), nums.end())) { permute(nums, out); }
}
演示
uj5u.com熱心網友回復：
您的代碼是完美的并且可以按預期作業。唯一的問題是您的應用程式有時會交換相同的數字，例如：
// nums = {0, 2, 2}
swap(nums[n], nums[i]); // n == 1, i == 2
// nums = {0, 2, 2}
在這里您可以注意到應用程式將交換 2 和 2，這不會有任何區別。
因此，您可以嘗試這樣的事情：
#include <iostream>
#include <vector>
#include <fstream>
// This std::vector will store all the elements that have been stored in output.txt
std::vector<std::string> output;
void input(int& m, int& p, int& q)
{
std::ifstream fin("input.txt");
fin >> m >> p >> q;
fin.close();
}
void fillVec(std::vector <int>& elements, int m, int p, int q)
{
fill_n(elements.begin() m, p, 1); // filling the std::vectors with correct amount of numbers. The 0's all already there, so I only put the 1's, and the 2's in.
fill_n(elements.begin() m p, q, 2);
}
void print(const std::vector<int>& nums, std::ofstream& fout)
{
for (int a : nums) { fout << a << ' '; }
fout << std::endl;
}
void permute(std::vector<int>& nums, int n, std::ofstream& fout)
{
if (n == nums.size())
{
std::string num;
// Convert nums (int array) to num (std::string)
for (int i = 0; i < nums.size(); i )
{
num.push_back(nums[i]);
}
// If same element found, return
for (int i = 0; i < output.size(); i )
{
if (num == output[i]) return;
}
print(nums, fout);
// Insert element to output (std::vector)
output.push_back(num);
}
else
{
for (int i = n; i < nums.size(); i )
{
std::swap(nums[n], nums[i]);
permute(nums, n 1, fout);
std::swap(nums[n], nums[i]);
}
}
}
int main()
{
int m, p, q;
input(m, p, q);
std::vector <int> elements(m p q);
fillVec(elements, m, p, q);
std::ofstream fout("output.txt");
permute(elements, 0, fout);
fout.close();
return 0;
}
這段代碼和你的一樣，除了我添加了一些檢查來確保沒有重復的元素。現在：
輸入.txt
1 0 2
output.txt（應用程式執行后）
0 2 2
2 0 2
2 2 0
...這是可取的。
此外，請考慮洗掉以下陳述句：
using namespace std;
...因為這被認為是不好的做法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424314.html