Ćwiczenia | Informatyka MIMUW

To są zadania na wyszukiwanie binarne.

Zadanie 1 (Pierwsze wystąpienie x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź miejsce pierwszego wystąpienia x (lub 0 gdy nie ma żadnego x)

Rozwiązanie 1

To zadanie było omawiane na wykładzie. Dla pełności włączamy je tu do zestawu.

<b>function</b> ZnajdźPierwsze(N,x:integer; A:array[1..N] of integer):integer; 
//Tablica A posortowana niemalejąco; szukamy pierwszego wystąpienia x w A 
<b>var</b> l,p,s&nbsp;: integer;
<b>begin</b> 
l:=1; 
p:=N; 
<b>while</b> l &lt; p <b>do</b> <b>begin</b>
s:=(l+p)div 2; 
<b>if</b> x &gt; A[s] <b>then</b> l:=s+1
<b>else</b> p:=s; 
<b>end</b>; 
<b>if</b> A[l] = x <b>then</b> ZnajdźPierwsze:=l 
<b>else</b> ZnajdźPierwsze:=0; 
<b>end</b>;

Koszt czasowy: logarytmiczny względem N
Koszt pamięciowy: stały

Ćwiczenie 1

Jaka będzie wartość A[l] w przypadku, gdy x nie ma w tablicy A ?

Zadanie 2 (Ostatnie wystąpienie x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź miejsce ostatniego wystąpienia x (lub 0 gdy nie ma żadnego x)

Wskazówka 1

Funkcja div ciągnie w lewo. Jeśli liczba jest nieparzysta, wówczas obcina wynik w dół. Aby uzyskać symetryczny efekt, powinniśmy się zastanowić, jak zmusić div do zaokrąglania w górę.

Rozwiązanie 1

<b>function</b> ZnajdźOstatnie(N,x:integer; A:array[1..N] of integer):integer; 
//Tablica A posortowana niemalejąco; szukamy ostatniego wystąpienia x w A 
<b>var</b> l,p,s&nbsp;: integer; <b>begin</b> 
l:=1; 
p:=N; 
<b>while</b> l &lt; p <b>do</b> <b>begin</b>
s:=(l+p+1)div 2;
<b>if</b> x &lt; A[s] <b>then</b> p:=s-1 
<b>else</b> l:=s; 
<b>end</b>; 
<b>if</b> A[l] = x <b>then</b> ZnajdźOstatnie:=l 
<b>else</b> ZnajdźOstatnie:=0; 
<b>end</b>;

Koszt czasowy: logarytmiczny względem N
Koszt pamięciowy: stały

Ćwiczenie 1

Jaka będzie wartość A[l] w przypadku, gdy x nie ma w tablicy A ?

Zadanie 3 (Liczba wystąpień x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Wyznacz liczbę wystąpień x w tablicy A.

Wskazówka 1

Trzeba użyć wyszukiwania binarnego, a nie liniowego.

Rozwiązanie 1

<b>function</b> LiczbaWystąpień(N,x:integer; A:array[1..N] of integer):integer; 
//Tablica A posortowana niemalejąco; wyznaczamy liczbę wystąpień x w A 
<b>var</b> p,l: integer; 
<b>begin</b> 
l:= ZnajdźPierwsze(N,x,A); 
p:= ZnajdźOstatnie(N,x,A); 
<b>if</b> l&lt;&gt;0 <b>then</b> LiczbaWystąpień:=p-l+1 
<b>else</b> LiczbaWystąpień:=0 
<b>end</b>;

Koszt czasowy: logarytmiczny względem N
Koszt pamięciowy: stały
Wariant rozwiązania, w którym większość kodu ZnajdźPierwsze i ZnajdźOstatnie jest wpisana wprost do treści procedury:

<b>function</b> LiczbaWystąpień1(N,x:integer; A:array[1..N] of integer):integer; 
//Tablica A posortowana niemalejąco; wyznaczamy liczbę wystąpień x w A 
<b>var</b> p,l,p1,l1: integer; 
<b>begin</b>
 l1:=1; p1:=n;
 <b>while</b> l1&lt;&gt;p1 <b>do</b>
 <b>begin</b>
 s:=(l1+p1) <b>div</b> 2;
 <b>if</b> A[s]&lt;x <b>then</b> l:=s+1
 <b>else</b> p:=s
 <b>end</b>;
 l:=l1;
 l1:=1; p1:=n;
 <b>while</b> l1&lt;&gt;p1 <b>do</b>
 <b>begin</b>
 s:=(l1+p1+1) <b>div</b> 2;
 <b>if</b> A[s]&gt;x <b>then</b> p:=s-1
 <b>else</b> l:=s 
<b>end</b>;
 p:=l1; 
LiczbaWystąpień1:=p-l+1 
<b>end</b>;

Uwaga: czy kod ten jest poprawny, gdy x'a nie ma w tablicy?

Zadanie 4 (Wartość równa indeksowi)

Dana jest posortowana rosnąco tablica A typu array[1..N] of integer. Sprawdź czy występuje w niej element o wartości równej swojemu indeksowi. Jeśli tak, to wyznacz ten indeks, jeśli nie, to funkcja ma dać wartość 0.

Wskazówka 1

Jeśli A[i] < i, to też A[i-1] < i-1. I podobnie dla i-2, i-3, ... ,1.

Rozwiązanie 1

<b>function</b> Równy(N:integer; A:array[1..N] of integer):integer; 
//Tablica A posortowana rosnąco; szukamy i, takiego że A[i]=i 
<b>var</b> p,l,s: integer;
<b>begin</b>
 l:=1;
 p:=N;
<b>while</b> l &lt; p <b>do</b> <b>begin</b>
s:=(l+p)div 2; 
<b>if</b> A[s] &lt; s <b>then</b> l:=s+1 
<b>else</b> p:=s; 
<b>end</b>; 
<b>if</b> (A[l]=l) <b>then</b> Równy:=l 
<b>else</b> Równy:=0; 
<b>end</b>;

Dla tablic posortowanych niemalejąco to rozwiązanie nie działa.
Koszt czasowy: logarytmiczny względem N
Koszt pamięciowy: stały

Zadanie 5 (Maksimum w ciągu bitonicznym)

Dana jest tablica A typu array[1..N] of integer, w której wartości ułożone są w ciąg bitoniczny (czyli istnieje 1 ≤ i ≤ N, takie że dla wszystkich k, takich że 1 ≤ k < i zachodzi A[k] < A[k+1] a dla wszystkich k, takich że i ≤ k < N zachodzi A[k] > A[k+1]). Znajdź maksimum w tym ciągu.

Wskazówka 1

Szukamy pierwszego elementu, dla którego A[i] > A[i+1]. Trzeba uważać na przypadek gdy maksimum jest w A[N].

Rozwiązanie 1

<b>function</b> MaksBitoniczny(N:integer; A:array[1..N] of integer):integer; 
//Tablica A zawiera ciąg bitoniczny; szukamy maksimum w tym ciągu 
<b>var</b> p,l,s: integer; 
<b>begin</b> 
<b>if</b> N=1 <b>then</b> MaksBitoniczny:=1 
<b>else</b>
 <b>if</b> A[N-1] &lt; A[N] <b>then</b> MaksBitoniczny:=N 
<b>else</b> <b>begin</b>
 l:=1;
 p:=N-1; 
<b>while</b> l &lt; p <b>do</b> <b>begin</b>
 s:=(l+p)div 2;
 <b>if</b> A[s] &lt; A[s+1] <b>then</b> l:=s+1 
<b>else</b> p:=s; 
<b>end</b>;
 MaksBitoniczny:=l; 
<b>end</b>; 
<b>end</b>;

Koszt czasowy: logarytmiczny względem N
Koszt pamięciowy: stały

Zadanie 6 (Pierwiastek z x)

Napisz program obliczający sufit z pierwiastka z x, dla \( x \in N ,x>0 \) (oczywiście bez operacji pierwiastek).

Wskazówka 1

Najprostsze rozwiązanie jest liniowe ze względu na wartość pierwiastka z x.

Rozwiązanie 1

<b>function</b> SufitZPierwiastka1(x:integer):integer; 
//Dla x &gt; 0 wyznaczamy sufit z pierwiastka z x 
<b>var</b> i: integer; 
<b>begin</b> 
i:=1; 
<b>while</b> x &gt; i*i <b>do</b> i&nbsp;:= i+1;
 SufitZPierwiastka1&nbsp;:= i;
<b>end</b>;

Koszt czasowy: pierwiastkowy względem x
Koszt pamięciowy: stały

Wskazówka 2

Oczywiście lepiej jest to zrobić binarnie. Szukamy takiej liczby całkowitej i z przedziału [1..x], że (i-1)*(i-1) < x ≤ i*i.

Rozwiązanie 2

<b>function</b> SufitZPierwiastka2(x:integer):integer; 
//Dla x &gt; 0 wyznaczamy sufit z pierwiastka z x 
<b>var</b> l,p,s&nbsp;: integer; 
<b>begin</b>
 l:=1; 
p:=x; 
<b>while</b> l &lt; p <b>do</b> <b>begin</b>
s:=(l+p)div 2;
 <b>if</b> x &gt; s*s <b>then</b> l:=s+1 
<b>else</b> p:=s; 
<b>end</b>; 
SufitZPierwiastka2:=l; 
<b>end</b>;

Koszt czasowy: logarytmiczny względem x
Koszt pamięciowy: stały

Inna wersja zadania

A jak znaleźć podłogę z pierwiastka z x ?

Wskazówka 3

Analogicznie jak w Rozwiązaniu 2.

Rozwiązanie 3

<b>function</b> PodłogaZPierwiastka(x:integer):integer; 
//Dla x &gt; 0 wyznaczamy podłogę z pierwiastka z x 
<b>var</b> l,p,s&nbsp;: integer;
<b>begin</b>
 l:=1;
 p:=x;
 <b>while</b> l &lt; p <b>do</b> <b>begin</b>
 s:=(l+p+1)div 2;
 <b>if</b> x &lt; s*s <b>then</b> p:=s-1 
<b>else</b> l:=s; 
<b>end</b>;
PodłogaZPierwiastka:=l; 
<b>end</b>;

Uwaga: porównaj różnice między Rozwiązaniami 2 i 3 oraz funkcjami ZnajdźPierwsze, ZnajdźOstatnie z Zadania 1 i 2.
Koszt czasowy: logarytmiczny względem x
Koszt pamięciowy: stały

Zadanie 7 (BinPower)

Dla zadanych x,n > 0 wyznacz xⁿ (oczywiscie bez exp i ln).

Wskazówka 1

Oczywiście nie chodzi o to, by pomnożyć x przez siebie n-1 razy.

Wskazówka 2

Użyj podobnego pomysłu jak przy mnożeniu chłopów rosyjskich. Pamiętaj, że mnożenie ma się tak do dodawania, jak potęgowanie do mnożenia.

Rozwiązanie 1

<b>function</b> BinPower(x,n:integer):integer; 
// Dla x,n &gt; 0 wyznaczamy x do potęgi n 
<b>var</b> z,y,i: integer; 
<b>begin</b> 
z:=1; 
y:=x; 
i:=n; 
<b>while</b> i &gt; 0 <b>do</b> <b>begin</b>
<b>if</b> (i mod 2 = 1) <b>then</b> z:=z*y;
 y:=y*y;
 i:=i div 2;
<b>end</b>;
BinPower:=z;
<b>end</b>;

Koszt czasowy: logarytmiczny względem N
Koszt pamięciowy: stały

O ile istnieją proste algorytmy mnożące w czasie wielomianowym (choćby szkolne słupki), to w przypadku potęgowania nie ma oczywistego szybkiego algorytmu potęgującego. Można spytać, po co usprawniać kod potęgowania, gdy wykładniki w naturze wcale nie sa takie duże. Nic bardziej mylnego! W jednym z najpopularniejszych algorytmów kryptograficznych - kodowaniu RSA - używa się potęgowania o wykładnikach będących bardzo dużymi liczbami (zazwyczaj stukilkudziesięciocyfrowymi!). Poleglibyśmy sromotnie, gdybyśmy próbowali mnożyć odpowiednią liczbę razy przez siebie podstawę potęgowania.

Zadanie 8 (Najdłuższy podciąg niemalejący)

Dana jest tablica A typu array[1..N] of integer, N > 1. Należy obliczyć długość najdłuższego podciągu niemalejącego w A.

Wskazówka 1

Kluczowe jest użycie dodatkowej tablicy B rozmiaru N, w której pod indeksem i przechowuje się minimalną wartość kończącą podciąg niemalejący o długości i w dotychczas przejrzanej części tablicy A, od 1 do k. Żeby uwzględnić A[k+1], należy w tablicy B odnależć miejsce na A[k+1] (najlepiej binarnie).

Rozwiązanie 1

Zacznijmy od pomocniczej funkcji ZnajdźPierwszyWiększy(A:array[1..N] of integer; l,p,x:integer):integer, która w tablicy A, na odcinku od l do p, wyznacza indeks pierwszego elementu o wartości większej od x przy założeniu że A[p] > x.

<b>function</b> ZnajdźPierwszyWiększy(C:array[1..N] of integer; l,p,x:integer):integer; 
//Tablica C jest posortowana niemalejąco na odcinku od l do p, zakładamy, że C[p] &gt; x; 
//szukamy indeksu pierwszego elementu z lewej większego od x 
<b>var</b> s: integer;
<b>begin</b>
<b>while</b> l &lt; p <b>do</b> <b>begin</b>
s:=(l+p+1)div 2; 
<b>if</b> x &lt; C[s] <b>then</b> p:=s-1
<b>else</b> l:=s; 
<b>end</b>;
<b>if</b> C[l] &lt;= x <b>then</b> ZnajdźPierwszyWiększy:=l+1
<b>else</b> ZnajdźPierwszyWiększy:=l; 
<b>end</b>;

Teraz funkcja MaxNiemalejący:

<b>function</b> MaxNiemalejący(N:integer; A:array[1..N] of integer):integer; 
<b>var</b> ia,ib,z: integer;
 B: array[1..N] of integer; 
<b>begin</b> 
ib:=1;
 B[ib]:=A[1];
 <b>for</b> ia:=2 <b>to</b> N <b>do</b>
 <b>if</b> A[ia] &gt;= B[ib] <b>then</b> <b>begin</b> 
ib:=ib+1;
 B[ib]:=A[ia]; 
<b>end</b> 
<b>else</b> <b>begin</b> 
z:=ZnajdźPierwszyWiększy(B,1,ib,A[ia]); B[z]:=A[ia]; 
<b>end</b>;
 MaxNiemalejący:=ib;
 <b>end</b>;

Ponieważ dla każdego elementu A wykonujemy wyszukiwanie binarne w B to:
Koszt czasowy: O(N×logN)
Koszt pamięciowy: liniowy względem N

Ćwiczenie 1

Czy algorytm zachłanny by zadziałał? Zachłanność polegałaby na tym, że przedłużalibyśmy podciąg pod warunkiem, że rozważany element jest niemniejszy od ostatniego elementu dotychczas znalezionego maksymalnego podciągu.