学习C，需要对“ Greedy”的一些帮助。 CS50解决方案 [英] Learning C, need some assistance with "Greedy" CS50 solution

问题描述

我是C语言的新手。我来自python背景。我想知道我的代码出了什么问题。

I am very new to C. I come from a python background. I would like to know where I went wrong with my code.

我正在处理CS50贪婪问题。我的代码有什么问题？它可以使用某些数字，但其他数字则无效。我试图从用户那里得到输入，询问要退还多少零钱，然后仅使用$ .25，$。10，$。05，$。01

I am doing the cs50 greedy problem. What is wrong with my code? It works with some numbers but others don't work. I am trying to get an input from the user asking how much change to give back, then calculate the minimum number of coins I can give back using only $.25, $.10, $.05, $.01

#include <cs50.h>
#include <stdio.h>


int main(void)
{
    float n;
    do
    {
        n = get_float("How much change is owed?\n");
    }
    while(n == EOF); 
    int minimumamountofcoins = 0;
    if (n/.25 >=1){
        do 
        {
            n -= .25;
            minimumamountofcoins++;
        }
        while (n/.25 >= 1);
    }
    if (n/.1 >=1){
        do
        {
            n -= .1;
            minimumamountofcoins++;
        }
        while (n/.1 >=1);
    }
    if(n/.05 >=1){
        do
        {
            n -= .05;
            minimumamountofcoins++;
        }
        while (n/.05 >=1);
    }
    if (n/.01 >=1){
        do
        {
            n -= .01;
            minimumamountofcoins++;
        }
        while (n/.01 >=1);
    }
    printf("The minimum amount of coins is %d\n", minimumamountofcoins);
}

新代码：（除了输入4.2之外，其他功能都很好）

New code: (works perfectly except when entering 4.2)

#include <cs50.h>
#include <stdio.h>


int main(void)
{
    float n;
    do
    {
        n = get_float("How much change is owed?\n");
    }
    while(n == EOF);

    int cents = (int)(n * 100);
    int minimumamountofcoins = 0;
    if (cents/25 >= 1){
        while (cents/25 >= 1)
        {
            cents -= 25;
            minimumamountofcoins++;
        }

    }
    if (cents/10 >= 1){
        while (cents/10 >= 1)
        {
            cents -= 10;
            minimumamountofcoins++;
        }
    }
    if(cents/5 >= 1){
        while (cents/5 >= 1)
        {
            cents -= 5;
            minimumamountofcoins++;
        }
    }
    if (cents/1 >= 1){
        while (cents/1 >= 1)
        {
            cents -= 1;
            minimumamountofcoins++;
        }
    }
    printf("The minimum amount of coins is %d\n", minimumamountofcoins);
}

推荐答案

因为您未包含测试情况下，我做了我自己的事。在某些情况下，您的算法无法返回正确答案：

Since you did not include test cases, I did my own. Here are some of the cases for which your algorithm does not return the correct answer:

.04，.11，.17，.19 ，.21，.26，.32等。

.04, .11, .17, .19, .21, .26, .32, etc.

这些情况在计算便士数时都会失败（最终-while循环），则它们返回的钱都比应少的多。这是因为浮点数错误。通过打印语句，我发现在计算最后一分钱的除法时，每次都会发生相同的事情：

These cases all fail when calculating the number of pennies (in the final do-while loop), and they all return one less coin then they should. This is because of error with floating-point numbers. With print statements, I discovered that when the division for the final penny was being calculated, the same thing occurred each time:

n /。 01 = 0.99999999

n/.01 = 0.99999999

这显然不是故意的，因为它应该等于1，最后的便士应加到总数中。因此，理论上可行的代码由于浮点数而被破坏。

This is obviously not intended, as this should be equal to 1, and the final penny should be added to the total. Thus, your code, which works in theory, is broken because of floating-point numbers.

为避免这种情况，您可以做很多事情，例如跟踪美元和美分分别作为整数，将条件更改为 n / .01> = .9999 而不是 n / .01> = 1 ，将您要进行计算的金额视为整数美分或任何其他数量的事物。

To avoid this, you could do any number of things, such as keeping track of dollars and cents separately as integers, change the condition to be n/.01 >= .9999 instead of n/.01 >= 1, treat the amount of money you are doing the calculations on as an integer number of cents, or any other number of things.

个人，我更喜欢最后一种选择，将金额视为整数分。这很容易做到，因为将美元转换为美分所需要做的就是乘以100。因此，最简单的方法是使用相同的算法，除了使用整数。

Personally, I prefer that last option, treating the amount of money as an integer number of cents. This is easy to do, as all you have to do to convert from dollars to cents is multiply by 100. Thus, the easiest thing to do is to use this same algorithm, except use integers.

因此，代码看起来像这样：

Thus, the code would look something like this:

int main(){
    float n;
    //code that parses in the amount of money, n now stores that amount
    int cents = (int)(n * 100);
    int minimumamountofcoins = 0;
    if (cents/25 >= 1){
        while (cents/25 >= 1)
        {
            cents -= 25;
            minimumamountofcoins++;
        }

    }
    if (cents/10 >= 1){
        while (cents/10 >= 1)
        {
            cents -= 10;
            minimumamountofcoins++;
        }
    }
    if(cents/5 >= 1){
        while (cents/5 >= 1)
        {
            cents -= 5;
            minimumamountofcoins++;
        }
    }
    if (cents/1 >= 1){
        while (cents/1 >= 1)
        {
            cents -= 1;
            minimumamountofcoins++;
        }
    }
    printf("The minimum amount of coins is %d\n", minimumamountofcoins);
}

这篇关于学习C，需要对“ Greedy”的一些帮助。 CS50解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！