Zadanie 1.2, matura czerwiec 2015, informatyka rozszerzona

3 pktotwartetrudne (szac.)Czerwiec 2015

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

Zadanie

Zadanie 1. Kod uzupełnień do dwóch

W kodzie uzupełnień do dwóch (w skrócie U2) zapisujemy liczby całkowite w dwójkowym systemie pozycyjnym. W n-bitowym systemie U2 reprezentujemy liczby całkowite z przedziału [−(2n−1), 2n−1 − 1]. Przykładowo – dla n = 8 są to liczby:

–128, –127, ..., 0, 1, ..., 127.

Zapis (an−1an−2…a2a1a0)U2, gdzie a0,a1,…,an−1∈{0,1}a_0,a_1,\ldots,a_{n-1}\in\{0,1\}, oznacza liczbę

−an−1 ⋅ 2n−1 + an−2 ⋅ 2n−2 + ⋯ + a1 ⋅ 21 + a0 ⋅ 20.

W porównaniu do klasycznego zapisu dwójkowego, w kodzie U2 najbardziej znaczący bit (an−1) ma przeciwną „wagę”. Przykładowo: w reprezentacji 8-bitowej (n = 8) wagi bitów a0, a1, a2, a3, a4, a5, a6, a7 są równe odpowiednio: 1, 2, 4, 8, ..., 64, –128. W takim systemie reprezentacje liczb 117 i –82 wyglądają następująco:

(01110101)U2 = −0 ⋅ 27 + 1 ⋅ 26 + 1 ⋅ 25 + 1 ⋅ 24 + 0 ⋅ 23 + 1 ⋅ 22 + 0 ⋅ 21 + 1 ⋅ 20 =

= 64 + 32 + 16 + 4 + 1 = 117

(10101110)U2 = −1 ⋅ 27 + 0 ⋅ 26 + 1 ⋅ 25 + 0 ⋅ 24 + 1 ⋅ 23 + 1 ⋅ 22 + 1 ⋅ 21 + 0 ⋅ 20 =

= −128 + 32 + 8 + 4 + 2 = −82

Polecenie

3 punkty

Poniżej przedstawiono algorytm wyznaczania liczby przeciwnej do danej liczby zapisanej w kodzie U2.

Specyfikacja:

Dane: liczba naturalna n > 1, reprezentacja (an−1an−2…a2a1a0)U2 liczby naturalnej x (x ≠ 0 oraz x ≠ −2n−1) w n-bitowym kodzie U2.

Wynik: reprezentacja (bn−1bn−2…b2b1b0)U2 liczby (–x) w n-bitowym kodzie U2.

Algorytm:

```text

1. i ← 0

2. dopóki a_i = 0 wykonuj:

a) b_i ← 0

b) i ← i + 1

3. b_i ← a_i

4. i ← i + 1

5. dopóki i < n wykonuj:

a) b_i ← not(a_i)

b) i ← i + 1

```

Uwaga: not oznacza negację bitu, tzn. not(0) = 1, not(1) = 0.

Podaj wynik wykonania algorytmu dla n = 16 i x = (1111001001110000)U2

Podaj przykład liczby zapisanej w 16-bitowym kodzie U2, dla której algorytm nie wykona żadnej instrukcji z wnętrza pętli w kroku 2.

Podaj przykład liczby zapisanej w 16-bitowym kodzie U2, dla której algorytm w pętli z kroku 5 wykona dokładnie 7 razy operację not.

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

1. (0000110110010000)U2; i = 4, ai = 1

2. Dowolny ciąg zerojedynkowy o długości 16, zakończony jedynką, tzn. ciąg postaci xxxxxxxxxxxxxxx1.

3. Dowolny ciąg zerojedynkowy o długości 16, którego 9 ostatnich bitów to 100000000, tzn. ciąg postaci: xxxxxxx100000000

Schemat punktowania

1 pkt

poprawny wynik algorytmu oraz poprawny bit ai oraz indeks.

1 pkt

poprawny przykład liczby dla której algorytm nie wykona instrukcji w kroku 2.

1 pkt

poprawny przykład liczby dla której operacja not w kroku 5 wykona się dokładnie 7 razy.

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.