Greedy Algorithm in “C”

问题:

I'm just start learning C language. I wrote this C code to implement Greedy algorithm I don't know what mistake I've made with this code, that code seems fine but its not working as I expected. Can anybody help me to fix this code?

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);
}

回答1:

Notes about the problems in the code:

• You are using in the first loop cents when there would be amount_left, in the case of the first loop if it require more that one iteration, the result would be incorrect.
• As recommended is better to change amount_left - 10 >= 0 by amount_left >= 10.
• The final printf statement most probably (by the text) is for printing the count of coin gained by the amount provided.

Code:

#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);
}

Using the formula: initial_amount = coin value * coin used + amount_left

This could be write in C as:

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

More optimized solution:

#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);
}

Notes:

• There is no need to while loop operation 17 / 5 = 3 in integers arithmetic in C and 17 % 5 = 2.
• Using this you use for a coin of value N, amount / N coins count (could be 0, eg: amount = 9 and N = 10, 9/10 = 0 in integer division) and the amount left is amount % N.
• The last case (for coin of 1) always left amount = 0.

回答2:

I agree with NetVipeC's answer.

I would add a note that is probably out of your assignment's scope, but might help you create better code in the future:

Your code suffers from code duplication. To eliminate that, I would create a function and call that function several times with different arguments. This process is called code reuse. code reuse is neccesary for writing more complicated programs. Code:

// 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);
}

I know this code might look wierd now. I've used a few key features of the C language that you will probably learn soon: user-defined function, array and for loop.

Hope this helps. Best of luck with your studies!

---

Edit:

If you don't wanna use a user-defined function, you can avoid code duplication without it. Basically you just pour the function's content inside the main function (and change names of variables):

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);
}