Блог

 //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] << " ";
  }


//
  

Я получаю сообщение об ошибке.

Этот алгоритм кажется мне разумным, кто-нибудь знает, почему он продолжает сбоить?

Правильно ли я использовал рекурсию здесь?

Если вы вызовете makechange дважды, во второй раз это не сработает, потому что глобальная переменная i будет неправильной.

Также, что должно произойти, если вы попытаетесь makechange и у вас недостаточно изменений для этого?

Аналогично, что произойдет, если у вас есть 3 четвертака и 3 десятицентовика, и вас просят внести 80 центов сдачи? Ваш алгоритм будет использовать все 3 квартала, а затем застрянет.

вы имели в виду

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

небольшая опечатка стала возможной благодаря использованию глобальной переменной i.

также

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

Я думаю, вы имели в виду

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

в зависимости от конечного значения amt это приведет к завершению работы с концом массива, что приведет к сбою.

вы можете решить это проще без рекурсии. обязательно ли использовать рекурсию для назначения? если нет, попробуйте это:

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

    for (int i=0; i < ndenoms amp;amp; amt > 0; i  )
    {
        while (onhand[i] > 0 amp;amp; 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
}