Zadanie

Liniowe przeszukiwanie ciągu liczbowego

Problem

W n-elementowym zbiorze Z wyszukać element posiadający pożądane własności.

Wyszukiwanie liniowe (ang. linear search), zwane również sekwencyjnym (ang. sequential search) polega na przeglądaniu kolejnych elementów zbioru Z. Jeśli przeglądany element posiada odpowiednie własności (np. jest liczbą o poszukiwanej wartości), to zwracamy jego pozycję w zbiorze i kończymy. W przeciwnym razie kontynuujemy poszukiwania aż do przejrzenia wszystkich pozostałych elementów zbioru Z.

W przypadku pesymistycznym, gdy poszukiwanego elementu nie ma w zbiorze lub też znajduje się on na samym końcu zbioru, algorytm musi wykonać przynajmniej n obiegów pętli sprawdzającej poszczególne elementy. Wynika z tego, iż pesymistyczna klasa złożoności obliczeniowej jest równa O(n), czyli jest liniowa – stąd pochodzi nazwa metody wyszukującej.

Często chcemy znaleźć wszystkie wystąpienia w zbiorze poszukiwanej wartości elementu. W takim przypadku algorytm na wejściu powinien otrzymywać dodatkowo pozycję (indeks) elementu, od którego ma rozpocząć wyszukiwanie. Pozycję tę przy kolejnym przeszukiwaniu podajemy zawsze o 1 większą od ostatnio znalezionej. Dzięki temu nowe poszukiwanie rozpocznie się tuż za poprzednio znalezionym elementem.

Algorytm wyszukiwania liniowego/sekwencyjnego

Wejście

n	–	liczba elementów w tablicy Z, n N
Z	–	tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
p	–	indeks pierwszego elementu Z, od którego rozpoczniemy poszukiwania. p C
k	–	poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z

Wyjście:

Pozycja elementu zbioru Z o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów Z. i C

Lista kroków:

K01:	Dla i = p,p+1,...,n-1: wykonuj K02	; przeglądamy kolejne elementy w zbiorze
K02:	Jeśli Z[i] = k, to zakończ z wynikiem i	; jeśli napotkamy poszukiwany element, zwracamy jego pozycję
K03:	Zakończ z wynikiem -1	; jeśli elementu nie ma w tablicy, zwracamy -1

Przeszukiwanie ciągu liczbowego z wartownikiem

Problem

W n-elementowym zbiorze Z wyszukać element posiadający pożądane własności.

W algorytmie wyszukiwania liniowego sprawdzamy kolejne elementy zbioru aż do napotkania jego końca lub poszukiwanego elementu. Zachodzi pytanie, czy algorytm ten można przyspieszyć. Aby na nie odpowiedzieć, zapiszmy algorytm w poniższej postaci:

Wejście

n	–	liczba elementów w tablicy Z, n N
Z	–	tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
k	–	poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z

Wyjście:

pozycja elementu zbioru Z o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów Z. i C

Numer	Operacja
1	i ← 0
2	Jeśli i ≥ n, to zakończ z wynikiem -1
3	Jeśli Z[i] = k, to zakończ z wynikiem i
4	i ← i + 1
5	Idź do 2

Sprawdzimy teraz ile operacji wykonuje ten algorytm w dwóch charakterystycznych przypadkach:

Przypadek pierwszy: poszukiwanej liczby nie ma w zbiorze. Poniżej przedstawiamy liczbę wykonań poszczególnych operacji w algorytmie:

Numer	Operacja	Liczba wykonań
1	i ← 0	1
2	Jeśli i ≥ n, to zakończ z wynikiem -1	n + 1
3	Jeśli Z[i] = k, to zakończ z wynikiem i	n
4	i ← i + 1	n
5	Idź do 2	n
	RAZEM:	4n + 2

Przypadek drugi: poszukiwana liczba statystycznie znajduje się w środku zbioru – czasem znajdziemy ją wcześniej, a czasem później, zatem średnio będzie w środku.

Numer	Operacja	Liczba wykonań
1	i ← 0	1
2	Jeśli i ≥ n, to zakończ z wynikiem -1	n/2 + 1
3	Jeśli Z[i] = k, to zakończ z wynikiem i	n/2 + 1
4	i ← i + 1	n/2
5	Idź do 2	n/2
	RAZEM:	2n + 3

