Informatyka I – Lab 10, r.a. 2011/2012

prow. Sławomir Czarnecki

Zadania na laboratorium nr. 10

Po utworzeniu nowego projektu, dołącz bibliotekę bibs.h.

1. Zdefiniuj dwie wersje funkcji „silnia” n! = n ⋅ ( n − ) 1 ⋅ ( n − 2) ⋅...⋅ 2 ⋅1 dla dowolnego n ≥ 0 .

Pierwszą wersję rekurencyjną:

unsigned long silnia(unsigned long n) i drugą wersję iteracyjną

unsigned long SILNIA(unsigned long n) Przetestuj działanie obu tych funkcji dla n nie większego od 12.

2. Zdefiniuj (bardzo niewydajną) rekurencyjną wersję unsigned long binomial(unsigned long n, unsigned long k) funkcji na współczynnik dwumianowy

 n 

n!

=

 

dla 0 ≤ k ≤ n

k

  k (

! n − k )!

korzystając z następującej prostej do udowodnienia indukcyjnie zależności rekurencyjnej

 n −1  n −1

 n  

+

0 < k < n



 



=

   k −1

k



 



k

  1

k = 0

lub

k = n



która pozwala wyeliminować konieczność obliczania wyrażenia typu n! lub k ! .

 n 

 n 

Algorytm rekurencyjny oblicza aż 2

−1

 

wyrazów w celu obliczenia wartości   .

k

 

k

 

Wykorzystując tablicę B = B

=

=

(

, gdzie składowa B [ i][ j] ( i 0,1,..., n, j

0,1,..., k )

n+ )

1 × ( k + )

1

 i 

będzie zawierała wartość   możliwe jest „skonstruowanie” znacznie wydajniejszej j

 

iteracyjnej wersji algorytmu

unsigned long BINOMIAL(unsigned long n, unsigned long k) Definiowanie składowych macierzy B oparte jest rekurencyjną zależność

[ ][ ]  B[ i − ]1[ j − ]1+ B[ i − ]

1 [ j] 0 < j < i

B i

j = 

1

j = 0

lub

j = i



oraz o realizację w porządku wstępującym, rozpoczynającym się od pierwszego wiersza i wyliczającym po kolei wartości w wierszach tablicy B. Każda kolejna składowa wiersza (od lewej do prawej) jest wyliczana na podstawie wartości składowych w wierszu poprzedzającym przy wykorzystaniu powyższej zależności rekurencyjnej. Ostatnia obliczana

 

 n = 4

wartość, to [ ][ ]

n

B n k =   . Np. przy obliczaniu 

 mamy

k

 

k = 2





B[0][0] = 1

(wartość B[0][0] nie jest potrzebna w dalszych obliczeniach) B[1][0]

=

1

B[1][1]

=

1

B[2][0]

=

1

B[2][1]

=

B[1][0] + B[1][1] = 1 + 1 = 2

B[2][ k=2]

=

1

B[3][0]

=

1

B[3][1]

=

B[2][0] + B[2][1] = 1 + 2 = 3

B[3][ k=2]

=

B[2][1] + B[2][2] = 2 + 1 = 3

B[ n=4][0]

=

1

B[ n=4][1]

=

B[3][0] + B[3][1] = 1 + 3 = 4

B[ n=4][ k=2] =

B[3][1] + B[3][2] = 3 + 3 = 6

(Uwaga ! możliwych jest jeszcze szereg wielu dodatkowych ulepszeń). Przetestuj działanie obu tych funkcji.

3. Zdefiniuj dwie, odpowiednio rekurencyjną i iteracyjną wersję double bisection(double ( * f )(double), double a, double b, double eps) double BISECTION(double ( * f )(double), double a, double b, double eps) funkcji poszukiwania pierwiastka ciągłej funkcji jednej zmiennej rzczywistej f : ℝ → ℝ w przedziale domkniętym I = [ a, b] ⊂ ℝ z dokładnością eps > 0, w oparciu o algorytm metody bisekcji. Zakładamy, że wartości funkcji f na końcach przedziału I są różne od zera i mają różne znaki.

W wersji rekurencyjnej mamy:

• Pre: x lewy < x prawy , eps > 0. Znaki f( x) w punktach x lewy i x prawy muszą być różne, co wystarcza do stwierdzenia, że w przedziale [ x lewy , x prawy] znajduje się co najmniej jeden pierwiastek.

• Rozpoczynamy od wyznaczenia punktu środkowego x srodek = ( x lewy + x prawy) / 2.

• Należy wyróżnić dwa przypadki elementarne: x prawy – x lewy < eps lub f( x srodek) = 0 dla których pierwiastek = x srodek.

• Nie spełnienie żadnego z przypadków elementarnych prowadzi do rekurencyjnego wywołania funkcji:

