Целочисленное переполнение в жадном подсчете монеты

Question

#include <stdio.h> 
#include <cs50.h> 
#include <math.h> 

int main (void) { 

    printf ("Enter amount: "); 
    float amount = GetFloat(); 
    int coins = 0; 

    while (amount != 0) { 

     if (fmod(amount, 0.25) == 0) { 
      amount = amount - 0.25; 
      coins += 1; 
     } 

     else if (fmod(amount, 0.10) == 0) { 
      amount = amount - 0.10; 
      coins += 1; 
     } 

     else if (fmod(amount, 0.05) == 0) { 
      amount = amount - 0.05; 
      coins += 1; 
     } 

     else { 
      amount = amount - 0.01; 
      coins += 1; 
     } 
    } 

    printf ("Coins : %d\n", coins); 
} 

Я пытаюсь реализовать маленький жадный алгоритм, в который пользователь вводит сумму денег (пример: 9.25), и мы выводим наименьшее количество монет, которые нам нужны обменять его на изменение (25 центов, 10 центов, 5 центов и 1 цент).

Этот алгоритм работает с целыми количествами, равными 10 или 20, и с суммами, которые требуют, чтобы программа использовала 25 центов.

Если я попробую сумму, равную 9,10 или 9,01, я получаю ошибку времени выполнения, целое переполнение целых чисел. Я понимаю, что это значит, но я не понимаю, как стоимость монет может быть настолько высокой.

Answer 1

Ваш алгоритм не правильно:

Например, с 30 центов вы можете обменять на: 25 + 5 (2 монеты) с алгоритмом это будет 10 + 10 + 10 (3 монеты). Так жадный означает, что он превышает 25 центов, а затем сначала обменяется на 25 центов.

while (amount != 0) { 

    if (amount >= 0.25) { 
     amount = amount - 0.25; 
     coins += 1; 
    } 

    else if (amount >= 0.10) { 
     amount = amount - 0.10; 
     coins += 1; 
    } 

    else if (amount >= 0.05) { 
     amount = amount - 0.05; 
     coins += 1; 
    } 

    else { 
     amount = amount - 0.01; 
     coins += 1; 
    } 
} 

Если вы хотите сделать это.

Лучший способ:

int coinTypes[] = {0.25, 0.1, 0.05, 0.01}; 

