Zadanie 2.2, matura dodatkowa 2020, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Ułamki egipskie
Ułamkami egipskimi nazywamy ułamki postaci , gdzie m jest liczbą całkowitą większą od 1.
Każdą dodatnią liczbę wymierną a < 1 można przedstawić w postaci sumy ułamków egipskich o różnych mianownikach. Takich różnych rozkładów może być kilka.
Jedna z metod rozkładu liczby wymiernej a na sumę ułamków egipskich jest następująca:
1. Szukamy najmniejszej liczby całkowitej n nie mniejszej od odwrotności a. Ułamek jest największym ułamkiem egipskim w rozkładzie liczby a.
2. Liczbę odejmujemy od a i otrzymujemy pewną różnicę r, która jest liczbą wymierną mniejszą od 1. Jeżeli r jest równe 0, to rozkład został znaleziony. W przeciwnym przypadku znajdujemy w ten sam sposób rozkład liczby r na ułamki egipskie, które dopisujemy do rozkładu liczby a.
Przykład:
Niech . Aby znaleźć największy ułamek egipski, który nie jest większy od a, szukamy najmniejszej liczy całkowitej nie mniejszej od odwrotności danego ułamka . Liczba 2 jest taką liczbą, zatem największym ułamkiem egipskim w rozkładzie liczby a jest .
W kolejnym kroku znajdujemy rozkład na ułamki egipskie liczby .
Ostatecznie otrzymujemy rozkład: .
Polecenie
4 punktyNapisz w wybranej przez siebie notacji (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) algorytm, który dla danej dodatniej liczby wymiernej a < 1, zadanej w postaci (gdzie p, q – liczby całkowite dodatnie, p < q), wypisze jej rozkład na sumę ułamków egipskich.
Uwaga: w zapisie możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), porównywanie liczb, wypisywanie liczb, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje. Możesz również wykorzystać funkcję zaokrąglającą wartość liczby rzeczywistej do najmniejszej liczby całkowitej nie mniejszej od danej liczby (tzw. sufit).
Specyfikacja:
Dane:
p, q – dodatnie liczby całkowite, p < q
Wynik:
ciąg k różnych liczb dodatnich, całkowitych n1 < n2 < ⋯ < nk, gdzie k > 0, taki, że
Przykład: dla p = 4 i q = 5 poprawnym wynikiem działania algorytmu jest ciąg liczb 2, 4, 20.
Algorytm:
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
```
void ul_egipt(int p, int q)
{
if (p>0)
{
int m=ceil(float(q)/p);
cout<<m<<" ";
ul_egipt(p*m-q,q*m);
}
}
```
Schemat punktowania
za poprawny algorytm, w tym:
– za warunek początkowy – 1 punkt
– za użycie poprawnej metody wyznaczania mianownika ułamków – 2 punkty
– za wyprowadzenie właściwego wyniku – 1 punkt.
Komentarz. Algorytm wykorzystuje rekurencję lub iterację do rozkładu. Warunkiem przerwania jest p=0.