Zadanie 2.2, matura dodatkowa 2020, informatyka rozszerzona

4 pktotwartetrudne (szac.)Dodatkowa 2020

Darmowe konto pozwoli wrócić do niego później.

Zadanie

Zadanie 2. Ułamki egipskie

Ułamkami egipskimi nazywamy ułamki postaci 1m\frac1m, 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 1n\frac1n jest największym ułamkiem egipskim w rozkładzie liczby a.

2. Liczbę 1n\frac1n 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 a=45a=\frac45. 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 1a=54\frac1a=\frac54. Liczba 2 jest taką liczbą, zatem największym ułamkiem egipskim w rozkładzie liczby a jest 12\frac12.

W kolejnym kroku znajdujemy rozkład na ułamki egipskie liczby 45−12=310\frac45-\frac12=\frac3{10}.

Ostatecznie otrzymujemy rozkład: a=45=12+14+120a=\frac45=\frac12+\frac14+\frac1{20}.

Polecenie

4 punkty

Napisz 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 pq\frac pq (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 pq=1n1+1n2+⋯+1nk\frac pq = \frac1{n_1}+\frac1{n_2}+\dots+\frac1{n_k}

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.

Wypróbuj za darmo

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

4 pkt

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.