Подсчитать количество способов получения суммы с заданным изменением

#c #algorithm #floating-point #currency

#c #алгоритм #с плавающей запятой #Валюта

Вопрос:

Я пытался закодировать алгоритм для подсчета количества различных возможных способов получения определенной суммы с заданными номиналами. Предположим, что доллар США доступен в номиналах $100, $50, $20, $10, $5, $1, $0.25, $0.10, $0.05 и 0,01 доллара. Приведенная ниже функция отлично подходит для значений int и int

 /* Count number of ways of making different combination */
int Count_Num_Ways(double amt, int numDenom, double S[]){
   cout << amt << endl; //getchar();

  /* combination leads to the amount */
  if(amt == 0.00)
    return 1;

  /* No combination can lead to negative sum*/
  if(amt < 0.00)
    return 0;

  /* All denominations have been exhausted and we have not reached
     the required sum */
  if(numDenom < 0 amp;amp; amt >= 0.00)
    return 0;

  /* either we pick this denomination, this causes a reduction of 
     picked denomination from the sum for further subproblem, or 
     we choose to not pick this denomination and 
     try a different denomination */
   return Count_Num_Ways(amt, numDenom - 1, S)   
          Count_Num_Ways(amt - S[numDenom], numDenom, S);
}

но когда я меняю свою логику с int на float, она переходит в бесконечный цикл. Я подозреваю, что это из-за сравнений с плавающей запятой в коде. Я не могу определить точную причину поведения бесконечного цикла.
Любая помощь в этом отношении была бы полезна.

Ответ №1:

При работе с такими «маленькими» суммами в валюте и без учета процентов будет намного проще иметь дело только с центами и целыми суммами, не используя плавающую точку.

Поэтому просто измените свою формулу, чтобы использовать центы, а не доллары, и продолжайте использовать целые числа. Затем, когда вам нужно отобразить суммы, просто разделите их на 100, чтобы получить доллары, и по модулю 100, чтобы получить центы.

Ответ №2:

операции с плавающей запятой не могут быть точными из-за конечного представления. Таким образом, вы никогда не получите ровно 0.0. Вот почему вы всегда проверяете интервал следующим образом:

 if (fabs(amt - 0.0) < TOL)

с заданным допуском TOL . TOL выбирается соответствующим образом для приложения, в этом случае 1/2 цента уже должно быть в порядке.

РЕДАКТИРОВАТЬ: Конечно, для такого рода вещей ответ Daemin гораздо более подходит.