Wstęp do programowania / Ćwiczenia 5: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Aneczka (dyskusja | edycje)
700 edycji
Aneczka (dyskusja | edycje)
700 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
{{powrot|Wstęp do programowania| do głównej strony wykładu}}
{{powrot|Wstęp do programowania| do głównej strony wykładu}}


{{powrot|modul_5|do modułu 5}}
{{powrot|WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|do modułu Gramatyki – definiowanie składni i semantyki wyrażeń}}


To są ćwiczenia z gramatyk bezkontekstowych.
To są zadania na wyszukiwanie binarne.


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
== Zadanie 1 (Pierwsze wystąpienie x)==
Ogladaj rozwiązania __SHOWALL__<br>
Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź
Ukryj rozwiązania __HIDEALL__
miejsce pierwszego wystąpienia x (lub 0 gdy nie ma żadnego x)
</div>


{{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


==Zadanie 1 (palindromy)==
''Koszt pamięciowy'': stały
Napisz gramatykę generującą wszystkie palindromy nad alfabetem {0,1}.
</div>
</div>}}


{{rozwiazanie|||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
S → &epsilon; | 0 | 1 | 0S0 | 1S1
Jaka będzie wartość A[l] w przypadku gdy x nie ma w tablicy A ?
</div>
</div>}}


''Zgodność'': (każde wygenerowane słowo jest palindromem) Dowód przez indukcję po długości wyprowadzenia.
== 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)


Przypadek bazowy: wyprowadzenie długości 1. Są 3 przypadki: S → &epsilon;, S → 0, S → 1. Wszystkie wygenerowane słowa są palindromami.
{{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


Krok indukcyjny: załóżmy że wszystkie wyprowadzenia długości < n (dla danego n>1) są zgodne. Weźmy dowolne wyprowadzenie S →...→ x długości n. Wyprowadzenie to może zaczynać się od produkcji S → 0S0 lub S → 1S1. W pierwszym przypadku x=0y0, a z jego wyprowadzenia łatwo odczytać wyprowadzenie S →...→ y o długości n-1. Z założenia indukcyjnego y jest palindromem, zatem jest nim również słowo x=0y0. Analogicznie dowodzimy zgodność wyprowadzenia zaczynającego się od produkcji S → 1S1.
''Koszt pamięciowy'': stały
</div>
</div>}}


''Pełność'': (każdy palindrom da się wygenerować) Dowód przez indukcję po długości słowa.
{{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>}}


Przypadek bazowy: jeśli słowo ma długość 0 lub 1, to jest to &epsilon;,  0 lub 1. Wszystkie te słowa dają się wygenerować.
== 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.


Krok indukcyjny: jeśli palindrom x ma długość > 1, to jest postaci 0y0 lub 1y1, gdzie y jest palindromem o mniejszej dlugości. Z założenia indukcyjnego S →...→ y. Zatem S → 0S0 →...→ 0y0 lub S → 1S1 →...→ 1y1 i otrzymaliśmy wyprowadzenie słowa x.
{{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>
</div>}}
</div>}}


==Zadanie 2==
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Napisz gramatykę generującą język wszystkich słów nad alfabetem {0,1} postaci <math>0^n1^m0^{n+m}</math>.
'''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
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
'''var''' p,l: integer;
J → &epsilon; | 1J0
'''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


S → J | 0S0
''Koszt pamięciowy'': stały
 
symbol startowy: S
 
''Zgodność'': (każde wygenerowane słowo należy do języka) pokażemy przez indukcję po długości wyprowadzenia, że każde słowo wyprowadzone z J jest postaci <math>1^m0^m</math> oraz że każde słowo wyprowadzone z S jest postaci <math>0^n1^m0^{n+m}</math>.
 
Przypadek bazowy: wyprowadzenie długości 1 jest możliwe tylko z J i rzeczywiście wyprowadzone słowo &epsilon; jest postaci <math>1^m0^m</math> (dla m=0).
 
Krok indukcyjny: załóżmy, że wszystkie wyprowadzenia o długości < n (dla pewnego n>1) spełniają tę własność. Weźmy dowolne wyprowadzenie o długości n. Jego pierwszym krokiem jest S → J, S → 0S0 lub J → 1J0,
 
W pierwszym przypadku wyprowadzenie zawiera wyprowadzenie o długości n-1 startujące z J. Z założenia indukcyjnego wiemy, że wyprowadzone słowo jest postaci <math>1^m0^m</math>, a więc również <math>0^n1^m0^{n+m}</math> (dla n=0).
 
W drugim przypadku wyprowadzone słowo jest postaci 0x0, gdzie x jest wyprowadzalny z S za pomocą n-1 kroków. Zatem z założenia indukcyjnego x jest postaci <math>0^n1^m0^{n+m}</math>, zatem <math>0x0=0^{n+1}1^m0^{n+m+1}</math>, zatem jest też jest tej postaci.
 
