Zadanie 1.1, matura czerwiec 2023, informatyka rozszerzona
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łania | Parametr x | Parametr y | Obliczone k | Obliczone z | Wynik |
|---|---|---|---|---|---|
| 1 | 9 | 11 | 5 | 45 | 99 (9+45+45) |
| 2 | 9 | 5 | 2 | 18 | 45 (9+18+18) |
| 3 | 9 | 2 | 1 | 9 | 18 (9+9) |
| 4 | 9 | 1 | – | – | 9 |
Polecenie
2 punktyUzupełnij poniższą tabelę tak, aby ilustrowała obliczenia wykonywane podczas wywołania iloczyn(10, 45).
| Numer wywołania | Parametr x | Parametr y | Obliczone k | Obliczone z | Wynik |
|---|---|---|---|---|---|
| 1 | 10 | 45 | 22 | ||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| 6 | 1 | – | – |
Miejsce na obliczenia:
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
| Numer wywołania | x | y | k | z | Wynik |
|---|---|---|---|---|---|
| 1 | 10 | 45 | 22 | 220 | 450 |
| 2 | 10 | 22 | 11 | 110 | 220 |
| 3 | 10 | 11 | 5 | 50 | 110 |
| 4 | 10 | 5 | 2 | 20 | 50 |
| 5 | 10 | 2 | 1 | 10 | 20 |
| 6 | 10 | 1 | – | – | 10 |
Schemat punktowania
odpowiedź poprawna w 6 wierszach.
odpowiedź poprawna w 5 wierszach.
odpowiedź niepoprawna albo brak odpowiedzi.