Leonardo z Pizy, szerzej znany jako Fibonacci, spisał na początku XIII wieku księgę matematyczną Liber Abaci (w wolnym tłumaczeniu Księga rachunków) dotyczącą arytmetyki. W jednym z rozdziałów traktuje
ona o ułamkach egipskich. Fibonacci podał kilka metod znajdowania dla charakterystycznych typów ułamków egipskich dla liczb wymiernych oraz jedną ogólną, która zostanie zaprezentowana poniżej. Algorytm rozbicia liczby wymiernej na ułamek egipski m/n można przedstawić w następujący sposób:

jeżeli m = 1, zakończ algorytm,

w przeciwnym razie odejmij największy możliwy ułamek jednostkowy niewiększy od m/n. Następnie odejmij te dwa ułamki i procedurę kontynuuj aż do momentu, gdy licznik tak powstałego ułamka nie będzie równy 1.


Dla przykładu rozbijemy ułamek 5/13. Ponieważ 1/3<5/13<1/2, odejmujemy 5/13−1/3=2/39. Największym ułamkiem jednostkowym nieprzekraczającym 2/39 jest 1/20, proces odejmowania kontynuujemy:
2/39-1/20=1/780.
Ponieważ licznik wynosi 1, algorytm się kończy.

Ostatecznie 5/13=1/3+1/20+1/780

Ponieważ algorytm ten „wybiera” największe ułamki jednostkowe w każdym kroku, nazywany jest przez to algorytmem zachłannym. Należy się jednak zastanowić, czy algorytm Fibonacciego jest poprawny, to jest czy dla każdej liczby wymiernej z przedziału (0, 1) algorytm się zakończy. By się o tym przekonać, wystarczy zauważyć, że mimo iż mianowniki kolejnych ułamków rosną, to liczniki maleją z każdym krokiem.

Stosując rekurencję napisz program który wypisze rozkład dowolnej liczby wiekszej od 0, przedstawi w postaci ułamka egipskiego.

wejście

dwie liczby naluralne oddzielone spacją p>0,q>0, licznik i mianownik przeliczanej wielkości.

wyjście

rozkład liczby na ułamek egipski w postaci 1/a1+1/a2+1/a3+...+1/an,

gdzie a1<a2<...<an,

przykład

wejście

4 5

wyjście

1/2+1/4+1/20

przykład

wejście

1/2

wyjście

1/2