Rozważmy poniższy algorytm podobny do algorytmu 1.
Wejście:
k — liczba naturalna,
A[1...2k] — tablica liczb całkowitych.
Algorytm 2:
n ← 1
dla i = 1,2,…,k wykonuj
n ← 2⋅n
s ← 1
dopóki s < n wykonuj
j ← 1
dopóki j < n wykonuj
(*) jeżeli A[j]>A[j+1]
zamień(A[j],A[j+1])
j ← j + 1
s ← s + 1
zwróć A[1], A[2],…,A[n]
Uwaga: Funkcja zamień(A[j],A[j+1]) zamienia miejscami wartości A[j] oraz A[j+1].
Uzupełnij luki w poniższych zdaniach. Przyjmij n = 2k
oraz k > 1.
Po zakończeniu działania algorytmu 2 element A[i] jest .........................
niż element A[i+1] dla każdego i większego od .........................
oraz mniejszego od .........................
Wiersz (*) algorytmu 2 wykonywany będzie w przebiegu algorytmu
• ..................................... niż n razy,
• ..................................... niż n2
razy.
Ta odpowiedź nie jest sprawdzana automatycznie. Zobacz odpowiedź i oceń się samodzielnie.
poleca:
