Kolokwium z AA1 - 1999-06-04 - grupa 2 1. Udowodnij metodą indukcji matematycznej poprawność poniższego wzoru: 13 + 33 + 53 + · · · + (2n − 1)3 = n2 (...
4 downloads
14 Views
45KB Size
Kolokwium z AA1 - 1999-06-04 - grupa 2 1. Udowodnij metodą indukcji matematycznej poprawność poniższego wzoru: 13 + 33 + 53 + · · · + (2n − 1)3 = n2 (2n2 − 1) 2. Rozwiąż metodą czynnika sumacyjnego układ równań (wyznacz T (n) jako funkcję n): 5T (n − 1) = T (n) + 7 T (0) = 1 3. Wyznacz średnią liczbę porównań x z elementami tablicy a dla poniższego algorytmu wyszukiwania binarnego: procedure BinarySearch ( a , l , r , x : integer ) ; var s : integer ; begin s : = ( l + r ) div 2 ; i f a [ s ] = x then return s ; else i f a [ s ] < x then BinarySearch ( a , l , s−1 , x ) ; else BinarySearch ( a , s+1 , r , x ) ; endif ; endif ; end ; Załóż, że wyszukiwany element występuje w tablicy a dokładnie raz. Przyjmij, że procedura jest wywoływana z parametrami l = 1, r = 31. 4. Wyznacz oczekiwaną wartość s po wykonaniu poniższej procedury. procedure t ; var a , b , c : integer ; begin a : = random ( 0 , 10 ) ; b : = random ( 1 , 9 ) ; c : = random ( 2 , 8 ) ; s := 0 ; if b > a s := 1 ; else if c = a s := 2 ; endif ; endif ; end ; Przyjmij, że funkcja random(x, y) generuje całkowitą liczbę losową z przedziału < x, y >.
3