 |
 |
 |
 |
|
 |
 |
133
х1'
x2'
…
x
k
'.
Данное предположение доказывается с помощью математической индукции. На начальных шагах
при k = 2 и k = 3 оно уже показано. Покажем, что оно будет выполнено на (k + 1)-м шаге, если это усло-
вие выполнено на k-м. шаге.
В силу леммы 2 на k-м и (k + 1)-м шагах выполнения основного цикла промежуточными
результатами будут
х
k
' = Min(x
k
, x
k+1
, ..., х
N
),
х
k+1
' = Min (x
k+1
, ..., х
N
).
В силу свойств минимума последовательности чисел имеем
х
k
' = Min(x
k
, x
k+1
, ..., х
N
) = min (х
k
, Min (х
k+1
, ...,х
N
))
Min (x
k+1
, ..., х
N
) = х
k+1
'.
Таким образом, х
k
x
k+1
и в силу индуктивного предположения получаем, что
x1'
х2'
...
х
k
'
x
k+
'1.
Что и требовалось доказать.
Осталось уточнить результаты выполнения последнего шага цикла при k = N - 1. В силу леммы 2
результатом будет значение
x
N-
'1 = Min (x
N-1
, x
N
)
х
N
'.
Таким образом, после N - 1 шагов выполнения основного цикла для последовательности в целом
будут выполнены соотношения упорядоченности
x1'
x2'
...
х
N
'
.
Что и требовалось доказать. Следовательно, рассмотренный алгоритм упорядочения чисел
правильный в целом.
Применим теперь данный способ упорядочения для решения задачи сортировки. Рассмотрим
следующую задачу. Пусть дана некоторая партия товаров с заданной отпускной ценой, указана цена
товаров и известны остатки от их продажи. Требуется подсчитать выручку от продажи и отсортировать
товары по их остатку.
Данные о товарах представлены двумя таблицами:
товар
стоим кол-во
яблоки
500
200
огурцы
400
250
арбузы
200
600
товар
цена
остаток
яблоки
2500
100
огурцы
2000
150
арбузы
1200
200
Приведем точную постановку задачи и сценарий диалога с компьютером для решения поставленной
задачи.