[Algorytmy] Tablica zero-jedynkowa - matura 2010

[Trok]

Jest to zadanie z matury rozszerzonej z informatyki z roku 2010:

(link do zadania, w pdf jest bardziej czytelne: ... a_PR_I.pdf)

Zadanie 2. Tablica zero-jedynkowa (8 pkt)
W tablicy a[1…1023] zapisano ciąg zer i jedynek w taki sposób, że wszystkie zera
poprzedzają jedynki.
Uwaga: W tablicy mogą być same zera lub same jedynki.
Oto niepełny algorytm obliczania liczby zer w tablicy a:
← – oznacza instrukcję przypisania
div – oznacza dzielenie całkowite

Kod: Zaznacz cały

liczba_zer ← 0
l ← 1, p ← 1023
dopóki l ≤ p wykonuj
s ←(l + p)div 2
jeśli a[s] =1 to
p←s − 1
w przeciwnym przypadku
liczba_zer ← liczba_zer + …………………
l ← …………………

a) Uzupełnij opis algorytmu, wstawiając w miejsce kropek stosowne wyrażenie, tak aby
obliczał on zawsze poprawnie liczbę zer z tablicy a.

Odpowiedź:
pierwsza luka: s - l + 1
druga luka: s + 1


Mógłby mi ktoś wytłumaczyć działanie tego kodu?
Wydaje mi się, że w ogóle nie sprawdza on 2 części tablicy.

Z góry dzięki za pomoc.


[pfauel]

algorytm ten to modyfikacja tzw. wyszukiwania binarnego ()
Opiera się on na zasadzie "dziel i zwyciężaj". Nie widzisz, gdzie jest sprawdzana druga część ciągu?

Kod: Zaznacz cały

jeśli a[s] =1 to
p←s − 1

Ten warunek jest odpowiedzialny za "pierwszą" część ciągu i jeżeli jest prawdziwy to już dalszej części ciągu nie musisz sprawdzać, ponieważ jest już pewne, że dalej 0 nie znajdziesz. Dlatego przesuwamy górną granice sprawdzanego przedziału na miejsce od którego mamy pewność, że już dalej 0 nie ma (p←s − 1).

Kod: Zaznacz cały

w przeciwnym przypadku
liczba_zer ← liczba_zer + s - l + 1
l ← s + 1

Ta część kodu sprawia, że "przenosimy się" na "drugą" część ciągu. Jeśli a[s] było 0 to mamy pewność, że wszystko przed s również jest 0 (czyli mamy na pewno s zer). Dlatego możemy zapisać: liczba_zer ← liczba_zer + s - l + 1, dlaczego to wszystko a nie po prostu liczba_zer ← s? Zauważ, że to daje ten sam wynik, ponieważ liczba_zer - l + 1 daje tutaj 0. Ustawiając tutaj l na s + 1 przesuwamy dolną granice sprawdzanego przedziału za miejsce gdzie znaleźliśmy 0, czyli tam gdzie już mamy pewność, że wcześniej są same 0.
Warunek końca

Kod: Zaznacz cały

dopóki l ≤ p wykonuj

polega na tym, że sprawdzamy, dopóki dolna granica sprawdzanego przedziału ciągu jest mniejsza od górnej, czyli kończymy jeżeli już mamy wszystko sprawdzone
Mam nadzieję, że pomogłem
pozdrawiam

[Trok]

Dzięki za odp, źle zrozumiałem treść zadania.
Myślałem, że "wszystkie zera poprzedzają jedynki" oznacza, że przed każdym zerem stoi jedynka, czyli np. w ten sposób:
10111110111010

[misiu9091909]

Zgadzam się, to polecenie jest niezrozumiałe i powinien dostać po uszach, ten co układa. Również na początku pomyślałem, że przed każdym zerem stoi jedynka, jest to najbardziej logiczne tłumaczenie tego niejednoznacznego zdania.