再帰メソッドがクラッシュする（アルゴリズム変更）

Question

//amt = amount of cents to get change for 
//onhand = array of available coins . Ex: {3, 0, 1, 0} = 3 quart, 0 dime, 1 nickel, 0 pennies 

//denoms = {25, 10, 5, 1} 

//ndenoms = 4 ; i.e the number of different denominations 

// thechange = array of change. Ex: if amt = 80, then one possible thechange = {3, 0, 1, 0} b/c 3*25 + 1*5 = 80 cents 



int i = 0; 

void makechange(int amt, int *onhand, int *denoms, int ndenoms, int *thechange) 
    {    

     if ((denoms[i] * onhand[i]) > amt) 
     { 
        onhand[i]--; // # of coins is too much, decrement and try again 
        makechange(amt, onhand, denoms, ndenoms, thechange); // try agan 
     } 

     thechange[i] = onhand[i]; //found #of coins 

     amt = amt - denoms[i]*onhand[i]; // get remaining amount from change 
     i++; 

     if (amt != 0) // we're not done with change so move on to next denomination 
     { 
      makechange(amt, onhand, denoms, ndenoms, thechange); 
     } 


     else if (amt == 0) // we're done with the change so all the other # coins = 0 
     { 
      for (int j = i; j < amt; j++) 
      { 
       thechange[j] = 0; 
      } 
     } 




    } 






Now, down in main when I actually call the function prototype and print out the result 

// 


makechange(amt, onhand, denoms, ndenoms, thechange); 

    for (int k = 0; k < ndenoms; k++) 
    { 
     cout << thechange[i] << " "; 
    } 


// 

私はエラーが発生します。

このアルゴリズムは私には分かりやすいようですが、誰でもなぜクラッシュするのか知っていますか？

再帰を正しく使用しましたか？

Answer 1

あなたは

for (int k = 0; k < ndenoms; k++) { cout << thechange[k] << " "; } 

グローバル変数iの使用によって可能になった小さなタイプミスを意味しました。

も

 for (int j = i; j < amt; j++) { thechange[j] = 0; } 

私はあなたがAMTの最終値に応じて、

for (int j = i; j < ndenoms; j++) 

を意味し、これはクラッシュで、その結果、あなたは配列の末尾をオフに実行する原因になると思います。

これを再帰なしで簡単に解決できます。あなたは割り当ての再帰を使用する必要がありますか？ない場合は、これを試してください：あなたは二回makechangeを呼び出す場合、グローバル変数iが間違っていることになるので、

int makechange(int amt, int *onhand, int *denoms, int ndenoms, int *thechange) 
{
 
    for (int i=0; i < ndenoms && amt > 0; i++) 
    { 
     while (onhand[i] > 0 && denoms[i] <= amt) 
     { 
      onhand[i]--; // use one coin 
      thechange[i]++; 
      amt -= denoms[i]; 
     } 
    } 
    return amt; // this is the amount you owe if you dont have enough on hand 
}

Answer 2

は、二回目は、それが動作しません。

また、makechangeを試してみると、それを作るために十分な変更がなされていないとどうなりますか？

同様に3四半期と3ダイムがあり、80セントを変更するよう求められたらどうなりますか？あなたのアルゴリズムは3四半期すべてを使用し、つづります。

Answer 3

私はshsmithが述べたように変更を加えました。変更された完全なC++プログラムです。

#include <iostream> 

using namespace std;

int i = 0;

void makechange(int amt, int *onhand, int *denoms, int ndenoms, int *thechange) 
{ 
    if ((denoms[i] * onhand[i]) > amt) 
    { 
      onhand[i]--; // # of coins is too much, decrement and try again 
      makechange(amt, onhand, denoms, ndenoms, thechange); // try agan 
    } 

    thechange[i] = onhand[i]; //found #of coins 
    amt = amt - denoms[i]*onhand[i]; // get remaining amount from change 
    i++; 
    if (amt != 0) // we're not done with change so move on to next denomination 
    { 
      makechange(amt, onhand, denoms, ndenoms, thechange); 
    } 
    else if (amt == 0) // we're done with the change so all the other # coins = 0 
    { 
      for (int j = i; j < ndenoms; j++) 
      { 
        thechange[j] = 0; 
      } 
    }} 

int main(){

//Now, down in main when I actually call the function prototype and print out the result 
    int amt = 80, onhand[] = {3, 0, 1, 0}, denoms[] = {25, 10, 5, 1}, ndenoms = 4, thechange[4]; 
    makechange(amt, onhand, denoms, ndenoms, thechange); 
    for (int k = 0; k < ndenoms; k++) 
    { 
      cout << thechange[k] << " "; 
    } 
    cout << "\n"; 
    return 0;} 

このコードは、私のマシン上で完全に実行されています。 Cygwinを使ってコンパイルしました。

注：このアルゴリズムは、金種の硬貨がより正確にまたは正確にオンである場合にのみ機能します。コインの数が不十分である場合、 'amt'は決してゼロにならないため、再帰的メソッドの終了はありません。それと同時に、あなたは 'ndenoms'の範囲内にあるかどうか '私'の価値をチェックすることは決してありません。これにより、境界プログラムのエラーが発生し、urプログラムが正しく終了しなくなる可能性があります。