C - My greedy algorithm is not working CS50x

Question

I am doing cs50x and have run into a spot of trouble with my work. I am supposed to create an algorithm that will output the least amout of coins required to give back change. E.g 0.41 dollars will be 4 coins, a quarter (0.25), two dimes, (0.10) and a cent (0.01).For some reason this algorithm is not working (it is out putting the incorrect number of coins) and I cannot figure out why:

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

int Coins;
float Owed;

int main(void)
{
    printf("How much is owed?\n");
    Owed = GetFloat();
    while (Owed < 0)
    {
        printf("A positive number please");
        Owed = GetFloat();
    }
    if (Owed >= 0.25)
    {
        while (Owed >=0.25)
        {
            Owed = Owed - 0.25;
            Coins++;
        }
    }

     if (Owed >= 0.1)
    {
        while (Owed >=0.1)
        {
            Owed = Owed - 0.1;
            Coins++;
        }

    }

       if (Owed >= 0.05)
    {
        while (Owed >=0.05)
        {
            Owed = Owed - 0.05;
            Coins++;
        }

    }

       if (Owed >= 0.01)
    {
        while (Owed >= 0.01)
        {
            Owed = Owed - 0.01;
            Coins++;
        }

    }
    printf("%d",Coins);
}

When i ran the code and used 0.41 as the amount owed, i got 3 coins when the answer is supposed to be 4:

GreedyNotWorkTerminalPage

Learn how to use a debugger, and how to step through the code line by line while monitoring the variables and their values. — Some programmer dude, Oct 07 '16 at 09:01
Instead of looping on each coin value, why not use modulo arithmetic? — Chimera, Oct 07 '16 at 23:39

score 2 · Answer 1 · edited May 23 '17 at 11:52

2

When you use float, you need notice that it's possible to lose accuracy in this kind of operations. Look at this: Floating point inaccuracy examples

I recommend you work with cents, using a int instead.

Coliru example

edited May 23 '17 at 11:52

Community

1
1

answered Oct 07 '16 at 09:20

David Isla

619
7
19

Matt Timmermans · Accepted Answer · 2016-10-07T12:42:05.257

You are using numbers (0.1, 0.05, 0.01) that don't have exact representations as floats, in exactly the same way that 2/3 doesn't have an exact representation as a 4-digit decimal. C will use the closest float value instead, so the errors are very tiny but that's enough to make your comparisons fail unexpectedly.

Imagine if a float was a 4-digit decimal, and you had 2/3 dollar coins:

Start with Owed = 2.0000
Owed >= 0.6667, so Owed-=0.6667. Now Owed = 1.3333
1.3333 >= 0.6667, so Owed-=0.6667. Now Owed = 0.6666
Oops! Owed = 0.6666, but that is NOT >= 0.6667

You can fix this by changing your comparisons to allow for a little rounding error. Instead of saying >=0.25, >=0.1, and >=0.01, use >=0.245, >=0.095, and >=0.005

Usually, though, it's better to use a type that can exactly represent the values you want to use. Instead of float dollars, use int cents.

C - My greedy algorithm is not working CS50x

2 Answers2