Na wtorkowym (31 marca 2020) pojawiła się prośba aby zaprezentować problem binarnego wyszukiwania. Powstał gotowy program korzystający z polecenia goto (który powinien być najpierw przerobiony tak aby wykorzystywał jakieś polecenie pętlowe, a później został zaprogramowany jako funkcja).
Problem postawiony jest tak:
- Mamy tablicę (dowolnego typu) zawierającą dowolne wartości wpisane w kolejności rosnącej (albo malejącej).
- Mamy też wartość
xi mamy sprawdzić czy wartość ta znajduje się w tablicy1 czy nie (a w wersji zaawansowanej) gdzie powinna być wstawiona.
Omówię powstały program:
Początek jest dosyć standardowy:
|
1 2 3 |
#include <stdio.h> int main(int argc, char **argv) { |
Żeby ułatwić sobie modyfikację danych, tablicę zadeklarowałem tak:
|
1 2 3 4 |
int t[] = { 1, 10, 123, 200, 1000, 2000 }; int n = sizeof( t ) / sizeof( int ); |
Nie podałem jej długości, zamiast tego wpisałem kolejne wartości co ułatwi wprowadzanie zmian polegających na przykład na „skróceniu ” tablicy, które można zrealizować za pomocą wstawienia znaku komentarza: 1, 10, // 123, 200, 1000, 2000 (wszystkie liczby po znakach // „znikają”).
Pozostaje natomiast problem znajomości rozmiaru tablicy. Wykorzystałem tu polecenie języka C sizeof(). Podaje one liczbę bajtów, którą zajmuje w pamięci obiekt będący argumentem polecenia. Zatem sizeof(D) poda długość (w bajtach) tablicy D, a sizeof(int) poda długość w bajtach każdego elementu (zmienna, stała) typu int. Podzielenie tych wartości powinno dać liczbę elementów tablicy.
Teraz deklaracja pozostałych zmiennych:
|
1 2 3 4 |
int x = -1; int a, b, c; a = 0; b = n - 1; |
x to szukana wartość, a i b to początek i koniec zakresu poszukiwań (zaczynamy od całej tablicy), c to srodek przedziału , który będzie wyliczany po każdej zmianie zakresu.
|
1 2 3 4 |
poczatek: c = ( a + b ) / 2; if ( t[c] == x ) goto koniec; |
Ponieważ będę korzystał z polecenia goto musiałem wprowadzić etykietę (poczatek:) tam gdzie cykl się rozpoczyna.
Sprawdzam najpierw czy (przypadkiem) nie odnalazłem już szukanej wartości. Jeżeli tak można skończyć obliczenia (goto koniec;).
W przeciwnym razie, trzeba zdecydować, którą połówkę tablicy trzeba odrzucić:
|
1 2 3 4 |
else if ( t[c] > x ) b = c - 1; else a = c + 1; |
Jeżeli środkowa wartość tablicy jest większa niż wartość szukana to odrzucamy prawą część tablicy (wraz ze środkiem, bo już wcześniej upewniliśmy się, że nie ma tam wartości szukanej…); w przeciwnym razem odrzucamy „lewą” część tablicy wraz ze środkiem.
W tym miejscu moglibyśmy już przejść na początek, żeby kontynuować obliczenia. Ale obliczenia nie mogą trwać w nieskończoność (jak było to w przypadku szukania miejsca zerowego metodą połowienia, tam przedział mógł się skracać i skracać). Teraz operujemy na liczbach całkowitych.
W przypadku gdy nie możemy w tablicy znaleźć szukanej wartości obliczenia należy kontynuować tylko jeżeli a <= b; zatem
|
1 2 |
if ( a <= b ) goto poczatek; |
Jeżeli znaleźliśmy się w tym miejscu możemy napisać, że liczby nie znaleziono i skończyć program
|
1 2 |
printf("nie ma\n"); return 1; |
Gdy liczbę znaleziono, kończyliśmy pętle „wyskakując” z niej do etykiety koniec:
|
1 2 3 4 |
koniec: printf("wartosc jest w tablicy na miejscu %d\n", c); return 0; } |
co kończy program.
- I na którym miejscu.↩