W trzecim przypadku wyprowadzone słowo jest postaci 1x0, gdzie x można wyprowadzić z J w n-1 krokach, zatem podobnie jak poprzednio 1x0 jest postaci <math>1^m0^m</math>, ponieważ x ma tę postać (z założenia indukcyjnego).
 
''Pełność'': (każde słowo języka da się wyprowadzić). Najpierw przez indukcję po m pokażemy, że każde słowo postaci <math>1^m0^m</math> można wyprowadzić z J. Następnie przez indukcję po n, że każde słowo postaci <math>0^n1^m0^{n+m}</math> można wyprowadzić z S.
 
Istotnie, jeśli m=0 to słowo <math>1^00^0=\epsilon</math> można wyprowadzić z J. Zakładając, że słowo <math>1^m0^m</math> można wyprowadzić z J, łatwo widać, że wyprowadzenie J → 1J0 →...→ 11<sup>m</sup>0<sup>m</sup>0 jest wyprowadzeniem słowa <math>1^{m+1}0^{m+1}</math>. Podobnie łatwo pokazać, że każde słowo postaci <math>0^n1^m0^{n+m}</math> da się wyprowadzić z S.
</div>
</div>
</div>}}
</div>}}


==Zadanie 3 (wyrażenia nawiasowe)==
== Zadanie 4 (Wartość równa indeksowi)==
Napisz gramatykę generującą wszystkie poprawne wyrażenia nawiasowe.
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.


{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
S → SS | (S) | &epsilon;
Jeśli A[i] < i to też A[i-1] < i-1. I podobnie dla i-2, i-3...1.
 
''Zgodność'': (każde wygenerowane słowo jest poprawnym wyrażeniem nawiasowym) Niech L oznacza język poprawnych wyrażeń nawiasowych. Dowód zgodności przez indukcję po długości wyprowadzenia.
 
Przypadek bazowy: poprzez wyprowadzenie długości 1 jest możliwe wygenerowanie tylko słowa &epsilon; i należy ono do L.
 
Krok indukcyjny: każde dłuższe wyprowadzenie zaczyna się od produkcji S → (S) lub S → SS. W pierwszym przypadku wygenerowane słowo będzie postaci (w), gdzie S →...→ w jest wyprowadzeniem o długości n-1, czyli w&isin;L z założenia indukcyjnego.
 
Podobnie w drugim przypadku, wygenerowane słowo będzie postaci uv, gdzie S →...→ u oraz S →...→ v są wyprowadzeniami o długości mniejszej niż n (suma długości tych wyprowadzeń wynosi n-1). Zatem u,v&isin;L, stąd uv&isin;L.
 
''Pełność'': (każde wyrażenie nawiasowe da się wyprowadzić) Dowód przez indukcję po długości wyrażenia. Wyrażenie o długości 0 (słowo puste &epsilon;) da się wyprowadzić.
 
Niech w będzie dowolnym wyrażeniem nawiasowym o długości n>0. Określmy funkcję <math>f_w(i)=\#_((w_1...w_i)-\#_)(w_1...w_i)</math>, czyli różnicę w liczbie wystąpień nawiasu otwierającego i zamykającego w prefiksie o długości i. Łatwo zauważyć, że:
* <math>f_w(0)=0</math>
* <math>f_w(n)=0</math>
* <math>f_w(i)\ge0</math> dla <math>i=0\dots n</math>
W przypadku gdy istnieje j takie, że <math>0<j<n</math> i <math>f_w(j)=0</math> słowa <math>w_1...w_j</math> oraz <math>w_{j+1}...w_n</math> są poprawnymi wyrażeniami nawiasowymi o długości mniejszej niż n. Zatem istnieją wyprowadzenia <math>S \rightarrow \cdots \rightarrow w_1...w_j</math> oraz <math>S \rightarrow \cdots \rightarrow w_{j+1}...w_n</math> i da się z nich złożyć wyprowadzenie <math>S \rightarrow SS \rightarrow \cdots \rightarrow w</math>.
 
W przypadku, gdy dla wszystkich j, <math>f_w(j)>0</math> słowo <math>w_2...w_{n-1}</math> jest poprawnym wyrażeniem nawiasowym o długości n-2, zatem wyprowadzalnym z S. Stąd łatwo otrzymać wyprowadzenie słowa w <math>S \rightarrow (S) \rightarrow \cdots \rightarrow w</math>.
</div>
</div>
</div>}}
</div>}}


