Zadanie 1.3, matura czerwiec 2023, informatyka rozszerzona

3 pktotwarteśrednie (szac.)Czerwiec 2023

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

Zadanie

Zadanie 1. Mnożenie

Następujący rekurencyjny algorytm mnożenia dwóch liczb całkowitych dodatnich x, y jest realizowany z użyciem operacji arytmetycznych dodawania i dzielenia całkowitego przez 2.

```

iloczyn(x, y):

jeżeli y = 1

wynikiem jest x

w przeciwnym razie

k ← y div 2

z ← iloczyn(x, k)

jeżeli y mod 2 = 0

wynikiem jest z + z

w przeciwnym razie

wynikiem jest x + z + z

```

Uwaga: x mod y oznacza resztę z dzielenia x przez y, natomiast x div y oznacza wynik dzielenia całkowitego x przez y.

Dla danych liczb x, y interesuje nas liczba wykonywanych operacji dodawania podczas obliczania wyniku funkcji iloczyn(x, y).

Przykład 1.

Dla liczb x=9 i y=11 algorytm wykonuje 5 dodawań. Działanie funkcji iloczyn(9, 11) można zilustrować w następujący sposób (w nawiasach obok wskazano liczbę wykonywanych operacji dodawania):

```

iloczyn(9, 11) = 9 + z + z, (dwa dodawania)

gdzie z = iloczyn(9, 5)

iloczyn(9, 5) = 9 + z + z, (dwa dodawania)

gdzie z = iloczyn(9, 2)

iloczyn(9, 2) = z + z, (jedno dodawanie)

gdzie z = iloczyn(9, 1)

iloczyn(9, 1) = 9

```

Poniższa tabela ilustruje obliczenia wykonywane podczas wywołania iloczyn(9, 11)

Numer wywołaniaParametr xParametr yObliczone kObliczone zWynik
191154599 (9+45+45)
29521845 (9+18+18)
3921918 (9+9)
491––9

Polecenie

3 punkty

Poniżej zapisano iteracyjny algorytm realizujący funkcję iloczyn(x, y). Uzupełnij trzy luki w algorytmie, tak aby był zgodny z poniższą specyfikacją.

UWAGA: spośród operacji arytmetycznych możesz użyć tylko: dodawania, odejmowania, dzielenia całkowitego i reszty z dzielenia. Nie możesz użyć zwłaszcza operacji mnożenia.

Specyfikacja:

Dane: x, y – liczby całkowite dodatnie

Wynik: z – wartość iloczynu x*y

Algorytm:

```

z ←

dopóki wykonuj:

jeżeli y mod 2 = 1

z ← z + x

x ← x + x

y ←

```

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

```

z ← 0

dopóki y ≥ 1, wykonuj:

jeżeli y mod 2 = 1

z ← z + x

x ← x + x

y ← y div 2

```

Schemat punktowania

2 pkt

odpowiedź poprawna dla 3 luk.

1 pkt

odpowiedź poprawna dla 2 luk.

0 pkt

odpowiedź niepoprawna albo brak odpowiedzi.

Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

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.