Zwróć uwagę, iż w każdym obiegu pętli nasz algorytm wykonuje dwa testy – w instrukcji numer 2 i 3. Usprawnienie pracy algorytmu będzie polegało na eliminacji testu 2. Jednakże test ten jest niezbędny, aby zakończyć przeglądanie tablicy w przypadku, gdy poszukiwanego elementu nie ma w zbiorze. Skoro tak, to wstawmy poszukiwany element na koniec zbioru, wtedy test 2 stanie się zbędny, nieprawdaż. Algorytm w zmienionej postaci wygląda następująco:

Numer	Operacja
1a	Z[n] ← k
1b	i ← 0
2	usunięta
3	Jeśli Z[i] = k, to idź do 6
4	i ← i + 1
5	Idź do 3
6	Jeśli i = n, to zakończ z wynikiem -1
7	Zakończ z wynikiem i

Zmiany w stosunku do pierwotnego algorytmu są następujące:

1a – instrukcja umieszcza na końcu zbioru Z poszukiwany element o wartości k. Dzięki tej operacji dostajemy gwarancję, iż zawsze znajdziemy w zbiorze element k.

2 – test osiągnięcia końca zbioru stał się zbędny, ponieważ element o wartości k zawsze znajdziemy w zbiorze.

3, 6, 7 – znalezienie elementu o wartości k wymaga sprawdzenia, czy nie jest on elementem wstawionym do zbioru w operacji 1a. Jeśli tak, to zbiór faktycznie nie zawierał poszukiwanego elementu.

Przypadek pierwszy: poszukiwanej liczby nie ma w zbiorze. Poniżej przedstawiamy liczbę wykonań poszczególnych operacji w algorytmie:

Numer	Operacja	Liczba wykonań
1a	Z[n] ← k	1
1b	i ← 0	1
2
3	Jeśli Z[i] = k, to idź do 6	n + 1
4	i ← i + 1	n
5	Idź do 3	n
6	Jeśli i = n, to zakończ z wynikiem -1	1
7	Zakończ z wynikiem i	0
	RAZEM:	3n + 4

Przypadek drugi: poszukiwana liczba statystycznie znajduje się w środku zbioru – czasem znajdziemy ją wcześniej, a czasem później, zatem statystycznie będzie w środku.

Numer	Operacja	Liczba wykonań
1a	Z[n] ← k	1
1b	i ← 0	1
2
3	Jeśli Z[i] = k, to idź do 6	n/2 + 1
4	i ← i + 1	n/2
5	Idź do 3	n/2
6	Jeśli i = n, to zakończ z wynikiem -1	1
7	Zakończ z wynikiem i	1
	RAZEM:	3/2n + 5

Porównajmy teraz wyniki z pierwszej i drugiej wersji algorytmu w poniższej tabelce (wartości ułamkowe z ostatniej kolumny należy rozumieć jako wartości statystyczne).:

n	Przypadek pierwszy		Przypadek drugi
	Algorytm podstawowy	Algorytm usprawniony	Algorytm podstawowy	Algorytm usprawniony
	4n + 2	3n + 4	2n + 3	3/2n + 5
1	6	7	5	6,5
2	10	10	7	8
3	14	13	9	9,5
4	18	16	11	11
5	22	19	13	12,5
6	26	22	15	14
...	...	...	...	...
10	42	34	23	20
100	402	304	203	155
1000	4002	3004	2003	1505
10000	40002	30004	20003	15005
...	...	...	...	...

Chociaż początkowo algorytm pierwszy wygrywa w ilości operacji, to przy wzroście liczby elementów zbioru widzimy wyraźnie, iż algorytm usprawniony wykonuje mniej operacji (począwszy od n > 3), zatem działa szybciej.

Opisana metoda wyszukiwania nosi nazwę wyszukiwania liniowego z wartownikiem (ang. Search with Sentinel). Wartownikiem jest dodany na końcu zbioru element równy poszukiwanemu. Dzięki niemu uzyskujemy zawsze pewność znalezienia poszukiwanego elementu w zbiorze. Jeśli jest to wartownik, to elementu poszukiwanego w zbiorze nie ma i zwracamy pozycję -1. Jeśli nie jest to wartownik, to znaleźliśmy poszukiwany element w zbiorze i zwracamy jego pozycję i.

Należy podkreślić, iż wyszukiwanie z wartownikiem można stosować tylko wtedy, gdy do zbioru da się dołączyć jeszcze jeden element.

wyszukiwanie lidera w zbiorze

Problem

W n-elementowym zbiorze Z znaleźć element, którego wartość występuje więcej niż ⁿ/₂ razy.

Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru Z. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z nie posiada lidera.

Istnieje jednakże prostszy i szybszy algorytm, który korzysta z następującego twierdzenia:

