Jarekz: /* Wyszukiwanie binarne */

2015-05-23T13:46:52Z

Wyszukiwanie binarne

Jarekz: Utworzono nową stronę " = Rekurencja = Rekurencja polega na rozwiązywaniu problemów przy następującym spostrzeżeniu: gdybyśmy mieli rozwiązanie danego problemu dla mniejszej liczby da..."

2015-05-23T13:43:35Z

Utworzono nową stronę " = Rekurencja = Rekurencja polega na rozwiązywaniu problemów przy następującym spostrzeżeniu: gdybyśmy mieli rozwiązanie danego problemu dla mniejszej liczby da..."

Nowa strona

= Rekurencja =

Rekurencja polega na rozwiązywaniu problemów przy następującym spostrzeżeniu:
gdybyśmy mieli rozwiązanie danego problemu dla mniejszej liczby danych, to rozwiązanie dla obecnej byłoby banalne. Łatwo to zobaczyć na poniższym przykładzie z obliczaniem silni:

===Przykład — obliczanie silni ===
Silnia przedstawia się następującą zależnością matematyczną:
::<math>n! = \prod_{k=1}^n k</math>
====Rekurencyjnie====
Silnię można zapisać jako równanie rekurencyjne:
::<math>\begin{matrix} &b_n = n\cdot b_{n-1}\\
&b_0 = 1\end{matrix}</math>
Jak wygląda to w praktyce? Zobaczmy, co dzieje się, gdy chcemy obliczyć <math>b_4</math>

{| class="wikitable"
|-
! Rekurencyjne obliczanie silni dla n = 4:
|-
|
b4 = 4 * b3
= 4 * 3 * b2
= 4 * 3 * 2 * b1
= 4 * 3 * 2 * 1 * b0
= 4 * 3 * 2 * 1 * 1
= 4 * 3 * 2 * 1
= 4 * 3 * 2
= 4 * 6
= 24
|}

Jak zapiszemy to równanie rekurencyjne w Pythonie?

<source lang="python">
def silnia(n):
if n == 0:
return 1
else:
return n*silnia(n-1)
</source>

====Iteracyjnie====
Silnię można oczywiście obliczyć iteracyjnie, co jest daleko bardziej wydajne.
<source lang="python">
def silnia(n):
silnia = 1
for i in xrange(2, n+1):
silnia *= i
return silnia
</source>

=== Przerywnik ===

Uruchom teraz silnia(999) i silnia(998). Co zauważasz?
W pythonie jest domyślnie ustawione ograniczenie na głębokość stosu wykonania programu = 1000. Limit ten można zmienić w następujący sposób:
<source lang="python">
import sys

sys.setrecursionlimit(1500)

</source>
Ale też nie w nieskończoność.
Żeby uniknąć takich problemów, optymalizuje się programy rekurencji tak, aby stosować tzw rekurencję ogonową:

<source lang="python">
def even(x):
if x == 0:
return True
else:
return odd(x - 1)

def odd(x):
if x == 0:
return False
else:
return even(x - 1)
</source>

<source lang="python">
def tail_rec(fun):
def tail(fun):
a = fun
while callable(a):
a = a()
return a
return (lambda x: tail(fun(x)))

def tail_even(x):
if x == 0:
return True
else:
return (lambda: tail_odd(x - 1))

def tail_odd(x):
if x == 0:
return False
else:
return (lambda: tail_even(x - 1))

even = tail_rec(tail_even)
odd = tail_rec(tail_odd)
</source>

== Do czego rekurencja będzie wygodna? ==

<korzen litera="d">
<lewy litera="b">
<lewy litera="a">
</lewy>
<prawy litera="c">
</prawy>
</lewy>
<prawy litera="f">
<lewy litera="e">
</lewy>
<prawy litera="g">
</prawy>
</prawy>
</korzen>

