Жадный алгоритм в C - PullRequest
Новая
       9

Жадный алгоритм в C

0 голосов
/ 10 апреля 2020

Итак, я начал изучать C в течение 2 дней в курсе CS50. На неделе № 2 был задан вопрос о кодировании для алгоритмов жадности, которые в основном возвращали заказчику их изменения при минимальном количестве монет. Вот мое решение, написанное в песочнице CS50. 

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

int main(void)
{
    //Assign value
    int q = 0; int d = 0; int n = 0; int p =0;
    int left;
    int count = 0;
    float change;

    // Promting user for change.
    do
    {
       change = get_float("Change:");
    }
    while(change < 0);

    // Convert cent to dollar.
    int cent = round(change * 100);
    printf("Dollar %i\n", cent);

    //Counting coin
    while(cent >=25)
    {
        q++;
        left = cent - 25;
    }
    while(left >=10)
    {
        d++;
        left = left -10;
    }
    while(left >=5)
    {
        n++;
        left = left -5;
    }
    while(left >=1)
    {
        p++;
        left=left-1;
    }
    count = q + d + n + p;  
    printf("Total coin: %i\n", count);
}

Я запускаю код на терминале CS50 в изолированной программной среде CS50 и получаю эту ошибку: 

cash.c:27:10: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'

Я понимаю, что мой l oop превышает ограничение хранения данных в инт. Но я не могу найти способ это исправить.

Ответы [ 2 ]

1 голос
/ 10 апреля 2020

У вас есть это: 

while(cent >=25) 
    q++;
    left = cent - 25;
}

Если cent изначально 25 или больше, закончится ли этот l oop когда-нибудь? cent никогда не меняется, поэтому нет. Другие циклы в порядке, поэтому все, что вам нужно сделать, это использовать тот же шаблон, который вы использовали для других циклов, и для этого.

0 голосов
/ 10 апреля 2020

Вам не нужно менять тип q, то есть int - для которого вообще появляется это сообщение об ошибке.

Проблема в другом месте:

q выходит за границы допустимых значений, которые должны храниться в int, потому что в l oop: 

while(cent >=25)
{ 
    q++;
    left = cent - 25;
}

значение для доказательства условия cent никогда не уменьшается и поэтому l oop никогда не заканчивается. Вы присваиваете cent - 25 только left, сама cent не изменяется.

Кстати, вам не нужна переменная left.

Скорее используйте: 

//Counting coin
while(cent >= 25)
{
    q++;
    cent = cent - 25;
}
while(cent >= 10)
{
    d++;
    cent = cent - 10;
}
while(cent >= 5)
{
    n++;
    cent = cent - 5;
}
while(cent >= 1)
{
    p++;
    cent = cent - 1;
}

Более того: 

printf("Dollar %i\n", cent);

неверно, поскольку вы пытаетесь распечатать деньги, чтобы изменить их в центах, а не в долларах: 

printf("Change in Cent: %i\n", cent);

Исправленный код: 

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

int main(void)
{
    //Assign value
    int q = 0; int d = 0; int n = 0; int p = 0;
    int count = 0;
    float change;

    // Promting user for change.
    do
    {
       change = get_float("Change in Dollar:");
    }
    while(change < 0);

    // Convert cent to dollar.
    int cent = round(change * 100);
    printf("Change in Cent: %i\n", cent);

    //Counting coin
    while(cent >= 25)
    {
        q++;
        cent = cent - 25;
    }
    while(cent >= 10)
    {
        d++;
        cent = cent - 10;
    }
    while(cent >= 5)
    {
        n++;
        cent = cent - 5;
    }
    while(cent >= 1)
    {
        p++;
        cent = cent - 1;
    }

    count = q + d + n + p;  
    printf("Total amount of coins: %i\n", count);
}
...