所以，假設陣列 A : 1,2,3,1,1,3 。不同的整數應該在陣列 B 中：1,2,3。然后，函式應該列印： [1,1][1,2][1,3][2,1][2,2][2,3][3,1][3,2][3, 3]。
我試圖解決不同的整數問題，但沒有遞回
#include <iostream>
#include <algorithm>
using namespace std;
void uniqueNumber(int A[], int n, int B[], int &dimB ){
sort(A, A n);
for( int i = 0; i < n; i ){
if( A[i] == A[i 1] ){
continue;
}
else {
B[dimB ] = A[i];
}
}
}
但問題是我必須以遞回方式解決它，有什么想法嗎？
uj5u.com熱心網友回復：
我可以提供您的問題的解決方案，使用演算法深度優先搜索。
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
void showContentSet(std::set<int>& input)
{
for(auto iterator=input.begin(); iterator!=input.end(); iterator)
{
std::cout<<*iterator<<", ";
}
return;
}
void dfs(int current, int previous, std::vector<int>& first, std::set<int>& second, std::vector<int>& visited)
{
if(visited[current]==1)
{
return;
}
visited[current]=1;
for(int next=(current 1); next<first.size(); next)
{
if(next==previous)
{
continue;
}
if(first[next]==first[current])
{
continue;
}
else
{
second.insert(first[current]);
second.insert(first[next]);
}
dfs(next, current, first, second, visited);
}
if(current==0)
{
for(auto& item : second)
{
for(auto& itemSet : second)
{
std::cout<<"["<<item<<", "<<itemSet<<"]"<<", ";
}
}
}
return;
}
void solve()
{
const int maximumSize=20;
std::vector<int> visited(maximumSize, 0);
std::vector<int> inputVector={1, 2, 3, 1, 1, 3};
std::set<int> inputSet;
dfs(0, -1, inputVector, inputSet, visited);
return;
}
int main()
{
solve();
return 0;
}
結果如下：
[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3],
uj5u.com熱心網友回復：
遞回只是另一種回圈方式。它通常是一種干凈的方法，盡管它通常不如實際for或while回圈優化好，并且除了尾遞回演算法之外，它可以爆破堆疊記憶體，除非資料大小很小，或者演算法是對數的或更好的。這是一個線性演算法（遍歷陣列），所以我不喜歡真正解決方案的遞回，盡管它是一個很好的學習練習。
重要的是要考慮以下內容：資料的結構，什么是不變數（即，在遞回發生時您可以依靠什么來保持真實），以及何時應該停止（“基礎”案件）。
當您“通過”您的資料進行遞回時，您通常一次查看一個元素或一小塊資料，以逐步構建解決方案。
有時您必須在開始遞回之前直接處理一些特殊情況。這對于處理超出遞回所需的不變數的情況是必要的，例如當沒有足夠的資料來滿足資料的預期“形狀”時。
鑒于您的界面：
void uniqueNumber(int A[], int n, int B[], int &dimB );
我們已經知道一些事情。首先，它不是一個好的界面。:) 陣列不是函式的安全引數，并且非常容易出錯。其次，dimB 是一個“out”引數，除非有必要，否則不贊成（因為我們可以將大小作為函式回傳值回傳。）第三，我們不知道 B 的大小，但必須假設它在至少和 A 一樣大。（這是這個介面的另一個安全問題。）
但是假設函式簽名是固定的，這就是我們必須使用的。那么我們想要什么？
目標：找到每個唯一的數字，按排序順序寫入 B，然后更新 dimB 以告訴呼叫者有多少項寫入 B。
所以基本上我們想要這樣做：
- 對數字進行排序
- 使用索引迭代陣列
i- 如果當前值 (
A[i]) 與前一個值 (A[i-1]) 不同，則將當前值附加到 B，并增加 dimB - 不要閱讀
A[-1]
- 如果當前值 (
- 增量
i - 當索引 i == n 時，我們停止
上面的不變數是：
- 對于任何索引 i，在它之前都有一個有效值
- 索引
i> 0 且 <= n - 每次遞回呼叫，
i增加
主要步驟將是：
如果沒有作業要做（A 是空的），我們已經完成了。剛回來。
否則我們的不變數就滿足了：我們至少有一個元素。保證第一個元素不在 B 中，因此對 A 進行排序，然后立即將 A[0] 添加到 B，然后我們開始遞回。這也處理 A 的大小正好為 1 的情況。遞回將簡單地立即回傳。
通常，遞回演算法由兩個函式撰寫：第一個函式處理特殊情況并進行其他設定，然后呼叫執行遞回作業的第二個函式，知道所有特殊情況都已處理。
所以這里是考慮了上述之后的 uniqueNumbers 函式：
void uniqueNumber(int A[], int n, int B[], int &dimB ) {
if (n > 0) {
std::sort(A, A n);
B[dimB ] = A[0];
detail::uniqueNumberRec(1, A, n, B, dimB);
}
}
由于遞回輔助函式不是直接呼叫的，而是實作細節，我把它放在detail命名空間中，這是記錄用戶不應直接呼叫它的常見做法，它還有助于防止混亂全域命名空間。
那么遞回函式有什么作用呢？
它采用當前索引和初始函式采用的相同引數，并且是上述描述的非常直接的后果：
namespace detail {
void uniqueNumberRec(int curIdx, int A[], int n, int B[], int &dimB ) {
// Base case: stop when we reach the end
if (curIdx == n) {
return;
}
// if current element differs from previous, include it in answer
if (A[curIdx] != A[curIdx-1]) {
B[dimB ] = A[curIdx];
}
// recurse onto next element in sequence, so increment curIdx
uniqueNumberRec(curIdx 1, A, n, B, dimB);
}
} // namespace detail
It's important to notice that the initial index passed into the recursive function (from the initail function) is 1, not 0, because we already added the first element to the output, and so are already past that.
As long as we know that curIdx 1 repeatedly called will eventually reach n, we know the recursion makes progress and will terminate. We already have verified n is positive in the first function.
A few things worth noting:
- if n == 0 we do nothing
- if n == 1, we add the only element of A into B, then recurse, but the recursion immediately stops since curIdx == 1 and n == 1
- 如果 n > 1，我們添加（已排序）A 的第一個元素，然后遞回。所以 A[0] 已經在結果中，我們開始對 A[1] 進行遞回，知道 A[i-1]（即 A[0]）是一個有效的讀取元素。然后我們遞回，直到我們的索引在 n 處，這意味著我們完成了。
另外值得注意的是：在您的代碼中，您有一個錯誤：
if( A[i] == A[i 1] ){
如果 i 是 A 中的最后一項，則 A[i 1] 讀取越界。這是不可接受的。這就是為什么我從以前的閱讀，確保有后是以前的。
編譯器資源管理器示例：https : //godbolt.org/z/8z3cf5Tab
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/389009.html
上一篇：如何等待遞回回圈完成并顯示訊息？