|
|
| Linia 1: |
Linia 1: |
| {{powrot|Wstęp do programowania| do głównej strony wykładu}}
| |
|
| |
|
| {{powrot|WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|do modułu Gramatyki – definiowanie składni i semantyki wyrażeń}}
| |
|
| |
| 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)
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' ZnajdźPierwsze(N,x:integer; A:array[1..N] of integer):integer;
| |
| //Tablica A posortowana niemalejąco; szukamy pierwszego wystąpienia x w A
| |
| '''var''' l,p,s : integer;
| |
| '''begin'''
| |
| l:=1;
| |
| p:=N;
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p)div 2;
| |
| '''if''' x > A[s] '''then''' l:=s+1;
| |
| '''else''' p:=s;
| |
| '''end''';
| |
| '''if''' A[l] = x '''then''' ZnajdzPierwsze:=l
| |
| '''else''' ZnajdzPierwsze:=0;
| |
| '''end''';
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Jaka będzie wartość A[l] w przypadku gdy x nie ma w tablicy A ?
| |
| </div>
| |
| </div>}}
| |
|
| |
| == 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)
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' ZnajdźOstatnie(N,x:integer; A:array[1..N] of integer):integer;
| |
| //Tablica A posortowana niemalejąco; szukamy ostatniego wystąpienia x w A
| |
| '''var''' l,p,s : integer;
| |
| '''begin'''
| |
| l:=1;
| |
| p:=N;
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p+1)div 2;
| |
| '''if''' x < A[s] '''then''' p:=s-1;
| |
| '''else''' l:=s;
| |
| '''end''';
| |
| '''if''' A[l] = x '''then''' ZnajdzOstatnie:=l
| |
| '''else''' ZnajdźOstatnie:=0;
| |
| '''end''';
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Jaka będzie wartość A[l] w przypadku gdy x nie ma w tablicy A ?
| |
| </div>
| |
| </div>}}
| |
|
| |
| == 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.
| |
|
| |
| {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Trzeba użyć wyszukiwania binarnego a nie liniowego.
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' LiczbaWystąpień(N,x:integer; A:array[1..N] of integer):integer;
| |
| //Tablica A posortowana niemalejąco; wyznaczamy liczbę wystąpień x w A
| |
| '''var''' p,l: integer;
| |
| '''begin'''
| |
| l:= ZnajdźPierwsze(N,A,x);
| |
| p:= ZnajdźPierwsze(N,A,x);
| |
| '''if''' l <> 0 '''then''' LiczbaWystąpień:=p-l+1;
| |
| '''end''';
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| == 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.
| |
|
| |
| {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Jeśli A[i] < i to też A[i-1] < i-1. I podobnie dla i-2, i-3...1.
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' Równy(N:integer; A:array[1..N] of integer):integer;
| |
| //Tablica A posortowana rosnąco; szukamy i, takiego że A[i]=i
| |
| '''var''' p,l,s: integer;
| |
| '''begin'''
| |
| l:=1;
| |
| p:=N;
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p)div 2;
| |
| '''if''' A[s] < s '''then''' l:=s+1;
| |
| '''else''' p:=s;
| |
| '''end''';
| |
| '''if''' (A[l]=l) '''then''' Równy:=l
| |
| '''else''' Równy:=0;
| |
| '''end''';
| |
| Dla tablic posortowanych niemalejąco to rozwiązanie nie działa.
| |
|
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| == 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.
| |
|
| |
| {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">Szukamy pierwszego elementu dla którego A[i] > A[i+1]. Trzeba uważać na przypadek gdy maksimum jest w A[N].
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' MaksBitoniczny(N:integer; A:array[1..N] of integer):integer;
| |
| //Tablica A zawiera ciąg bitoniczny; szukamy maksimum w tym ciągu
| |
| '''var''' p,l,s: integer;
| |
| '''begin'''
| |
| '''if''' N=1 '''then''' MaksBitoniczny:=1
| |
| '''else'''
| |
| '''if''' A[N-1] < A[N] '''then''' MaksBitoniczny:=N
| |
| '''else''' '''begin'''
| |
| l:=1;
| |
| p:=N-1;
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p)div 2;
| |
| '''if''' A[s] < A[s+1] '''then''' l:=s+1;
| |
| '''else''' p:=s;
| |
| '''end''';
| |
| MaksBitoniczny:=l;
| |
| '''end''';
| |
| '''end''';
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| == Zadanie 6 (Pierwiastek z x)==
| |
| Napisz program obliczający sufit z pierwiastka z x, dla xεN, x > 0 (oczywiście bez operacji pierwiastek).
| |
|
| |
| {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Najprostsze rozwiązanie jest liniowe.
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' SufitZPierwiastka1(x:integer):integer;
| |
| //Dla x > 0 wyznaczamy sufit z pierwiastka z x
| |
| '''var''' i: integer;
| |
| '''begin'''
| |
| i:=1;
| |
| '''while''' x > i*i '''do''' i := i+1;
| |
| SufitZPierwiastka1 := i;
| |
| '''end''';
| |
| ''Koszt czasowy'': liniowy względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">Oczywiście lepiej jest to zrobic binarnie. Szukamy takiej liczby całkowitej i z przedziału [1..x], że (i-1)*(i-1) < x ≤ i*i.
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' SufitZPierwiastka2(x:Real):integer;
| |
| //Dla x > 0 wyznaczamy sufit z pierwiastka z x
| |
| '''var''' l,p,s : integer;
| |
| '''begin'''
| |
| l:=1;
| |
| p:=x;
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p)div 2;
| |
| '''if''' x > s*s '''then''' l:=s+1;
| |
| '''else''' p:=s;
| |
| '''end''';
| |
| SufitZPierwiastka2:=l;
| |
| '''end''';
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| ===Inna wersja zadania===
| |
| A jak znaleźć podłogę z pierwiastka z x ?
| |
|
| |
| {{wskazowka| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Analogicznie jak w Rozwiązaniu 2.
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' PodłogaZPierwiastka(x:Real):integer;
| |
| //Dla x > 0 wyznaczamy podłogę z pierwiastka z x
| |
| '''var''' l,p,s : integer;
| |
| '''begin'''
| |
| l:=1;
| |
| p:=x;
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p+1)div 2;
| |
| '''if''' x < s*s '''then''' p:=s-1;
| |
| '''else''' l:=s;
| |
| '''end''';
| |
| PodłogaZPierwiastka:=l;
| |
| '''end''';
| |
| 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 N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| == Zadanie 7 (BinPower)==
| |
| Dla zadanych x,n > 0 wyznacz x<sup>n</sup> (oczywiscie bez exp i ln).
| |
|
| |
| {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| Oczywiście nie chodzi o to by pomnożyć x przez siebie n-1 razy.
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| '''function''' BinPower(x,n:integer):integer;
| |
| // Dla x,n > 0 wyznaczamy x do potęgi n
| |
| '''var''' z,y,i: integer;
| |
| '''begin'''
| |
| z:=1;
| |
| y:=x;
| |
| i:=n;
| |
| '''while''' i > 0 '''do''' '''begin'''
| |
| '''if''' (i mod 2 = 1) '''then''' z:=z*y;
| |
| y:=y*y;
| |
| i:=i div 2;
| |
| '''end''';
| |
| BinPower:=z;
| |
| '''end''';
| |
| ''Koszt czasowy'': logarytmiczny względem N
| |
|
| |
| ''Koszt pamięciowy'': stały
| |
| </div>
| |
| </div>}}
| |
|
| |
| == 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.
| |
|
| |
| {{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
| |
| 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).
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">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.
| |
| '''function''' 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] > x;
| |
| //szukamy indeksu pierwszego elementu z lewej większego od x
| |
| '''var''' s: integer;
| |
| '''begin'''
| |
| '''while''' l < p '''do''' '''begin'''
| |
| s:=(l+p+1)div 2;
| |
| '''if''' x < C[s] '''then''' p:=s-1;
| |
| '''else''' l:=s;
| |
| '''end''';
| |
| '''if''' C[l] <= x '''then''' ZnajdźPierwszyWiększy:=l+1
| |
| '''else''' ZnajdźPierwszyWiększy:=l;
| |
| '''end''';
| |
|
| |
| Teraz funkcja MaxNiemalejący:
| |
|
| |
| '''function''' MaxNiemalejący(N:integer; A:array[1..N] of integer):integer;
| |
| '''var''' ia,ib,z: integer;
| |
| B: array[1..N] of integer;
| |
| '''begin'''
| |
| ib:=1;
| |
| B[ib]:=A[1];
| |
| '''for''' ia:=2 '''to''' N '''do'''
| |
| '''if''' A[ia] >= B[ib] '''then''' '''begin'''
| |
| ib:=ib+1;
| |
| B[ib]:=A[ia];
| |
| '''end'''
| |
| '''else''' '''begin'''
| |
| z:=ZnajdźPierwszyWiększy(B,1,ib,ia);
| |
| B[z]:=A[ia];
| |
| '''end''';
| |
| MaxNiemalejący:=ib;
| |
| '''end''';
| |
| Ponieważ dla każdego elementu A wykonujemy wyszukiwanie binarne w B to:
| |
|
| |
| ''Koszt czasowy'': O(N×logN)
| |
|
| |
| ''Koszt pamięciowy'': liniowy względem N
| |
| </div>
| |
| </div>}}
| |
|
| |
| {{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">Czy algorytm zachłanny by zadziałał (przedłużamy podciąg o ile rozpatrywany element jest większy równy od ostatniego elementu dotychczas znalezionego podciągu) ?
| |
| </div>
| |
| </div>}}
| |
