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

Question

Я только начинаю учиться C language. Я написал этот C-код для реализации алгоритма Greedy Я не знаю, какую ошибку я совершил с этим кодом, этот код кажется прекрасным, но он не работает, как я ожидал. Может кто-нибудь помочь мне исправить этот код?

int main(void) { 
    float amount = 0; 
    int cents = 0; 
    int count = 0; 
    int amount_left = 0; 

    amount = .30; 

    cents = (int)round(amount * 100); 

    printf("%d", cents); 

    amount_left = cents; 

    while (cents - 25 >= 0) { 
     count = count + 1; 
     amount_left = cents - 25; 
    } 
    while (amount_left - 10 >= 0) { 
     count = count + 1; 
     amount_left = amount_left - 10; 
    } 
    while (amount_left - 5 >= 0) { 
     count = count + 1; 
     amount_left = amount_left - 5; 
    } 
    while (amount_left - 1 >= 0) { 
     count = count + 1; 
     amount_left = amount_left - 1; 
    } 
    printf("You get %d coins\n", count); 
} 

Answer 1

Заметки о проблемах в коде:

• Вы используете в первом цикле cents когда будет amount_left, в случае первого цикла, если он требует более, что одной итерации, результат будет неправильным.
• Как рекомендуется, рекомендуется изменить amount_left - 10 >= 0 на amount_left >= 10.
• Заключительное заявление printf, скорее всего, (по тексту) предназначено для печати количества монет, полученных на предоставленную сумму.

Код:

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

int main(void) { 
    float amount = 0; 
    int cents = 0; 
    int count = 0; 
    int amount_left = 0; 

    amount = .30; 

    cents = (int)round(amount * 100); 

    printf("%d\n", cents); 

    amount_left = cents; 

    while (amount_left >= 25) { 
     count++; 
     amount_left -= 25; 
    } 
    while (amount_left >= 10) { 
     count++; 
     amount_left -= 10; 
    } 
    while (amount_left >= 5) { 
     count++; 
     amount_left -= 5; 
    } 
    while (amount_left >= 1) { 
     count = count + 1; 
     amount_left -= 1; 
    } 
    printf("You get %d coins\n", count); 
} 

Используя формулу: initial_amount = coin value * coin used + amount_left

Это может быть писать в C, как:

• initial_amount/coin value = coin used
• initial_amount% coin value = amount_left

Более оптимальное решение:

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

int main(void) { 
    float amount = 0; 
    int cents = 0; 
    int count = 0; 
    int amount_left = 0; 

    amount = .30; 

    cents = (int)round(amount * 100); 

    printf("%d\n", cents); 

    amount_left = cents;   // beginning with 30 cents 

    count += amount_left/25; // 30/25 = 1,  one 25 cent coin 
    amount_left %= 25;   // 30 % 25 = 5,  left with 5 cents 

    count += amount_left/10; // 5/10 = 0  no coin used 
    amount_left %= 10;   // 5 % 10 = 5  left the same 5 cents 

    count += amount_left/5;  // 5/5 = 1   one 5 cent coin 
    amount_left %= 5;    // 5 % 5 = 0   left with 0 cents 

    count += amount_left;  // not needed 1 cent coins. 

    printf("You get %d coins\n", count); 
} 

Примечания:

• Там нет необходимости while loop операции 17/5 = 3 в целых числах арифметики в C и 17 % 5 = 2.
• С помощью этого вы используете для монет стоимости N, рассчитывать amount/N монеты (может быть 0, например: amount = 9 и N = 10, 9/10 = 0 в целочисленном делении) и количество остались в amount % N.
• Последний случай (для монеты 1) всегда оставил amount = 0.

Answer 2

Я согласен с ответом NetVipeC.

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

Ваш код страдает от code duplication. Чтобы устранить это, я бы создал функцию и вызывал эту функцию несколько раз с разными аргументами. Этот процесс называется code reuse. повторное использование кода необходимо для написания более сложных программ.Код:

// a user-defined function that counts the number of coins with a specific value used 
int count_number_of_coins(int amount_left, int coin_value) { 
    int count = 0; 
    while(amount_left >= coin_value) { 
     count++; 
     amount_left -= coin_value; 
    } 
    return count; 
} 

int main(void) { 
    float amount = 0; 
    int cents = 0; 
    int count = 0; 
    int amount_left = 0; 
    int coin_values[] = {25, 10, 5, 1}; // an array of ints that hold the values of the coins in cents. 
    int i; 

    amount = .30; 

    cents = (int)round(amount * 100); 

    printf("%d", cents); 

    amount_left = cents; 

    for(i=0; i<4; i++) { 
     int current_count = count_number_of_coins(amount_left, coin_values[i]); 
     amount_left -= current_count*coin_values[i]; 
     count += current_count; 
    } 

    printf("You get %d coins\n", count); 
} 

Я знаю, что теперь этот код может выглядеть странным. Я использовал несколько ключевых функций C language, которые вы, вероятно, скоро узнаете: user-defined function, array и for loop.

Надеюсь, это поможет. Удачи вам в учебе!

---

Edit:

Если вы не хотите использовать определенную пользователем функцию, вы можете избежать дублирования кода без него. В основном вы просто заливаете содержимое функции внутри основной функции (и изменяете имена переменных):

int main(void) { 
    float amount = 0; 
    int cents = 0; 
    int count = 0; 
    int amount_left = 0; 
    int coin_values[] = {25, 10, 5, 1}; // an array of ints that hold the values of the coins in cents. 
    int i; 

    amount = .30; 

    cents = (int)round(amount * 100); 

    printf("%d", cents); 

    amount_left = cents; 

    for(i=0; i<4; i++) { 
     while(amount_left >= coin_values[i]) { 
      count++; 
      amount_left -= coin_values[i]; 
     } 
    } 

    printf("You get %d coins\n", count); 
}