Zadanie 1.2, matura czerwiec 2023, informatyka rozszerzona

2 pktobliczenioweś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

2 punkty

Dla liczb x, y wymienionych w poniższej tabeli podaj liczbę operacji dodawania, jaka zostanie wykonana podczas obliczania wyniku funkcji iloczyn(x, y).

xyLiczba dodawań
9115
832
247
112112

Miejsce na obliczenia

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

xyLiczba dodawań
9115
8325
2479
1121128

Schemat punktowania

2 pkt

odpowiedź poprawna w 3 wierszach.

1 pkt

odpowiedź poprawna w 2 wierszach.

0 pkt

inna odpowiedź niepoprawna albo brak odpowiedzi.

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.