再帰的コインチェンジC++

Question

最小限の関数で再帰呼び出しを行うたびに、プログラムがクラッシュするようです。なぜ誰がクラッシュするのか教えてもらえますか？私は最小限の関数を呼び出した後、即座にフリーズします。私はベクトルを使っているからですか？

#include <iostream> 
#include <vector> 
#include <math.h> 
#include <algorithm> 

using namespace std; 

int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N 
{ 
    if(N == 0) 
    { 
     return 1; 
    } 
    else if(N < 0 || (N > 0 && s <=0)) 
    { 
     return 0; 
    } 
    else 
    { 
     return min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1])); 
    } 
} 
int main() 
{ 
    int N; 
    unsigned int sizeofcoin; 
    cout << "Enter the value N to produce: " << endl; 
    cin >> N; 
    cout << "Enter the number of different denominations: " << endl; 
    cin >> sizeofcoin; 

    vector<int> denom(sizeofcoin); 
    for(unsigned int i= 0; i < sizeofcoin; i++) 
    { 
     cout << "Enter denomination #" << (i+1) << endl;   //save all the denominations in an array 
     cin >> denom[i]; 
    } 

    sort(denom.begin() , denom.end(),greater<int>()); //sort the array from largest to smallest 
    if(denom.back() != 1)         //check the end of the array (since the back is smallest now) if it has 1 
    { 
     denom.push_back(1);        //Will include 1 if the user does not input a 1 (doesn't have to be used) 
    } 
    minimum(denom,sizeofcoin,N); 
    return 0; 
} 

Answer 1

あなたはそうNが以下0に等しくなることはありません、および再帰を終了することはありません再帰呼び出しminimum(denom,s - 1, N)を持っています。

これは、デバッガの使い方を学び、コードを1行ずつ進めて再帰呼び出しを行った場合には、非常に分かりやすいでしょう。

Answer 2

私はexplain your minimum() function to your rubber duckに挑戦しました。あなたのラバーダックにはあなたに質問があります。ここで私たちの会話が行った方法は次のとおりです。

int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N 
{ 
    if(N <= 0) 
    { 
     return 0; 
    } 

私は：その3番目のパラメータ、Nは、0、または負の場合、このminimum()再帰関数はすぐに戻ります。

あなたのラバーダック：Ok。

return (minimum(denom,s - 1, N)... 

は（ここでは、私はあなたのゴム製のアヒルに、ここにあなたの最初の再帰呼び出しを説明しようとした）：

私は：だから、これはその第2回を除いて、同じパラメータを使用して、再帰呼び出しを行いますパラメータは減分されます。 3番目のパラメータはNです。

あなたのラバーダック：だから、三番目のパラメータの値は、N場合、変更されず、Nが0または負で、かつminimum()の最初の呼び出しが0より大きい値を通過したときに、再帰関数は再帰なしで返しますNの場合は、正確にこの再帰が停止すると予想されますか？

私は自分自身でこの質問に答えることができませんでした、多分あなたは自分自身であなたのゴム製のアヒルにこれを説明することができます。再帰がいつ止まるのですか？

Answer 3

私が指摘したいもう一つは、あなたが2つの値の合計を返すようにしようとしているということです：あなたは何をすべきか代わりに

(minimum(denom,s - 1, N) + minimum(denom, s,N-denom[s-1]) 

は次のとおりです。

min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1])) 

考えはということです最初のコールではコインを使用していませんが、2回目のコールでは1つを使用しているので、同じコールに1を追加します。

同じもののための動的プログラミングソリューションを探します。 https://people.cs.clemson.edu/~bcdean/dp_practice/