2. Kolokwium - [1999]

pseudo Drugie kolokwium poprawkowe z AA1 - 1999-06-24 1. Rozwiąż metodą czynnika sumacyjnego układ równań (wyznacz T (n) jako funkcję n):  T (0) = 2 3T (n) = 3T (n − 1) + n2 2. Stosując metodę indukcji matematycznej udowodnij poprawność poniższej równości: 14 + 24 + 34 + · · · + n4 =

n(n + 1)(2n + 1)(3n2 + 3n − 1) 30

3. Wyznacz średnią liczbę porównań elementów tablicy a z e wykonywanych przez następujący algorytm wyszukiwania: src11.src Załóż, że: • n jest liczbą parzystą, • tablica a jest posortowana rosnąco, • tablica a nie zawiera dwóch takich samych elementów, • wyszukiwany element e znajduje się w tablicy a. 4. Wyznacz zależność liczby operacji dominujących od parametru n dla procedury licz zapisanej w Pascal-u: src12.src Załóż, że operacją dominującą jest wywołanie procedury writeln. Funkcja Length zwraca długość łańcucha, funkcja copy(łańcuch, początek, długość) część łańcucha zaczynającą się od podanego indeksu i o podanej długości. Indeksy znaków w łańcuchu zaczynają się od jedynki.

1