bisection( f, x lewy, x srodek, eps) jeśli f( x lewy) f( x srodek) < 0

lub

bisection( f, x srodek, x prawy, eps) jeśli f( x lewy) f( x srodek) > 0.

f(x prawy )

pierwiastek

x lewy

x prawy

x srodek

f(x lewy )

f(x prawy )

pierwiastek

x lewy

x prawy

x srodek

f(x lewy )

f(x prawy )

x

x

lewy

prawy

x srodek

pierwiastek

f(x lewy )

W wersji iteracyjnej strategia polega poszukiwaniu pierwiastka od skrajnego lewego punktu przedziału I w kierunku prawym lub od skrajnego prawego punktu przedziału I w kierunku lewym, w zależności od tego, w którym z tych punktów wartość funkcji jest ujemna. Każdy kolejny przyrost (dodatni lub ujemny) jest połową wartości ostatniego przyrostu, przy czym nie dopuszczamy do sytuacji, w której wartość funkcji w nowo sprawdzanym punkcie byłaby dodatnia (zawsze jesteśmy po ujemnej stronie). Szczegóły będą omówione na laboratorium.

Przetestuj działanie obu tych funkcji dla funkcji f ( x) 3

2

= x − 8 x − 35 x +150 w przedziale

[-3 , 4], której wykres przedstawiono na poniższym rysunku.

4. Sortowanie tablicy a[ dim] przez wstawianie (por. np. Cormen T., Leiserson C., Rivest R., Wprowadzenie do algorytmów, Wyd. Naukowo-Techniczne, Warszawa 1997). Algorytm jest analogiczny do czynności porządkowania talii kart. Zaczynamy od „pustej” lewej ręki, po czym bierzemy ze stołu kolejne karty i wstawiamy je we właściwe miejsca w posortowanej już części talii kart trzymanej w lewej ręce. Aby znaleźć właściwe miejsce dla danej karty trzymanej w prawej ręce, porównujemy ją (od strony prawej do lewej) z posortowanymi już

kartami, które mamy w lewej ręce. Przykład:

lewa ręka

stół z nieposortowanymi kartami

5 2 4 6 1 3

talia na stole do posortowania

5

2 4 6 1 3

bierzemy pierwszą kartę 5 ze stołu do lewej ręki 5 2

4 6 1 3

bierzemy drugą kartę

2 ze stołu do lewej ręki

2 5

4 6 1 3

szukamy dla karty

2 właściwego miejsca w lewej ręce

2 5 4

6 1 3

bierzemy trzecią kartę

4 ze stołu do lewej ręki

2 4 5

6 1 3

szukamy dla karty

4 właściwego miejsca w lewej ręce

2 4 5 6

1 3

bierzemy czwartą kartę 6 ze stołu do lewej ręki

2 4 5 6 1

3

bierzemy piątą kartę

1 ze stołu do lewej ręki

2 4 5 1 6

3

szukamy dla karty

1 właściwego miejsca w lewej ręce

2 4 1 5 6

3

szukamy dla karty

1 właściwego miejsca w lewej ręce

2 1 4 5 6

3

szukamy dla karty

1 właściwego miejsca w lewej ręce

1 2 4 5 6

3

szukamy dla karty

1 właściwego miejsca w lewej ręce

1 2 4 5 6 3

bierzemy szóstą kartę

3 ze stołu do lewej ręki

1 2 4 5 3 6

szukamy dla karty

3 właściwego miejsca w lewej ręce

1 2 4 3 5 6

szukamy dla karty

3 właściwego miejsca w lewej ręce

1 2 3 4 5 6

szukamy dla karty

3 właściwego miejsca w lewej ręce

Uwaga ! Elementy tablicy mogą być sortowane w miejscu, tzn. nie jest konieczne definiowanie żadnej innej dodatkowej tablicy pomocniczej i wszystkie operacje można przeprowadzać na elementach sortowanej tablicy.

5. Porównanie dwóch algorytmów sortowania: insert_sort(...) oraz quick_sort(...).

Utwórz dość dużą tablicę v typu double (np. v[100000]) inicjalizując ją dowolnymi liczbami losowymi (na przykład z przedziału [–1000.0,1000.0]).

Przeprowadź dla tablicy v test szybkości działania obu algorytmów sortowania insert_sort(...) i quick_sort(...).

6. Zaimplementuj algorytm poszukiwania binarnego w posortowanej tablicy a[dim] jako funkcję int binary_search(double* a, double x, int dim). Funkcja binary_search(...) ma zwracać najmniejszy indeks i (0 ≤ i < dim) , dla którego x = a[ i] lub –1, jeśli nie istnieje składowa wektora a równa x. Idea (dobrze znanego i bardzo prostego) algorytmu poszukiwania binarnego przedstawiona będzie w czasie zajęć.