Navigation bar
  Print document Start Previous page
 96 of 144 
Next page End  

96
перестановка2:     
1, 3,   9,  7, 4.
перестановка3:     
1, 3,   4,  7, 9.    
упорядочено.
Приведем точную математическую постановку задачи. 
Постановка задачи
Упорядочение последовательности чисел. 
Дано: x1, х2, ..., х
N
- исходные числа. 
Треб.: x1', x2', ..., х
N
' - упорядоченные числа. 
Где:   х1'
х2'
...
х
N
'. 
При:   N > 0.
Упорядочение чисел по методу «пузырька» в общей форме имеет вид:
Способ «упорядочение чисел»
нач 
от k=1 до N-1 цикл 
хтп := xk 
imn := k
от i=k+1 до N цикл 
если xi < хтп то 
хтп := xi 
imn : =
кесли
кцикл                    
xmn = Min (х
k
, ..., х
N
xk' = хтп 
ximn ' = xk
кцикл                           
х
k
= Min (х
k
, ..., х
N
)
кон                               
x1 < х2 < ... < х
k
Приведенный алгоритм можно рассматривать как алгоритм, сложенный из нескольких
фрагментов - вспомогательных алгоритмов, решающих определенные подзадачи.
Первый фрагмент (внутренний цикл) решает подзадачу нахождения минимального значе-
ния в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального
значения на k-e место в массиве.
Лемма 1. Для вспомогательного алгоритма
алг «поиск минимума» 
нач 
хтп := xk 
imn := k 
от i = k + 1 до N цикл 
если x
i
< хтп то
хтп := x
i
 
imn := i 
кесли
кцикл                     
{ xmn = Min (х
k
, ..., х1) } 
кон
конечным результатом вычислений будет значение 
xmn = Min (х
k
, ..., х
N
).
Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает
xmn
k
= x
k
.
Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:
   
      x
k+1
при x
k+1
< xmn
k
,
xmn
k+l
      xmn
k
при x
k+1
xmn
k
На втором шаге цикла будет получен минимум первых трех чисел:
xmn
k+2
= min (x
k+2
, min (х
k+1
, х
k
)) = Min (х
k+2
, х
k+1
, х
k
).
Сайт создан в системе uCoz