алчен алгоритъм при представяне на египетски дроби

египетски дроби
допустима грешка – сходяща редица
верижни дроби
точност при изчисление - сума от дроби

Наричаме тези дроби египетски, т.к древните египтяни са използвали само дроби с числител 1, т.е. всяка дроб се е представяла и записвала като дроб с числител 1 или сума от дроби само s числител 1. Друго често срещано название за дроби с числител 1 и знаменател естествено число е аликвотна дроб.

Да припомним някои действия с дроби.
Имаме следните естествени числа a,b,c,d, представляващи числител и знаменател на две дроби: a/b и c/d.
а) събиране на дроби a/b + c/d = (a*d + b*c) / b*d
б) изваждане на дроби a/b - c/d = (a*d - b*c) / b*d
в) умножение на дроби a/b * c/d = a*c / b*d
г) делене на дроби a/b : c/d = a*d / b*c
д) сравняване на дроби: ако a/b > c/d то a*d > b*c
Нека имаме число представено като дроб с числител a и знаменател b. За такива числа, казваме че са:
- правилни дроби, ако: а < b;
- неправилни дроби, ако a > b;
- смесени дроби, ако числото е представено с цяла и дробна част;
- десетични дроби, ако знаменателят е степен на 10.
В някои от задачите се налага рационализиране на дроби - умножаване на числител и знаменател с едно и също число или израз.
Крайната цел на рационализирането е получаване на несъкратимата дроб. Ако след рационализиране на дроб нейният знаменател е по-голям от 1 разглеждаме само знаменателя. Така дробите биват: - непериодични дроби - ако знаменателя може да се представи като произведение на 2 и/или 5; - периодични дроби - в останалите случаи. При събиране/изваждане на дроби, когато събираемите са с различни знаменатели се извършва предварително привеждане под общ знаменател на участващите дроби.
При аритметични действия със смесени дроби последните се преобразуват в неправилни дроби.
Използването на дроби се среща в задачи с пропорции - просто тройно правило, намиране на най-голям общ делител и др.
Няколко уточнения: дроб от вида 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 egipetski drobi

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

Начало на страницата

допустима грешка – сходяща редица

В ред приложни задачи се налага изчисляване стойност на ирационални числа. В повечето случаи задачата се свежда до изчисляване на определен брой члена в сходяща редица за достигане на желана точност. Нека разгледаме алгоритъма за изчисляване на π, предложен от Готфрид Лайбниц: pi/4 = 1/1-1/3+1/5-1/7+1/9-1/11+...-1/(2*n-1). Целта е достигане на стойност в рамките на допустимата грешка. Не знаем предварително необходимия брой членове в редицата и ще го определим на основа предварително обявена минимална стойност на последния член от сходящата редица.

Следващата примерна блок схема илюстрира алгоритъм за работа с допустима грешка:

Алгоритъм:
Отново ще работим с аликвотна дроб.
Предварително въвеждаме допустима грешка – eps;
числителят във всяка следваща дроб сменя знака си – ще го постигнем с последователно умножение с k=-1*k;
знаменателят на всяка дроб е поредното нечетно число – ще използваме формула 2*i-1;
На всяка стъпка изчисляваме поредната дроб k/(2*i-1), и я прибавяме към получената до момента стойност на π;
сравняваме абсолютната стойност на новата дроб с желаната точност за изчисление.
Следващата примерна програма дава решена задача за допустима грешка – сходяща редица:

#include <iostream>
#include <cmath>
using namespace std;
double const eps=0.01;

int main()
{double b,k,pi=0;
int i;
 b=k=1;
 i=1;
 //Leibniz pi/4 = 1/1-1/3+1/5-1/7+1/9-1/11+...-1/(2*n-1)
 while (fabs(b)>eps)
 { b=k /(2*i-1);  
   pi+=b;
   cout<<k<<"/"<<2*i-1<<":"<<4*pi<<endl;
   i++;
   k*=-1;
}
cout<<"pi = "<<4*pi<<endl;
system("pause");
return 0;
}//tochnost - dopustima greshka

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Размер на шрифта

Търсене в сайта:

Спонсори

Изпълними приложения за

алчен алгоритъм при представяне на египетски дроби

допустима грешка – сходяща редица