Wie kann ich einen rekursiven Münzwechsel in C++ programmieren?

Question

Ich versuche einen rekursiven Aufruf für Münzwechsel in C++ zu erstellen. Ich habe den Großteil des Algorithmus im Internet ausprobiert, aber es scheint nicht mit Vektor zu gelten oder die Summen der verwendeten Münze nicht aus. Kann mir jemand helfen zu verstehen, was die rekursive Funktion aufrufen muss? Daher gibt mir mein Algorithmus nicht die Mindestanzahl an Münzen und ich weiß nicht, wie ich die verwendete Münze speichern soll.

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

einige Punkte zu beachten: dh s als Argument an die coin Verfahren so lange

• Erstens gibt es keine Notwendigkeit, die Anzahl der Konfessionen zu senden als vector verwendet wird, weil vector hat eingebaute size() Methode, die diesen Job für uns erledigt. Zweitens
• , zu die Lösung zu speichern Sie eine andere vector von int genannt brauchen solution, aber das vector ist nur einen Datensatz zu halten und hat nichts mit der tatsächlichen rekursive Implementierung zu tun, und daher wird es als globale Variable definiert. Alternativ könnten Sie es auch als Argument mit Bezug auf die coin-Methode übergeben.
• Drittens sollten die vom Benutzer eingegebenen Werte sortiert werden, bevor sie an die Methode übergeben werden. Dazu habe ich die -Methode aus der algorithm-Bibliothek verwendet.

Was der rekursive Algorithmus im Grunde tut, ist:

• Bei jedem Schritt hält es das größte Stückelung d (letzte Element in der sortierten Stückelung vectordenom wie denom[denom.size() - 1]), die dann von den vector entfernt wird unter Verwendung von pop_back Methode von vector.
• Mit d finden wir count_d, die die Anzahl der Münzen der Bezeichnung d, in der Lösung verwendet wird. Wir erhalten dies, indem wir einfach eine Div-Operation wie N/d anwenden, die den Quotienten ergibt.
• Dann wird d zu der vectorsolution, count_d Anzahl hinzugefügt.
• Der rekursive Aufruf fügt count_d aus dieser Iteration und erinnert an coin mit den reduzierten Konfessionen vectordenom und Rest der Menge NN%d verwenden.

Siehe Quotient and Remainder für Klarheit, was div / und mod % Betreiber tun. Hier

ist der Code:

#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"); 
}