Jeśli zbiór Z posiada lidera, to usunięcie z niego pary elementów różnych daje zbiór z tym samym liderem.

Dowód tego twierdzenia jest bardzo prosty. Oznaczmy przez n_L liczbę elementów będących liderami. Zbiór Z posiada n elementów, zatem liczba pozostałych elementów wynosi n - n_L. Zachodzi nierówność:

n_L > n - n_L

Przypadek 1

Ze zbioru Z usuwamy dwa elementy, które nie są liderami. W tym przypadku n_L nie zmniejsza się, lecz zmniejsza się o 2 liczba elementów n. Otrzymamy zatem:

n_L > (n - 2) - n_L
n_L > (n - n_L) - 2

Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż n_L jest liczebnością liderów), to tym bardziej będzie prawdziwa druga nierówność. Wynika z tego, iż usunięcie dwóch elementów nie będących liderami nie wpływa na występowanie lidera.

Przypadek 2

Ze zbioru Z usuwamy jeden element lidera oraz jeden element nie będący liderem. Zmniejszeniu o 1 ulega zatem liczba liderów, a liczba elementów maleje o 2. Otrzymujemy:

n_L - 1 > (n - 2) - (n_L - 1)
n_L - 1 > n - 2 - n_L + 1
n_L - 1 > (n - n_L) - 1

Otrzymaliśmy nierówność wyjściową, w której od obu stron odjęto tę samą liczbę -1. Zatem nierówność jest wciąż prawdziwa, z czego wynika, iż usunięcie ze zbioru jednego lidera i jeden element nie będący liderem nie wpływa na występowanie lidera.

Innych przypadków nie ma, zatem dowiedliśmy prawdziwości twierdzenia.

Z powyższego twierdzenia bezpośrednio wynikają dwie dalsze własności:

Jeśli zbiór posiada lidera, to usunięcie z niego wszystkich par elementów różnych daje zbiór zawierający tylko elementy będące liderem.Jeśli w wyniku takiej operacji otrzymujemy jednak zbiór pusty, to lidera w zbiorze wejściowym nie było.

Zamiast faktycznie wyrzucać ze zbioru elementy różne – co jest dosyć trudne, możemy wykonać operację odwrotną. Będziemy zliczali elementy o równych wartościach – wystarczy wtedy zapamiętać wartość elementu oraz ilość jej wystąpień. Algorytm pracuje w sposób następujący:

Licznik elementów równych L ustawiamy na zero. Rozpoczynamy przeglądanie elementów zbioru od pierwszego do ostatniego. Jeśli licznik elementów równych L jest równy 0, to kolejny element zbioru zapamiętujemy, zwiększamy licznik L o 1 i wykonujemy kolejny obieg pętli dla następnego elementu. Jeśli licznik L nie jest równy zero, to sprawdzamy, czy bieżący element jest równy zapamiętanemu. Jeśli tak, to mamy dwa elementy równe – zwiększamy licznik L o 1. W przeciwnym razie licznik L zmniejszamy o 1 – odpowiada to wyrzuceniu ze zbioru dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.

Jeśli zbiór posiadał lidera, to liczba elementów równych jest większa od liczby elementów różnych. Zatem licznik L powinien mieć zawartość większą od zera. Jeśli zawartość licznika L jest równa zero, to lidera w zbiorze nie ma. W przeciwnym razie zapamiętany element należy przeliczyć w zbiorze – jest to kandydat na lidera. Jeśli liczba jego wystąpień jest większa od liczby połowy elementów, to wytypowany element jest liderem. W przeciwnym razie zbiór Z nie posiada lidera.

Algorytm posiada liniową klasę złożoności obliczeniowej O(n), jest zatem bardziej efektywny od opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości.

Program

Program umieszcza w tablicy Z 80 liczb pseudolosowych z zakresu od 0 do 99 w taki sposób, aby mógł się pojawić w niej lider. Następnie program wyszukuje lidera podanym powyżej algorytmem, wyświetla zawartość tablicy z zaznaczonym liderem  i wypisuje jego wartość oraz liczbę wystąpień. Jeśli pomimo wszystko zdarzy się, iż w tablicy Z nie będzie lidera, program wypisze tekst BRAK LIDERA.

Jednoczesne znajdowanie minimalnego i maksymalnego elementu

Problem

W n-elementowym zbiorze Z znaleźć element maksymalny i minimalny.

Jeśli do wyszukiwania elementu max i min zastosujemy standardowy algorytm, to otrzymamy:

Wejście

n	–	liczba elementów w tablicy Z, n N
Z	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.

Wyjście:

