Информатика
Решение сложных задач - часть 2
исходные числа: 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
кесли
кцикл
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 будет получен минимум первых двух чисел:
xmnk+l =