{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
S → (S)S | &epsilon;
'''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.


''Zgodność'': oczywista.
''Koszt czasowy'': logarytmiczny względem N


''Pełność'': podobnie jak w Rozwiązaniu 1. Dla uzyskania danego słowa w o długości > 0 należy posłużyć się funkcją <math>f_w</math>. Przyglądając się '''pierwszej''' pozycji j>0 dla której <math>f_w(j)=0</math>, zauważamy, że słowa <math>w_2...w_{j-1}</math> oraz <math>w_{j+1}...w_n</math> są poprawnymi wyrażeniami nawiasowymi o mniejszej długości. Zatem można uzyskać wyprowadzenie słowa w <math>S \rightarrow (S)S \rightarrow \cdots \rightarrow w</math>.
''Koszt pamięciowy'': stały
</div>
</div>
</div>}}
</div>}}


==Zadanie 4==
== Zadanie 5 (Maksimum w ciągu bitonicznym)==
Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)</math>
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 &le; i &le; N, takie że dla wszystkich k, takich że 1 &le; k < i zachodzi A[k] < A[k+1] a dla wszystkich k, takich że i &le; k < N  zachodzi A[k] > A[k+1]). Znajdź maksimum w tym ciągu.


{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{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].
S → SS | 0S1 | 1S0 | &epsilon;
 
''Zgodność'': oczywista.
 
''Pełność'': podobnie jak w Zadaniu 3. Dla uzyskania słowa w o długości n należy przyjrzeć się wykresowi funkcji <math>f_w(i)=\#_0(w_1...w_i)-\#_1(w_1...w_i)</math>.
Jeśli funkcja ta nie ma miejsc zerowych poza 0 i n, pierwszą produkcją jest S → 0S1 lub S → 1S0. W przeciwnym przypadku w rozkłada się na dwa krótsze słowa o równej liczbie zer i jedynek i pierwszą produkcją jest S → SS.
</div>
</div>
</div>}}
</div>}}


{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
S → 0S1S | 1S0S | &epsilon;
'''function''' MaksBitoniczny(N:integer; A:array[1..N] of integer):integer;
 
//Tablica A zawiera ciąg bitoniczny; szukamy maksimum w tym ciągu
''Zgodność'': oczywista
'''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


''Pełność'': podobnie jak w Rozwiązaniu 1 i w Rozwiązaniu 2 Zadania 3.
''Koszt pamięciowy'': stały
</div>
</div>
</div>}}
</div>}}


==Zadanie 5==
== Zadanie 6 (Pierwiastek z x)==
Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)+1</math>
Napisz program obliczający sufit z pierwiastka z x, dla x&epsilon;N, x > 0 (oczywiście bez operacji pierwiastek).
 
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
R → 0R1 | 1R0 | RR | &epsilon;


N → 0N1 | 1N0 | RN | NR | 0
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
Najprostsze rozwiązanie jest liniowe.
symbol startowy: N
 
''Zgodność'': wiedząc (z Zadania 4), że R generuje słowa o równej liczbie 0 i 1, łatwo pokazać przez indukcję, że N generuje słowa, w których liczba 0 jest o jeden większa niż liczba 1.
 
''Pełność'': mając dane słowo w o długości > 1 zaczynamy od wskazania (dowolnego) nadmiarowego 0. Następnie postępujemy jak w Zadaniu 4, nie licząc wskazanego 0, pamiętając przy tym, żeby ta część słowa, która zawiera wskazane 0, była wyprowadzana z N, a nie z R.
</div>
</div>
</div>}}
</div>}}
<!--
R → 0R1R | 1R0R | &epsilon;
N → 0N1R | 0R1N | 1N0R | 1R0N | 0
symbol startowy: N
-->
==Zadanie 6 (liczby podzielne przez 3)==
Podaj gramatykę generującą liczby w zapisie binarnym, które są podzielne przez 3.
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
S<sub>0</sub> → 0 | S<sub>0</sub>0 | S<sub>1</sub>1
S<sub>1</sub> → 1 | S<sub>0</sub>1 | S<sub>2</sub>0
S<sub>2</sub> → S<sub>1</sub>0 | S<sub>2</sub>1
symbol startowy: S<sub>0</sub>


''Zgodność'': Łatwo pokazać, że kolejne symbole generują liczby, które w dzieleniu przez 3 mają resztę odpowiednio 0, 1 i 2. Dwa przypadki bazowe są oczywiste, następnie weźmy na przykład produkcję S<sub>1</sub> → S<sub>2</sub>0. Jeśli (z założenia indukcyjnego) S<sub>2</sub> wygeneruje liczbę w o reszcie 2, to wygenerowana przez S<sub>1</sub> liczba w0 będzie miała resztę 2×2 mod 3 = 1. Podobnie można sprawdzić wszystkie pozostałe produkcje.
{{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


''Pełność'': Przez indukcję po długości liczby pokażemy, że każdą liczbę o reszcie z dzielenia przez 3 wynoszącej i da się wygenerować z symbolu S<sub>i</sub>. Istotnie, dla liczb jednocyfrowych jest to oczywiste. Dla pozostałych, postaci wb, wystarczy popatrzeć na ostatnią cyfrę b. Reszta z dzielenia wb przez 3 oraz wartość b determinują resztę z dzielenia w przez 3. Dla wszystkich sześciu przypadków w naszej gramatyce istnieje odpowiednia produkcja. Następnie wystarczy użyć założenia indukcyjnego, aby wygenerować w.
''Koszt pamięciowy'': stały
</div>
</div>
</div>}}
</div>}}


