C语言中的贪心算法

Question

于是在CS50的课程中开始学了2天的C。在第 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'

我知道我的循环超出了以 int 格式存储数据的限制。但是我找不到修复它的方法。

Answer 1

你有这个：

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

如果 cent 最初是 25 以上，这个循环会永远结束吗？ cent 永远不会改变，所以不会。其他循环都很好，所以你所要做的就是对这个循环使用与其他循环相同的模式。

Answer 2

您不需要更改 q 的类型，即 int - 根本不会出现此错误消息。

问题出在其他地方：

q 超出了 int 中能够保存的值的范围，因为在循环中：

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

证明条件的值 cent 永远不会减少，因此循环永远不会终止。你只把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);
}

C语言中的贪心算法

Greedy Algorithm in C

c

cs50