Алчен алгоритъм при представяне на египетски дроби
Наричаме тези дроби египетски, т.к древните египтяни са използвали само дроби с числител 1, т.е. всяка дроб се е представяла и записвала като дроб с числител 1 или сума от дроби с само числител 1.
Друго често срещано название за дроб с числител 1 и знаменател естествено число е аликвотна дроб.
Няколко уточнения: дроб от вида c/z, където c,z принадлежи на множеството на естествените числа и c<z.
Примерът, който ще разгледаме е 7/9 и тази дроб може да се представи като:
7/9 = 1/9 + 1/9 + 1/9 + 1/9 + 1/9 + 1/9 + 1/9
При използване на алчен алгоритъм за решаване на задачата: на всяка стъпка поредния член в сумата да бъде максималната дроб, която може да се добави към текущата сума така, че резултатът да не надвишава c/z.
7/9 = 1/2 + 1/4 + 1/36
Следващата примерна програма дава решена задача за египетски дроби:
#include <iostream>
using namespace std;
void kratni (unsigned long &c, unsigned long &z)
// ako chislitelq i znamenatelq sa kratni se sykrashawat
{ if (z % c ){;}//ako ne sa kratni
else
{ z /=c;
c=1;//chislitelq weche e samo 1
}
}//void kratni
void egipet (unsigned long c, unsigned long z)
{ unsigned long ob;
cout<<c<<"/"<<z<<" = ";
if (c>z) {cout<<c/z<<" + ";c%=z;}//ako chislitelqt e > ot znamenatelq
kratni(c, z);//prowerka dali chislitelq ne e naj-golqm obsh delitel
while (c>1)//dokato ostawashata drob ima chislitel >1
{ ob = (c + z) / c; //tyrsim naj-golqmata drob 1/r, taka che 1/r<=p/q
cout<<"1/"<<ob<<" + ";
//izchislqwa/me na c/z - 1/ob
c = c * ob - z;
z = z * ob;
kratni(c, z);
}//while
if (c >0)cout<<c<<'/'<<z<<endl;
}//void egipet
int main()
{ unsigned long int c,z;//ostawashiq znamenatel move da se poluchi golqmo chislo
char ose;
cout<<"Egipetski drobi - se predstawqt kato suma ot drobi, w koqto\n";
cout<<"wsqko ot sybiraemite ima za chislitel 1.\n";
cout<<"Da se systawi programa, chrez koqto se wywevdat 2 estestweni\n";
cout<<"chisla N,M ot interwala [2..102] N za chislitel, a M za \n";
cout<<"znamenatel N<M, Programata da predstawi tqhnoto otnoshenie\n";
cout<<"kato egipetska drob.\n";
cout<<"Primer: 3 5 Izhod: 3/5 = 1/2 + 1/10\n";
do {
cout<<"Wywedete chislitel: ";cin>>c;
cout<<"Wywedete znamenatel: ";cin>>z;
egipet(c,z);
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
} while (ose=='y');
return 0;
}//kraj na programa egipetski drobi
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
