ASD ITN k1 05 2002 5

Zad. 8 Ile przestawień elementów wykona algorytm inserion-sort (sortowania przez wstawianie) podczas sortowania ciągu 1,2,3)15,10,9,8,7,6 w porządku niemalejącym. (Jedno przestawienie polega na zamianie pozycji jednego elementu)

AO '    ¹

Zad. 8 Ile przestawień elementów wykona algorytm selection-sort (sortowania przez wybór) podczas sortowania ciągu 6,7,8,9,10,1,2,3,4,5, w porządku niemalejącym. (Jedno przestawienie polega na zamianie miejscami dwóch elemeątów.)    -j o> G    9'

Odp.

Zad. 8 Ile przestawień element' nie) podczas sortowania ciąg_; przestawienie polega na zamia: Odp.:..............L

le

( 7J 9 ^ A i >

5 9 {o JS 7, >

'z. y °) ic 6 3- y' g

'Tyykona algorytm'inserion-sort (sortowania przez wstawia-2,4,6,8,10,1,3,5,7,9 w porządku niemalejącym. (Jedno >zycji jednego elementu) 7

■1

'La/

12 tv>

CrtA P

Zad 9. Dla każdej z wymienionych zależności, dotyczących poniższego algorytmu, ustal, czy jest czy nie jest prawdziwa

while i< (2n-l) do ..    ^

i;.U i* »    -

^od    (scAr z uyt

end    l

(a) Niezmiennikiem pętli „while” jest formuła:(i<(2n-1)) ^{J Ł}    prawda^ /(Taisz

-f- (b) Po wykonaniu pętli „while” (s = n² a i= 2n-l)    (jnawda / fałsz

(c) Jeżeli n jest liczbą parzystą, to po wykonaniu algorytmu wartością^y~gsf liczba^ nieparzysta.    /^/prawaay/Oałsz j<£=-

Zad 9. Następujący algorytm oblicza iloczyn skalarny dwóch wektorów R i Q. Zaznacz dla każdej formuły, czy jest czy nie jest niezmiennikiem pętli w tym algorytmie, begin    -A _o

i ~ 0; s := 0; $ = ^₀^v|^Qi . ... while i<n+l do _7__ >    s.- 27 » ■ A

s := s + P(i) * Q(i); i := i+1

<^rO

- I

Ł-“ J-A- ’ ' i<

s - y

od:

end    _ y

(a) s = Zⁱjlo(PO)*Qa))

~ (b) i<(n+l)/\s = P(i)*Q(i) (c) i < n+1

tak t rue^ tak

<3&*>