Wartość najmniejszego i największego elementu w tablicy Z.

Zmienne pomocnicze

i	–	przebiega przez kolejne indeksy elementów Z. i   C
maxZ	–	tymczasowy element maksymalny
minZ	–	tymczasowy element minimalny

Numer Operacja Liczba wykonań 1 minZ ← Z[0] 1 2 maxZ ← Z[0] 1 3 i ← 1 1 4 Jeśli i = n, to idź do 9 n 5 Jeśli Z[i] < minZ, to minZ ← Z[i] n - 1 6 Jeśli Z[i] > maxZ, to maxZ ← Z[i] n - 1 7 i ← i + 1 n - 1 8 Idź do 4 n - 1 9 Pisz minZ, maxZ 1 10 Zakończ 1 Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z minZ oraz z maxZ. Tutaj tkwi nieefektywność. Obie operacje nr 5 i 6 są wykonywane po n - 1 razy, co daje w sumie 2n - 2 porównania w całym zbiorze. Wyobraźmy sobie, iż ze zbioru bierzemy parę 2 elementów i porównujemy je ze sobą. Element większy nie może być minimalnym, zatem nie musimy go już porównywać z minZ. Wystarczy porównanie z maxZ. To samo dotyczy elementu mniejszego – porównujemy go tylko z minZ. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z minZ i maxZ). Teraz mamy: Jedno porównanie dwóch elementów, które rozdzieli je na element mniejszy i element większy. Element mniejszy porównujemy z minZ. Element większy porównujemy z maxZ. Daje to 3 porównania zamiast 4. Ponieważ ze zbioru pobieramy po dwa kolejne elementy, to ich liczba musi być parzysta. Jeśli zbiór ma nieparzystą liczbę elementów, to po prostu dublujemy ostatni element i dostaniemy parzystą liczbę elementów. Porównanie pary elementów dzieli zbiór na dwa podzbiory – zbiór elementów większych i mniejszych. W podzbiorze elementów większych szukamy elementu maksymalnego, a w podzbiorze elementów mniejszych szukamy minimalnego. Ponieważ ich liczebność jest o połowę mniejsza od liczebności zbioru wejściowego, to wykonamy mniej operacji porównań. Metoda rozwiązywania problemów przez podział na mniejsze części w informatyce nosi nazwę Dziel i Zwyciężaj (ang. Divide and Conquer). Dzięki niej często udaje się zmniejszyć złożoność obliczeniową wielu algorytmów.

Sortowanie szybki.

Algorytm

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

1. DZIEL - problem główny zostaje podzielony na podproblemy
2. ZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemów
3. POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego

Idea sortowania szybkiego jest następująca:

DZIEL :	najpierw sortowany zbiór dzielimy na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją).
ZWYCIĘŻAJ :	każdą z partycji sortujemy rekurencyjnie tym samym algorytmem.
POŁĄCZ :	połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany.

Sortowanie przez wybór.

• Idea algorytmu sortowania przez wybór jest bardzo prosta. 

Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. 

Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. 

Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. 

W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.

W identyczny sposób postępujemy z resztą elementów należących do zbioru. 

Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji.

Otrzymamy dwa posortowane elementy. 

Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.

Algorytm sortowania przez wybór posiada klasę czasowej złożoności obliczeniowej równą O(n²). Sortowanie odbywa się w miejscu.

Sortowanie Bąbelkowe.

• Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. . Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zmianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

 Po zamianie kolejności elementów sprawdzana jest kolejna para elementów sortowanego zbioru. Dzięki temu podejściu rośnie efektywność algorytmu oraz zmienia się klasa czasowej złożoności obliczeniowej z O(n³) na O(n²).

Uwaga:

Algorytm sortowania bąbelkowego jest uważany za bardzo zły algorytm sortujący. Można go stosować tylko dla niewielkiej liczby elementów w sortowanym zbiorze (do około 5000). Przy większych zbiorach czas sortowania może być zbyt długi.

Sortowanie przez wstawianie .

• Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii.

Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii.
Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego).
Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort).
Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty.
A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

• Algorytm sortowania przez wstawianie będzie składał się z dwóch pętli.

Pętla główna (zewnętrzna) symuluje pobieranie kart, czyli w tym wypadku elementów zbioru.
Odpowiednikiem kart na ręce jest tzw. lista uporządkowana (ang. sorted list), którą sukcesywnie będziemy tworzyli na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru).
Pętla sortująca (wewnętrzna) szuka dla pobranego elementu miejsca na liście uporządkowanej.
Jeśli takie miejsce zostanie znalezione, to elementy listy są odpowiednio rozsuwane, aby tworzyć miejsce na nowy element i element wybrany przez pętlę główną trafia tam.
W ten sposób lista uporządkowana rozrasta się.
Jeśli na liście uporządkowanej nie ma elementu większego od wybranego, to element ten trafia na koniec listy.
Sortowanie zakończymy, gdy pętla główna wybierze wszystkie elementy zbioru.

