DODAJ ZADANIE




Kategorie

  1.  
    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
 

Korzystanie z Witryny oznacza zgodę na wykorzystywanie plików cookies. Możesz zablokować cookies zmieniając ustawienia w Twojej przeglądarce.