c++ - 递归方法不断崩溃(更改算法)

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

如果你两次调用makechange，第二次就不会起作用，因为全局变量i会出错。

另外，如果您尝试makechange 并且手头没有足够的零钱来完成，应该怎么办？

同样，如果您有 3 个 25 美分和 3 个角钱，并且被要求找零 80 美分，会发生什么情况？您的算法将使用所有 3 个季度，然后卡住。