* Napisz program, który wczyta następujące drzewo xml i wypisze je w porządku infiksowym.
* Napisz program, który z zadanego ciągu znaków utworzy analogiczne drzewo xml, tak, aby po wypisaniu go w porzadku infiksowym otrzymać wyjściowy ciąg znaków.
* Spróbuje oba problemu rozwiązać zarówno iteracyjnie, jak rekurencyjnie. Ile linii kodu zajęło Ci rozwiązanie iteracyjne, a ile rekurencyjne? Ile razy szybciej udało Ci się napisać rozwiązanie rekurencyjnie? Ile razy pomyliłeś się pisząc rozwiązanie iteracyjne, a ile rekurencyjne?

==Ciąg Fibonacciego==
<source lang="python">
def fibonacci(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
</source>

[[Plik:fib_1_galaz.svg|thumb|<figure id="fig:fib_1_galaz"/>Ciągu Fibonacciego od liczby 4 — schemat wywołań funkcji w pierwszej gałęzi.]]

==Wyszukiwanie binarne==
Szukanie za pomocą bisekcji jest jednym z najbardziej intuicyjnych sposobów szukania wartości w uporządkowanym wektorze, czy sekwencji.
Wyobraź sobie, że musisz znaleźć liczbę 54 w sekwencji składającej się z <math>N</math> liczb od 1 do 90. Zgadywałbyś zapewne, że 54 jest to element <math>\nicefrac{N}{2}</math>. Jeżeli nie trafisz, sprawdzisz, czy wybrany element jest większy, czy mniejszy od 54. Jeżeli jest mniejszy, poszukasz go w połowie lewej części sekwencji. Jeżeli jest większy, poszukasz go w połowie prawej części sekwencji. Tak jak na rysunku:

[[File:Dsa_bin_search.svg|thub|Przykład wyszukiwania binarnego]]

Jeżeli w którymś momencie lewa granica sekwencji okaże się większa niż prawa, podzieliłeś sekwencję na 2 o raz za dużo i nie masz już w czym szukać. Zwracasz wtedy -1, na znak tego, że nie znalazłeś.

Rozwiązanie rekurencyjne tego algorytmu jest intuicyjne i sprowadza się do zapisu w poleceniami powyżej opisanej procedury. Poniżej kod w Pythonie.
<source lang="python">
def znajdz(lista, lewy, prawy, x):
if lewy>prawy:
raise IndexError
srodek = (lewy + prawy) / 2
if lista[srodek] == x:
return srodek
if lista[srodek] > x:
return znajdz(lista, lewy, srodek - 1, x)
else:
return znajdz(lista, srodek + 1, prawy, x)
</source>
===Zadanie===
Rozwiąż ten problem iteracyjnie.

==Wieże Hanoi==
[[Plik:Tower of Hanoi.jpeg|thumb|300px|<figure id="fig:hanoi1"/>Wieże Hanoi: Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C.]]
Wieże Hanoi są łamigłówką matematyczną przypominającą dziecięcą zabawkę. Tak, jak na rysunku <xr id="fig:hanoi1"/> mamy trzy słupki, oznaczone A, B i C. Na słupku A znajduje się wieża — ułożone na sobie dyski, o zmniejszającej się średnicy. Słupki B — pełniący rolę bufora; i C — będący słupkiem docelowym; są puste. Zadanie polega na przeniesieniu całej wieży ze słupka A na słupek C, zachowując zależność im wyższy dysk, tym mniejsza jego średnica, posługując się słupkiem B jako buforem. Dodatkowo:
* W każdym kroku można przenieść tylko jeden dysk.
* Krok polega na przeniesieniu dysku z wybranego słupka na inny słupek i umieszczeniu go na dyskach, które znajdują się na danym słupku.
* Dysk o większej średnicy nigdy nie może znaleźć się nad dyskiem o mniejszej średnicy.

===Rozwiązanie rekurencyjne===
Jest banalnie proste.
*Przenieść wieżę z <math>n-1</math> dysków ze słupka A na słupek B.
*Przenieść jeden dysk na słupek C.
*Przenieść wieżę z <math>n-1</math> dysków ze słupka B na słupek C.
===Rozwiązanie iteracyjne===
[[File:Tower_of_Hanoi_4.gif|thumb|300px|<figure id="fig:hanoi2"/>Wieże Hanoi: Animacja pokazująca rozwiązanie łamigówki.]]
Rozwiązanie takiego problemu z wieżą o czterech dyskach można zobaczyć na animacji na rysunku <xr id="fig:hanoi2"/>.
*Na początku należy przenieść najszerszy dysk — pomarańczowy, ze słupka A na słupek C. W tym celu:
**czerwony na B,
**żółty na C,
**czerwony na C,
**niebieski na B,
**czerwony na A,
**żółty na B,
**czerwony na B.
*Uwolniony pomarańczowy jest na słupku A. Słupek C jest wolny. Pomarańczowy przechodzi na C.
*Teraz należy przenieść niebieski na C.
**czerwony na C,
**żółty na A,
**czerwony na A.
*Uwolniony niebieski jest na słupku B. Na słupku C jest wyłącznie pomarańczowy. Niebieski przechodzi na C.
*Teraz należy przenieść żółty na C.
**czerwony na B.
*Żółty jest wolny na A, można go przenieść na C.
*Czerwony zostaje przeniesiony na C.
Łamigłówkę udało się rozwiązać.

====Algorytm iteracyjny====
#W przypadku parzystej liczby krążków:
#*wykonaj dozwolone przeniesienie pomiędzy słupkami A i B,
#*wykonaj dozwolone przeniesienie pomiędzy słupkami A i C,
#*wykonaj dozwolone przeniesienie pomiędzy słupkami B i C,
#*powtarzaj, aż przeniesiesz wszystkie.
#W przypadku nieparzystej liczby krążków:
#*wykonaj dozwolone przeniesienie pomiędzy słupkami A i C,
#*wykonaj dozwolone przeniesienie pomiędzy słupkami A i B,
#*wykonaj dozwolone przeniesienie pomiędzy słupkami B i C,
#*powtarzaj, aż przeniesiesz wszystkie.

Wykonano <math>2^n-1\;</math> ruchów.

Jak widać opis rekurencyjny jest prostszy niż iteracyjny.

===Zadanie===
Napisz program, który implementuje algorytm iteracyjny i rekurencyjny. Załóż, że słupki A, B i C są listami. Lista A jest wypełniona "dyskami" — liczbami albo słowami, listy B i C są puste.
Sprawdź swój program na dwóch zestawach danych:
*<source lang="python">A1 =['duzy', 'sredni', 'maly']</source>
*<source lang="python">A2 =['bardzo duzy', 'duzy', 'sredni', 'maly', 'bardzo maly']</source>

== Zadania różne ==

Rozwiąż [http://wazniak.mimuw.edu.pl/index.php?title=Wst%C4%99p_do_programowania/Rekursja/%C4%86wiczenia następujące zadania]

==Wyznacznik macierzy (obliczany z definicji)==
[[Plik:Macierz.svg|right]]

'''Napisz funkcję'''
<source lang='py'>
def wyznacznik_1(macierz):
"Oblicza wyznacznik korzystając z definicji."
</source>
która oblicza wyznacznik macierzy <tt>macierzy</tt> korzystając z rekurencyjnej
definicji wyznacznika.

'''Przypomnienie''': jeśli <math>M</math> jest macierzą kwadratową o wymiarze <math>n</math>,
to jej wyznacznik wynosi
:<math>\left|M\right| = \sum_{k=1}^n(-)^{i+k} a_{ik} \left|M_{/i/k}\right|</math>
gdzie <math>i</math> jest dowolne, a <math>M_{/i/k}</math> oznacza macierz o wymiarze zmniejszonym o 1 przez wykasowanie wiersza <math>i</math> oraz kolumny <math>j</math>.

Sprawdź swoją funkcję na macierzy jednostkowej różnych rozmiarów, na macierzy wypełnionej jedynkami lub zerami i na paru małych macierzach dla których jesteś w stanie samemu policzyć wynik.

'''Uwaga o funkcjach rekurencyjnych''' 
Funkcje mogą wywoływać same siebie. Funkcja <tt>f</tt> może
też wywoływać inne funkcje, które wywołają <tt>f</tt> jeszcze raz. Tak czy inaczej, w pewnym
momencie, funkcja <tt>f</tt> jest wykonywana jednocześnie dwa (lub więcej) razy. W momencie
wywołania przez funkcję <tt>f</tt> funkcji potomnej, to wykonanie zostaje zawieszone — stan
zmiennych i miejsce wykonywania jest zapamiętane. Funkcja zostaje wznowiona, kiedy
funkcja potomna zakończy działanie.

Z rekurencyjnym wywoływaniem funkcji nie należy przesadzać. Np. obliczenie miliona
liczb Fibonnaciego z deﬁnicji — w sposób rekurencyjny — raczej nie jest dobrym pomysłem. Obliczanie ich w pętli jest dużo, dużo szybsze. Niemniej, funkcje rekurencyjne są
zazwyczaj bardzo czytelne i podobne do deﬁnicji matematycznych.

==Macierz odwrotna==
Jeżeli wyznacznik macierzy M jest niezerowy (macierz jest
niezdegenerowana), można pokusić się o znalezienie macierzy
odwrotnej.

::<math>
A^{-1}=\frac{A^D}{\vert A\vert }
</math>

Macierz <math>A^D</math> jest macierzą dołączoną do macierzy A.

Macierz dołączona powstaje po transponowaniu macierzy dopełnień algebraicznych.

Element <math>ij</math> macierzy dopełnień algebraicznych to wyznacznik macierzy
powstałej z <math>A</math> poprzez skreślenie jej <math>i</math>-tego wiersza i <math>j</math>-tej kolumny,
pomnożony przez <math>(-)^{i+j}</math>.

<equation id="uid9">
<math>
A^D_{ji} = \vert A_{/i /j} \vert (-)^{i+j}
</math>
</equation>

Napisz program, który:

<ol>

<li>
wczyta macierz;

<li>
sprawdzi, czy nie jest osobliwa;

<li>
jeżeli nie jest osobliwa, obliczy macierz odwrotną;

<li>
i sprawdzi, czy iloczyn macierzy i macierzy odwrotnej daje macierz <math>I</math>.

</ol>

@@ Linia 139: / Linia 139: @@
 ==Wyszukiwanie binarne==
 Szukanie za pomocą bisekcji jest jednym z najbardziej intuicyjnych sposobów szukania wartości w uporządkowanym wektorze, czy sekwencji.
-Wyobraź sobie, że musisz znaleźć liczbę 54 w sekwencji składającej się z <math>N</math> liczb od 1 do 90. Zgadywałbyś zapewne, że 54 jest to element <math>\nicefrac{N}{2}</math>. Jeżeli nie trafisz, sprawdzisz, czy wybrany element jest większy, czy mniejszy od 54. Jeżeli jest mniejszy, poszukasz go w połowie lewej części sekwencji. Jeżeli jest większy, poszukasz go w połowie prawej części sekwencji. Tak jak na rysunku:
+Wyobraź sobie, że musisz znaleźć liczbę 54 w sekwencji składającej się z <math>N</math> liczb od 1 do 90. Zgadywałbyś zapewne, że 54 jest to element <math>\frac{N}{2}</math>. Jeżeli nie trafisz, sprawdzisz, czy wybrany element jest większy, czy mniejszy od 54. Jeżeli jest mniejszy, poszukasz go w połowie lewej części sekwencji. Jeżeli jest większy, poszukasz go w połowie prawej części sekwencji. Tak jak na rysunku:
 [[File:Dsa_bin_search.svg|thub|Przykład wyszukiwania binarnego]]
@@ Linia 160: / Linia 160: @@
 ===Zadanie===
 Rozwiąż ten problem iteracyjnie.
 ==Wieże Hanoi==

TI/Algorytmy i struktury danych/Rekurencja - Historia wersji

Jarekz: /* Wyszukiwanie binarne */

Jarekz: Utworzono nową stronę " = Rekurencja = Rekurencja polega na rozwiązywaniu problemów przy następującym spostrzeżeniu: gdybyśmy mieli rozwiązanie danego problemu dla mniejszej liczby da..."