Информатика


              

Приведем точную математическую постановку задачи.


исходные числа:                    3, 7,   9, 1, 4.
перестановка1:                       1, 7,   9,  3, 4.
перестановка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 : = i
кесли
кцикл                                                    
            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 цикл
если
xi < хтп то
хтп
:= xi
imn := i
кесли
кцикл                                                         { xmn = Min (хk, ..., х1) }
кон
конечным результатом вычислений будет значение
xmn = Min (хk, ..., хN).
Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает
xmnk =
xk.
Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:
                  xk+1 при xk+1 < xmnk,
xmnk+l =

Содержание  Назад  Вперед