9. Kolokwium - [2001]

15 czerwiec 2001

Sprawdzian z Analizy Algorytmów. grupa A Zadanie 1 (1 pkt.) Rozwiąż układ równań (wyznaczyć T(n) jako funkcję n):

T (0) = 4  T ( n ) = 4T ( n − 1) − 9 Zadanie 2 (2 pkt.) Jakie jest prawdopodobieństwo, że po wykonaniu poniższego algorytmu zmienna s będzie spełniała warunek s=3 ? procedurę A; var n, s : integer; begin n := 10000 + random ( 10000 ); s := 0; while ( n <>0 ) do if ( n mod 10 < 5 ) then s : = s + i ; endif; n : = n di v 10; endwhile; end;

Zadanie 3 (2 pkt.) Wyznacz średnią liczbę operacji dominujących w zależności od parametrów dla następującej procedury: {sx>0, sy>0, skala>1} procedure ENLARGE (sx, sy, skala : integer); var I, j, k , l : integer; begin i:=sx-1; while (i>=0) do j:=sy-1 while (j>=0) do if ( GetPixel(i,j)=White ) then for k:=0 to skala-1 do for l:=0 to skala-1 do Putpixel (skala*i+k, skala*j+1, White); endfor; endfor: endif: PutPixel (I, j, Black); J:=j-1; endwhile; I:=i-1; endwhile; end; Założyć, że operacjami dominującymi są odwołania do biblioteki graficznej, tzn. wywołania funkcji GetPixel i procedury PutPixel. Założyć, że funkcja GetPixel zwraca tylko wartości While i Black z jednakowym prawdopodobieństwem.