 |
 |
 |
 |
|
 |
 |
98
Из приведенных выкладок можно сделать индуктивное предположение, что на каждом оче-
редном k-м шаге выполнения основного цикла первые k членов последовательности х1', x2', .... х
k
'
будут удовлетворять условию
х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
Приведем точную постановку задачи и сценарий диалога с компьютером для решения по-
ставленной задачи.
Постановка задачи
Сценарий
Сортировка товаров по остатку.
Дано:
товары:
D = (d1, d2, .... d
N
)
- данные товара,
<товар1> <s1> < m 1> *
d = (товар, s, m),
...... ... ...
s
- стоимость, m - кол-во,
остатки:
R = (r1, r2, ..., r
N
)
- данные об остатках,
<товap1> <c1> < р1> *
г = (товар, с, р),
...... ... ...
с - цена, р - остаток.
Треб.: S - сумма выручки,
выручка = <S>
R' = (r1', ..., r
N
') - упорядоченные данные,
сортировка:
Где:
<товар1'> <с1'> <р1'> *