 |
 |
 |
 |
|
 |
 |
136
Это утверждение доказывается с помощью математической индукции. На его основании можно
сделать заключение о том, что конечным результатом выполнения цикла и алгоритма в целом будет
сумма
S
N
= (с(1) - s(l))
(m(l) - р(1)) + ... + (c(N) - s(N))
(m(N) - p(N)).
Что и требовалось доказать.
Для сортировки данных воспользуемся алгоритмом упорядочения чисел по методу «пузырька»,
предполагая, что исходная и упорядоченная последовательность чисел r1, r2, ..., r
N
будут записаны в мас-
сиве x[l:N].
Для формирования результирующих упорядоченных данных используется массив индексов L(1:N), в
котором будут записаны номера элементов исходной последовательности так, что x(k) = p(L(k)) для
всех k = 1, ..., N.
алг «сортировка данных»
sortdan: 'сортировка данных
массив x[1:N]
dim x(N)
нач
'
от k = 1 до N цикл
for k = 1 to N
L(k) = k
L(k) = k
x(k)=p(L(k))
x(k)=p(L(k))
кцикл
next k
сортировка-массива
gosub sortmas 'сортировка
от k = 1 до N цикл
for k = 1 to N
i := L(k)
i = L(k)
вывод (tv(i),c(i),p(i))
? tv$(i);c(i);p(i)
кцикл
next k
кон
return
Модификация алгоритма упорядочения чисел, размещаемых в массиве x[l:N], с учетом перестановок
значений в массиве индексов L[1:N] получает следующий вид:
алг «сортировка массива»
sortmas: 'сортировка массива
нач
'
от k = 1 до N-1 цикл
for k = 1 to N-1
xmn := x(k)
xmn = x(k)
imn := k
imn = k
от i = k + 1 до N цикл
for i = k + 1 to N
если x(i) < xmn то
if x(i) < xmn then
xmn := x(i)
xmn = x(i)
imn := i
imn = i
кесли
end if
кцикл
next i
Imn := L(imn)
Imn = L(imn)
xmn := x(imn)
xmn = x(imn)
L(imn) := L(k)
L(imn) = L(k)
x(imn) := x(k)
x(imn) = x(k)
L(k) :=Imn
L(k) = Imn
x(k) := xmn
x(k) = xmn
кцикл
next k
кон
return
Лемма 4. Результатами выполнения алгоритма сортировки массива будут последовательность чисел,
упорядоченная по возрастанию
х(1)'
х(2)'
...
x(N)'