метод рекурсии продолжает падать (сменить алгоритм)

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 четверти и 3 цента, и вас попросят внести 80 центов в обмен?Ваш алгоритм будет использовать все 3 четверти, а затем застрянет.

Answer 2

Я внес изменения, как упомянуто shsmith, и вот модифицированная и полная программа на С ++.

#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' никогда не станет нулевым. В то же время вы никогда не проверяете значение «i», находится ли оно в пределах «ndenoms». Это также может привести к ошибкам за пределами границ, что может привести к некорректному завершению работы программы.

Answer 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) {<br> 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 }