CODEWITHSUNDEEP
c++algorithm
nahive
nahive

Reputation: 263

Simple greedy algorithm. Infinite loop

I wrote a simple greedy algorithm, but somehow it doesn't work. 

#include <stdio.h>
#include <iostream>
#include <conio.h>

int main(void)
{
    float change;
    std::cout << "Change: ";
    std::cin >> change;
    int quantity = 0;
    while(change > 0.0){
        if(change >= 0.5){
            change -= 0.5;
        }
        else if(change >= 0.25){
            change -= 0.25;
        }
        else if(change >= 0.1){
            change -= 0.1;
        }
        else if(change >= 0.05){
            change -= 0.05;
        }
        else if(change >= 0.01){
            change -= 0.01;
        }
        quantity++;
        std::cout << change << std::endl;
    }
    std::cout << quantity << std::endl;
    _getch();
    return 0;
}

While it works for 0.5 and 0.25 it doesn't for 0.01 or 0.1 for example. (it looks like it returns some really small number) I can't see where the problem is.

//EDIT Converted everything to int values to avoid problem mentioned below Zeno

Upvotes: 0

Views: 3553

Answers (2)

user2249683
user2249683

Reputation:

The problem is elementary: While 0.5, 0.25, 0.125, ... are 'exact' floating point numbers 0.1, 0.01 are not: You compare/subtract is wrong. In the set 0.1 ... 0.9 the only 'exact' floating point is 0.5.

(All of that assumes binary floating points)

Upvotes: 4

Alexis Wilke
Alexis Wilke

Reputation: 20798

You need a case when change is between 0.01 and 0.0, maybe avoid the last if()?

    else if(change >= 0.05){
        change -= 0.05;
    }
    else /*if(change >= 0.01)*/ {
        change -= 0.01;
    }

Upvotes: 0

Related Questions