for (int i = 0; i < 4; i++) { 
    coins += floor(amount/coinTypes[i]; 
    amount -= coins * coinsTypes[i]; 
} 

Answer 2

Основная проблема с алгоритмом является недопустимым использование fmod функции. Согласно определению результатом является fmod(num, denom)

fmod = num - floor(num/denom) * denom 

, где floor(num/denom) является целым числом. Таким образом, fmod(9.10, 0.25) == 0.1, fmod(9.10, 0.10) == 0.1.

Кроме того, манипуляция с числом с плавающей запятой редко дает точные результаты. так amount никогда не 0.

Answer 3

Поскольку Danial Tran сказал, что лучше использовать int, когда выполняете логические операции. Пожалуйста, прочитайте Why not use Double or Float to represent currency? Также вы можете избежать цикла while.

#include <stdio.h> 
#include <cs50.h> 
#include <math.h> 

int main (void) { 

    printf ("Enter amount: "); 
    //float amount = GetFloat(); //Please refer to chqrlie's comments below. 
    double amount = 0.0; 
    scanf("%lf",&amount); //I don't know GetFloat() equivalent for double. So using scanf(). 

    long long int amountInt = (long long int) (amount * 100.0); 

    int coins = 0; 

    if (25 <= amountInt) { 
     coins += (amountInt/25); 
     amountInt = amountInt % 25; 
    } 

    if (10 <= amountInt) { 
     coins += (amountInt/10); 
     amountInt = amountInt % 10; 
    } 

    if (5 <= amountInt) { 
     coins += (amountInt/5); 
     amountInt = amountInt % 5; 
    } 

    if (1 <= amountInt) { 
     coins += amountInt; 
    } 

    printf ("Coins : %d\n", coins); 
} 

Answer 4

Кажется, что никто не ответил на конкретный вопрос

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

поэтому для полноты картины, частично в качестве упражнения:

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

if (fmod(amount, 0.25) == 0) { 
    amount = amount - 0.25; 
    coins += 1; 
} 

В момент прерывания amount было около минус 1,2 миллиона монет почти 5 миллионов человек. Это ясно показывает одну вещь, которую вы не смогли проверить: отрицательность. Это может случиться легко с поплавками, что вы пропустили точный ноль, как другие правильно рассудили, не нужно повторять это.Но если это произойдет, ваша программа должна волноваться в момент, когда amount получает отрицательный результат. В противном случае, при правильных условиях, он может также продолжать вычитать свой путь к отрицательной бесконечности, и да, целочисленное переполнение произойдет в coins.

Answer 5

Это происходит потому, что компьютер представляет десятичные в бинарной (степени 2)

Для 0,25, компьютер может представлять его должным образом в двоичной системе. Это потому, что мы можем получить 0,25 точно с использованием мощности 2.

Однако для 0,10 (или других конфессий, упомянутых), они не могут быть выражены точно по степеням 2.

Предположим, вы пытаетесь получить 0,1, используя мощность 2-х, вы не сможете получить его точно. Вы можете просто приблизиться к нему.

0,1 = 0,0625 (2^4) + 0,03125 (2^5) + 0,00390625 (2^-8) + ...

Вы приблизитесь к 0.1, но вы никогда не достигнете 0,1 точно.

Float, double каждый имеет фиксированное количество бит для представления десятичного числа. Так он будет держать только те несколько битов, сумма которых будет немного меньше, чем 0,1

Если вы хотите следовать такой же подход, вы можете иметь два возможных решения: -

1. Использование (сумма > 0) вместо (суммы! = 0) или
2. Используйте валюты, которые могут быть легко выражены в степеней 2 например 0,25, 0,125, 0,375, 0,06125.

Answer 6

Вы не можете вычислить это с float типа. Суммы, которые не являются точными кратными 0,25, не могут быть представлены точно в float или double.

Вы можете решить эту проблему путем вычисления точного количества центов и отправить его при помощи целочисленной арифметики:

#include <stdio.h> 
#include <math.h> 

void print_coins(int coins, const char *singular, const char *plural) { 
    if (coins > 0) 
     printf(" %d %s", coins, coins > 1 ? plural : singular); 
} 

int main(void) { 
    for (;;) { 
     double amount; 
     int amountInt, coins, quarters, dimes, nickels, pennies; 

     printf("Enter amount: "); 
     if (scanf("%lf", &amount) != 1 || amount <= 0) 
      break; 

     amountInt = (int)(amount * 100.0 + 0.5); 

     quarters = amountInt/25; 
     amountInt %= 25; 
     dimes = amountInt/10; 
     amountInt %= 10; 
     nickels = amountInt/5; 
     amountInt %= 5; 
     pennies = amountInt; 
     amountInt = 0; 

     coins = quarters + dimes + nickels + pennies; 

     printf("coins returned: %d:", coins); 
     print_coins(quarters, "quarter", "quarters"); 
     print_coins(dimes, "dime", "dimes"); 
     print_coins(nickels, "nickel", "nickels"); 
     print_coins(pennies, "penny", "pennies"); 
     printf("\n"); 
    } 
    return 0; 
} 

Примечание:

• Использования float без + 0.5, изменение неверно по немного как 100.10: один копейка короткий.
• Использование float, неверное изменение для 1000000.10: 3 дополнительных гроши.
• Чтобы обрабатывать суммы свыше 20 миллионов долларов, вам нужен более крупный интегральный тип, такой как long long int. При этом вы можете обрабатывать суммы, превышающие государственный долг США.