Matematyka.pl

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
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.


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? 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). 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 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

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

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.