Dan_yef - 1 year ago 74
C Question

# greedy algorithm(with coins) in C

In my code I usede the greedy algorithm in order to use the minimum amaount of coins. For example: I must return \$0.41, the minimum amount of coins I can use is 4:

``````1 - 0,25;
1 - 0.10;
1 - 0.05;
1 - 0.01;
``````

There are 4 types of coins: 0.25,0.10,0.05,0.01.

Here is my code:

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

int main(void)
{
printf("Enter the sum, that you want to return you:");
float sum = GetFloat();
float quaters = 0.25;
float dime = 0.10;
float nickel = 0.05;
float penny = 0.01;
int count_q = 0,count_d = 0,count_n = 0,count_p = 0;

while(sum<0){
printf("Incorrect, enter the positive float number");
sum = GetFloat();
}

while(sum > 0){
if(sum - quaters >=0){
sum -=quaters;
count_q +=1;
}
else if((sum -quaters <0) && (sum -dime>=0)){
sum -= dime;
count_d +=1;
}
else if((sum - dime <0) &&(sum - nickel>=0) ){
sum -= nickel;
count_n +=1;
}
else if(sum - nickel <0){
sum -= penny;
count_p +=1;
}
}
printf("The number of quaters: %i\n",count_q);
printf("The number of dimes: %i\n",count_d);
printf("The number of nickels: %i\n",count_n);
printf("The number of pennies: %i\n",count_p);
}
``````

This code calculates how many coins of each type of was used to return the sum. In most cases it works fine.

But sometimes, for example, when i enter the number 1.12 it gives me wrong result:

``````Enter the sum, that you want to return you:1.12
The number of quaters: 4
The number of dimes: 1
The number of nickels: 0
The number of pennies: 3
``````

I think, that the problem is in last else if statement. But i don't know how can I correct it.

To my understanding, there is no bug in your code in the strictest sense, as the reasoning on which the implementation is based (a greedy algorithm) is correct. You are most likely experiencing rounding errors due to repeated subtraction, as you use `float`, the single-precision floating type to represent your values. Perhaps, if you change `float` to `double` in your code, the output will be as expected for your example input.
However, this only pushes the boundaries of the limitation. Perhaps it would be better to internally represent the amount of money in pennies as `int`.