贪心算法在"C“中的实现

Question

我刚刚开始学习C language。我写了这段C代码来实现贪婪算法，我不知道我在这段代码中犯了什么错误，这段代码看起来很好，但它并没有像我预期的那样工作。有人能帮我修复这段代码吗？

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 by final 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 used
• initial_amount = amount_left

% coin value = coin value

更优化的解决方案：

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

备注：

在17 % 5 = 2.

• Using和amount % N.

• The中，无需在整数算术中进行while loop运算17 / 5 = 3您可以将其用于值为C的硬币，并且硬币计数(可以是0，例如：N amount / N N = 10，<while loop>d43在整数除法中)，剩余的金额是最后一种情况(对于1的硬币)始终保持不变

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。

希望这能有所帮助。祝你学习顺利！

编辑：

如果你不想使用用户定义的函数，你可以避免没有它的代码重复。基本上，您只需将函数的内容倾倒在main函数中(并更改变量的名称)：

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