Zadanie

Wypisać metody segregowania i temat 2.11.1 prezentacja na f\wtorek :D

Badanie czy dana liczba jest pierwsza

Najprostszym algorytmem określającym czy liczba n to liczba pierwsza, jest sprawdzenie czy posiada ona więcej niż dwa dzielniki. Należy więc zbadać, czy w przedziale [2,n-1] znajduje się co najmniej jedna wartośc całkowita, przez którą dzieli się liczba n.



II Kod C++

#include
using namespace std;

bool sprawdz (int n)
{
for (int i=2;i> n;
if (sprawdz(n)) cout << n << " jest liczba pierwsza" << endl;
else cout << n << " jest liczba zlozona" << endl;
cin.get();
cin.get();
return 0;

Zmiennopozycyjna reprezentacja liczb

Reprezentacja zmiennopozycyjna charakteryzuje się zmiennym położeniem kropki dziesiętnej.
Przykład
602252000000000000000000*101 wartość liczby jest w każdym przypadku taka sama, zmienia się tylko położenie kropki dziesiętnej
6,02252*1023
0,602252*1024
602252*1022

W podobny sposób przedstawiane są liczby w formacie naukowym w arkuszu kalkulacyjnym: 4,92e36, czyli 4,92*10+36
Aby liczby zapisane w ten sposób można było porównywać ze sobą, stosuje się znormalizowaną reprezentację zmiennopozycyjną, gdzie liczba przedstawiona jest jako iloczyn
a=m*10c
m - mantysa, 0,1<=|m|<1
c - cecha, liczba całkowita
Przykład: 0,662607*10-33

Stałopozycyjna reprezentacja liczb

Reprezentacja stałopozycyjna charakteryzuje się stałym położeniem kropki dziesiętnej.
Na część całkowitą liczby oraz na część ułamkową przeznaczona jest stała, z góry określona liczba bitów.
Jeśli na część ułamkową przeznaczone jest 0 bitów to reprezentacja stałopozycyjna służy do przechowywania liczb całkowitych.
Jeśli liczba, którą chcemy przedstawić w tej reprezentacji, mieści się na ustalonej liczbie bitów, to może być reprezentowana dokładnie.
Jeśli wynik działań wykonywanych na liczbach stałopozycyjnych nie mieści się na ustalonej liczbie bitów, powstaje nadmiar w obliczeniach (wynik jest błędnie interpretowany przez komputer).
Mając do dyspozycji n bitów możemy w reprezentacji stałopozycyjnej przedstawić liczby całkowite z zakresu:
-2n-1 .. 2n-1-1

Przykład
n=8: -27 .. 27-1, czyli -128 .. 127, odpowiada to typowi danych ShortInt (C++: char)
n=16: -215 .. 215-1, czyli -32788 .. 32787, odpowiada to typowi danych Integer (C++: short)
n=32: -231 .. 231-1, czyli -2 147 483 648 .. 2 147 483 647, odpowiada to typowi danych LongInt (C++: int)
Deklaracja odpowiedniego typu zmiennych w programie określa dopuszczalny zakres danych.

Rozwiązywanie Przykładów U2

I Kod uzupełnień do dwóch (U2) - system reprezentacji liczb całkowitych w dwójkowym systemie
pozycyjnym. Jest obecnie najpopularniejszym sposobem zapisu liczb całkowitych w systemach cyfrowych. Jego popularność wynika z faktu, że operacje dodawania i odejmowania są w nim wykonywane tak samo jak dla liczb binarnych bez znaku. Z tego też powodu oszczędza się na kodach rozkazów procesora.

Zaletą tego kodu jest również istnienie tylko jednego zera. Przedział kodowanych liczb nie jest przez to symetryczny. W U2 na n bitach da się zapisać liczby z zakresu:

[- 2^{n-1}\quad ,\quad 2^{n-1}-1]

Dla reprezentacji 8-bitowej (jednobajtowej) są to liczby od −128 do 127. Liczba −2n−1 nie ma liczby przeciwnej w n-bitowej reprezentacji kodu U2.

II Przykład liczby zapisanej w systemie U2

(-56)[10] = 256 - 56 = 200[10] = 11001000[2]