{{cwiczenie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{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 &le;  i*i.
Jak należy zmodyfikować tę gramatykę, aby generowane liczby binarne nie mogły zaczynać się od 0 ?
</div>
</div>
</div>}}
</div>}}


{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
S<sub>0</sub> → S<sub>0</sub>0 | S<sub>1</sub>1  
'''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


S<sub>1</sub> → 1 | S<sub>0</sub>1 | S<sub>2</sub>0
''Koszt pamięciowy'': stały
 
</div>
S<sub>2</sub> → S<sub>1</sub>0 | S<sub>2</sub>1
</div>}}


S → S<sub>0</sub> | 0
===Inna wersja zadania===
A jak znaleźć podłogę z pierwiastka z x ?


symbol startowy: S
{{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>
</div>}}
</div>}}


==Zadanie 7==
{{rozwiazanie| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Podaj gramatykę generującą słowa nad alfabetem {0,1}, w których nie występuje podsłowo 000.
'''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


{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
''Koszt pamięciowy'': stały
S<sub>0</sub> → &epsilon; | S<sub>0</sub>1 | S<sub>1</sub>1 | S<sub>2</sub>1
</div>
</div>}}


S<sub>1</sub> → S<sub>0</sub>0
== Zadanie 7 (BinPower)==
Dla zadanych x,n > 0 wyznacz x<sup>n</sup> (oczywiscie bez exp i ln).


S<sub>2</sub> → S<sub>1</sub>0
{{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>}}


S → S<sub>0</sub> | S<sub>1</sub> | S<sub>2</sub>
{{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


symbol startowy: S
''Koszt pamięciowy'': stały
 
Zgodność i pełność tej gramatyki wynika z faktu, że S<sub>j</sub> generuje wszystkie słowa w nie zawierające 000 i kończące się na j zer.
</div>
</div>
</div>}}
</div>}}


{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
== Zadanie 8 (Najdłuższy podciąg niemalejący) ==
S<sub>0</sub> → &epsilon; | S<sub>0</sub>1 | S<sub>0</sub>01 | S<sub>0</sub>001
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.
 
S → S<sub>0</sub> | S<sub>0</sub>0 | S<sub>0</sub>00
 
symbol startowy: S


Ta gramatyka powstała z poprzedniej przez usunięcie symboli S<sub>1</sub> i S<sub>2</sub> i włączenie ich (pojedynczych) produkcji do produkcji pozostałych symboli.
{{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>
</div>}}
</div>}}


{{rozwiazanie| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
{{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.
Z → &epsilon; | 0 | 00
'''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''';


S → Z | S1Z
Teraz funkcja MaxNiemalejący:


symbol startowy: S
'''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:


Z - krotki ciąg zer (mniej niż 3)
''Koszt czasowy'': O(N×logN)


S - ciąg krótkich ciągów zer poprzedzielanych jedynkami
''Koszt pamięciowy'': liniowy względem N
</div>
</div>
</div>}}
</div>}}


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{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) ?
'''Dla ciekawskich ''' 
<div class="mw-collapsible-content" style="display:none">
Język opisany w tym zadaniu (i w Zadaniu 6) jest w istocie [[językiem regularnym]], czyli dającym się wygenerować bez rekurencji, a tylko poprzez iterację (czyli prostszym, niż ''zwykły'' język bezkontekstowy). Można to poznać po tym, że udało nam się stworzyć gramatykę, w której wszystkie produkcje są postaci X → Yz lub X → Y gdzie X i Y to symbole nieterminalne, a z to symbol terminalny.
 
Języki regularne mają wiele wspólnego z [[wyrażeniami regularnymi]] używanymi w prostych operacjach na tekstach, takich jak wyszukiwanie i zastępowanie (np przez programy Unixowe [[grep]], [[sed]] itp.)
</div>
</div>
</div>
</div>}}

Wersja z 12:33, 7 sie 2006

<<< Powrót do głównej strony wykładu

<<< Powrót 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)

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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)

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 6 (Pierwiastek z x)

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

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Inna wersja zadania

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

Wskazówka 3

{{{3}}}

Rozwiązanie 3

{{{3}}}

Zadanie 7 (BinPower)

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

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Wstęp_do_programowania_/_Ćwiczenia_5&oldid=10517”