Informatika gyűjtemény

Egy szinttel feljebb Egyiptomi törtek

2004050607080910

NézetNyomtat

Egyiptomi törtek

Egyik legrégebbi írásos emlékünk, a megtalálójáról elnevezett Rhind-papirusz, az egyiptomi matematika 4000 évvel ezelőtti módszereibe nyújt betekintést. A papirusz táblázataiból kiderül, hogy az egyiptomi matematikusok a racionális számokat különböző egészek reciprokának – úgynevezett egységtörteknek – az összegeként írták fel. Először Leonardo Pisano (Fibonacci) bizonyította be a 12. században, hogy minden racionális szám felírható különböző egységtörtek összegeként.
A felíráshoz tartozó legenda szerint a sólyom-fejű isten - Hórusz - szemének részeihez tartozott egy-egy törzstört, és így a Hórusz-szimbólum részletei különböző törteket határoztak meg.

Feladat

Készíts programot, amely kiszámítja egy 0 és 1 közé eső racionális szám egyiptomi felbontását! Törekedj arra, hogy minél kevesebb tört segítségével állítsd elő a felbontást, és a nevezők legyenek minél kisebbek.

Bemenet

A racionális szám számlálóját és nevezőjét a standard inputról kell beolvasni, a két pozitív egész számot egy szóköz választja el.

Kimenet

A felbontáson kívül ki kell írni a felbontásban szereplő törtek számát, és az előforduló legnagyobb nevezőt. Az eredményt a standard outputra kell írni.

Példák

$\frac{3}{7}=\frac{1}{3}+\frac{1}{11}+\frac{1}{231}$
3/7 = 1/3+1/11+1/231
db = 3
max = 231
$\frac{3}{7}=\frac{1}{4}+\frac{1}{8}+\frac{1}{28}+\frac{1}{56}$
3/7 = 1/4+1/8+1/28+1/56
db = 4
max = 56