如何在C++中編程遞歸硬幣更改？

Question

我想在C++中建立遞歸調用硬幣更改。我在互聯網上嘗試了大部分算法，但它似乎不適用於矢量或者它沒有使用硬幣的總和。任何人都可以幫助我理解遞歸函數必須調用什麼？所以我的算法沒有給我使用的最小數量的硬幣，我不知道如何保存使用的硬幣。

int coin(vector<int> denom, int s,int N) 
{ 
    if(N == 0) 
    { 
     return 1; 
    } 
    if(N < 0 || (N > 0 && s < 0)) 
    { 
     return 0; 
    } 

    return min(coin(denom,s - 1, N), 1 + coin(denom, s,N-denom[s-1])); 

} 


Input a value N: 
    Input: 40 
Input how many denominations: 
    Input: 3 
Denominations #1: 
    Input: 5 
Denominations #2: 
    Input: 20 
Denominations #3: 
    Input: 30 

Output: 
Minimum # of coins: 2 
Coin used: 20 + 20 
Don't want: 30 + 5 + 5 

Answer 1

幾點考慮：

• 首先，沒有必要派教派的人數即s 作爲參數傳遞給coin方法，只要一個vector正在被使用，因爲vector內置size()方法，爲我們做這項工作。
• 其次，保存液你需要的int命名solution另一個vector，但這vector只是造冊，並沒有任何實際遞歸實現，因此，它被定義爲一個全局變量。或者，您也可以通過參考coin方法將它作爲參數傳遞。
• 第三，在將用戶輸入的面額傳遞給coin方法之前，應對其進行排序。爲此，我使用algorithm庫中的sort方法。

什麼遞歸算法基本上做的是：

• 在每一個步驟，它認爲最大面額d（最後在排序面額元素vectordenom像denom[denom.size() - 1]），然後從vector使用去除pop_back方法vector。
• 使用d我們找到count_d，這是解決方案中使用的面額d的硬幣數量。我們通過簡單地應用像N/d這樣的div操作得到這個，其給出商數。
• 然後d被添加到vectorsolution,count_d次數。
• 的遞歸調用，從該迭代增加count_d並回顧coin具有減小的面額vectordenom和使用N%d量N的剩餘。

對什麼的div /和國防部%運營商做清晰見Quotient and Remainder。

下面是代碼：

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

vector<int> solution; 

int coin(vector<int> denom, int N) 
{ 
    if(N <= 0 || denom.size() <= 0) 
    { 
     return 0; 
    } 

    int d = denom[denom.size() - 1]; 
    denom.pop_back(); 

    int count_d = N/d; 

    solution.insert(solution.end(), count_d, d); 

    return count_d + coin(denom, N%d); 
} 

int main() 
{ 
    int N,s; 
    cout<<"Input a value N:\nInput: "; 
    cin>>N; 
    cout<<"Input how many denominations:\nInput: "; 
    cin>>s; 
    vector<int> denom; 

    for(int i = 0; i < s; i++) 
    { 
     int d; 
     cout<<"Denominations #"<<i+1<<":\nInput: "; 
     cin>>d; 
     denom.push_back(d); 
    } 

    std::sort(denom.begin(), denom.end()); 

    int minNoOfCoins = coin(denom, N); 

    cout<<"\nOutput:\nMinimum # of coins: "<<minNoOfCoins; 

    if(minNoOfCoins > 0) 
    { 
     cout<<"\nCoins used: "; 

     for(int i = 0; i < solution.size(); i++) 
     { 
      if(i > 0) 
      { 
       cout<<" + "; 
      } 
      cout<<solution[i]; 
     } 
    } 

    cout<<endl; 

    system("pause"); 
}