 |
 |
 |
 |
|
 |
 |
130
В качестве иллюстрации рассмотрим две задачи, которые можно отнести к сложным проблемам
обработки данных. Для каждой из этих задач приведем спецификации, алгоритмы и доказательства
правильности.
Первая задача: упорядочение массивов данных. Пример, для чисел 3, 7, 9, 1,
4 упорядоченная
последовательность имеет вид: 1, 3, 4, 7, 9.
Существует несколько способов и методов упорядочения массивов и последовательностей.
Простейший из них называется методом «пузырька».
Метод «пузырька» состоит в нахождении в массиве наименьшего числа и перестановке его на
первое место. Это как бы «пузырек», поднимающийся к началу массива. Затем в остатке массива нахо-
дится наименьшее число, которое перемещается на второе место, и так далее - до исчерпания всего
массива.
Для рассматриваемых чисел метод «пузырька» дает следующие перестановки:
исходные числа:
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