Жадный алгоритм возвращает слишком большие величины для малых значений, но не для больших - PullRequest
Новая
       17

Жадный алгоритм возвращает слишком большие величины для малых значений, но не для больших

1 голос
/ 17 мая 2019

Я пишу жадный алгоритм (который уже вызвал у меня много головных болей), который выводит наименьшее количество монет, которое можно использовать для некоторой денежной стоимости, и я наконец получил код, которым был доволен, или я так думал.При вводе значения .41 мне возвращается 4 coins, что правильно - однако, ввод .01 возвращает 2 coins, и я понятия не имею, почему. 

// declare variable change_owed, num_coins, and input globally
float change_owed = 0;
float dollars;
int cents;
int num_coins;

int main(void)
{
    // makes sure the input is non-negative
    do
    {
        dollars = get_float("Change owed:\n");
        cents = round(dollars * 100);
    }
    while(cents <= 0);

    // begin checking 


        while(cents - 25 >= 0) // quarters
        {
            num_coins++; // number of coins used, to be printed later, is incremented
            cents = cents - 25; // coin is subtracted from total
        }
        while(cents - 10 >= 0) // dimes
        {
            num_coins++;
            cents = cents >= 10;
        }   
        while(cents - 5 >= 0) // nickels
        {
            num_coins++;
            cents = cents - 5;
        } 
        while(cents >= 0) // pennies
        {
            num_coins++;
            cents = cents - 1;
        } 

    printf("%i coins\n", num_coins);
}

Ответы [ 2 ]

2 голосов
/ 17 мая 2019

Основная проблема (от одной монеты): 

while(cents >= 0) // pennies

должно быть 

while (cents - 1 >= 0) // or even better: while (cents >= 1)

Также есть опечатка: 

cents = cents >= 10;

должно быть 

cents = cents - 10; // or even better: cents -= 10;
1 голос
/ 17 мая 2019

Насколько я вижу, вы не инициализировали num_coins 

int num_coins = 0;

Есть ли причина, по которой вы используете циклы while? целочисленная арифметика сделает то же самое проще. Поскольку центов является целым числом, его деление на другое целое возвращает только целую часть (эффективно округленную в меньшую сторону). 

num_coins = cents / 25; // returns the integer part, count of quarters
                        // This is an alternative to initialization
cents %= 25; // modulus operator returns the remainder
num_coins = num_coins + cents / 10; // count of dimes
cents %= 10;
num_coins = num_coins + cents / 5; // count of nickles
cents %= 5;
num_coins += cents; // cents must equal number of pennies required.

ОК, я не тестировал приведенный выше код, поэтому могут быть некоторые ошибки, но вы поняли.

...