c - "C"中的贪心算法

Question

我刚开始学习C 语言。我写了这段 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 更改为 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/硬币值(value) = 使用的硬币
• initial_amount % 硬币值(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);
}

注意事项:

• 在 C 和 17 % 5 = 中的整数运算中不需要 while 循环 操作 17/5 = 3 2.
• 使用这个你可以使用值(value) N 的硬币，amount/N 硬币计数(可以是 0，例如:amount = 9和 N = 10，9/10 = 0 在整数除法中)，剩下的数量是 amount % N。
• 最后一个案例(1 枚硬币)总是留下 amount = 0。