Chaque fraction positive peut être représentée comme une somme de fractions unitaires uniques. Une fraction est une fraction unitaire si le numérateur est 1 et le dénominateur est un entier positif, par exemple 1/3 est une fraction unitaire. Une telle représentation est appelée Fraction égyptienne car elle était utilisée par les anciens Égyptiens.
Voici quelques exemples :
La représentation de la fraction égyptienne de 2/3 est 1/2 + 1/6 La représentation de la fraction égyptienne de 6/14 est 1/3 + 1/11 + 1/231 La représentation de la fraction égyptienne du 12/13 est 1/2 + 1/3 + 1/12 + 1/156
Nous pouvons générer des fractions égyptiennes en utilisant l' algorithme greedy. Pour un nombre donné de la forme 'nr/dr' où dr > nr, trouvez d'abord la plus grande fraction unitaire possible, puis répétez pour la partie restante. Par exemple, considérons 6/14, nous trouvons d'abord un plafond de 14/6, c'est-à-dire 3. Ainsi, la première fraction unitaire devient 1/3, puis se répète pour (6/14 - 1/3) c'est-à-dire 4/42. Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus.
void printEgyptian(int nr, int dr){ // If either numerator or denominator is 0 if (dr == 0 || nr == 0) return; // If numerator divides denominator, then simple division // makes the fraction in 1/n form if (dr%nr == 0) { cout << "1/" << dr/nr; return; } // If denominator divides numerator, then the given number // is not fraction if (nr%dr == 0) { cout << nr/dr; return; } // If numerator is more than denominator if (nr > dr) { cout << nr/dr << " + "; printEgyptian(nr%dr, dr); return; } // We reach here dr > nr and dr%nr is non-zero // Find ceiling of dr/nr and print it as first // fraction int n = dr/nr + 1; cout << "1/" << n << " + "; // Recur for remaining part printEgyptian(nr*n-dr, dr*n); } // Driver Programint main(){ int nr = 6, dr = 14; cout << "Egyptian Fraction Representation of " << nr << "/" << dr << " is\n "; printEgyptian(nr, dr); return 0;}La représentation de la fraction égyptienne du 6/14 est 1/3 + 1/11 + 1/231
L'algorithme Greedy fonctionne car une fraction est toujours réduite à une forme où le dénominateur est supérieur au numérateur et le numérateur ne divise pas le dénominateur. Pour de telles formes réduites, l'appel récursif en surbrillance est fait pour le numérateur réduit. Ainsi, les appels récursifs continuent de réduire le numérateur jusqu'à ce qu'il atteigne 1.