The Greedy algorithm/method
A greedy algorithm repeatedly executes a procedure which tries to maximize the return based on examining local conditions, with the hope that the outcome will lead to a desired outcome for the global problem.
In some cases such a strategy is guaranteed to offer optimal solutions, and in some other cases it may provide a compromise that produces acceptable approximations. Typically, the greedy algorithms employ simple strategies that are simple to implement and require minimal amount of resources. For most optimization problems, greedy algorithms are not optimal. But when they are, they are usually the fastest available.
Scope: Greedy algorithms do not always yield a genuinely optimal solution. In such cases the greedy method is frequently the basis of a heuristic approach. Even for problems which can be solved exactly by a greedy algorithm, establishing the correctness of the method may be a non-trivial process. Greedy approximation algorithms have been frequently used to obtain sparse solutions to learning problems. For example, all known greedy algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.
Egyptian fractions: The ancient Egyptians only used fractions of the form 1/n so any other fraction had to be represented as a sum of such unit fractions and, furthermore, all the unit fractions were different! An example:
6/7 = 1/2 + 1/3 + 1/42
This problem is solved using the greedy method.
using namespace std;
int main()
{
int numerator,denominator, i=1; //define the numerator and denominator
double factor,temp; //define the factor for division num/den
cout << “Enter numerator and then denominator” << endl;
cin>>numerator>>denominator;
factor=double(numerator)/double(denominator); //divide the factor
do //and put it in temp
{
temp=double(1)/double(++i); //result value of the fraction
if(factor>=temp) //if factor is less than temp then subtract
{ //temp from factor and then print the factor
cout << i << ” “;
factor = factor - temp;
}
}while(factor>0 && i<32000); //check for all factors till the denominator is
} //32000 and as long as it is greater than 0
hey it’s not working on my borland 3.1 he show my 2 3 43 and 1807
Hi C,
download the Dev C compiler and try it! You can find the compiler on http://www.bloodshed.net/devcpp.html
Good luck. Let me know if you have some trouble!
I had the same problem with the code as “C” did (though Java/Eclipse). I believe the program doesn’t work properly because the computer rounds doubles. Even in this example (6/7) the error grows big enough to cause false results.
I suggest a more accurate version using fractions instead of floating :
#include
using namespace std ;
void main ()
{
int numerator,denominator ;
cout > numerator >> denominator ;
int i = 1 ;
// factor == factor_num/factor_den
int factor_num = numerator ;
int factor_den = denominator ;
do {
// temp == 1 / i ==> factor >= temp factor_num/factor_den >= 1/i factor_num*i >= factor_den
i ;
if (factor_num*i >= factor_den)
{
cout 0 ) ;
}
Thanks for you site !
Gaspos
Ooops ! the copy/paste did not worked proprely !
I try once more :
#include
using namespace std ;
void main ()
..{
..int numerator,denominator ;
..
..cout > numerator >> denominator ;
..int i = 1 ;
..// factor == factor_num/factor_den
..int factor_num = numerator ;
..int factor_den = denominator ;
..do {
….// temp == 1 / i ==> factor >= temp
….// factor_num/factor_den >= 1/i
….// factor_num*i >= factor_den
….i ;
….if (factor_num*i >= factor_den)
……{
……cout 0 ) ;
..}
I had to put ‘.’ instead of ‘ ‘ to keep indentation.
Pleace replace ‘.’ with ‘ ‘ before to compile !
Gaspos
It’s me again !
I understood : the character inferior is interpreted !
So here a new version with inferior replaced with ‘^’ :
#include ^iostream>
using namespace std ;
void main ()
..{
..int numerator,denominator ;
..
..cout ^^ “Enter numerator and then denominator” ^^ endl ;
..cin >> numerator >> denominator ;
..int i = 1 ;
..// factor == factor_num/factor_den
..int factor_num = numerator ;
..int factor_den = denominator ;
..do {
….// temp == 1 / i ==> factor >= temp
….// == factor_num/factor_den >= 1/i
….// == factor_num*i >= factor_den
….i ;
….if (factor_num*i >= factor_den)
……{
……cout ^^ ” 1/” ^^ i ;
……// factor - 1/i
……// == factor_num/factor_den - 1/i
……// == (factor_num*i - factor_den)/(factor_den*i)
……factor_num = factor_num*i - factor_den ;
……factor_den = factor_den*i ;
……}
….}
….while ( factor_num > 0 ) ;
..}
I had to put ‘.’ instead of ‘ ‘ to keep indentation.
Pleace replace ‘.’ with ‘ ‘
and ‘^’ with inferior sign before to compile !
Gaspos
i tried to undarstand gaspos’s method…but i can’t see why doesn’t he increase(/modify) “i”…..
..int i = 1 ;
….i ;//was it i; ?
or the double character is interpreted too?
@ Gaspos: You can use the online HTML encoder to encode your programme’s source code and then post it here. This form obviously doesn’t escape the text and displays it as HTML in browser. Let me check:
alert(’Yep, it does not escape it!’)
Cheers.