Информатика


Решение сложных задач - часть 12


x(i)' = p(L(i)) для всех i = 1, ..., N.

Что и требовалось доказать.

Утверждение. Конечным результатом выполнения алгоритма и подпрограммы сортировки данных будет список данных, в котором последовательность значений р1', р2', ..., рN' будет упорядочена:

p1' £  р2' £  … £ pN'

Доказательство. В соответствии с доказанной выше леммой 4 зна­чения в массиве x[l:N] после выполнения алгоритма упорядочения чисел будут удовлетворять условиям

х(1)' £  х(2)' £  ... £  x(N)'.

В силу этой же леммы 4 значения индексов в массиве

L[1:N] будут удовлетворять соотношениям x[k]' = p(L(k)) для всех k = 1, ..., N.

Конечным результатом алгоритма сортировки данных является вывод значений из массива p[l:N] в соответствии с массивом индек­сов L[1:N]. Таким образом, очередные значения последовательности p1', p2',... будут равны:

р1' = p(L(l)) = х(1)',

p2'= р(L (2)) = х(2)'и т. д.

В силу упорядоченности значений х(1)', х(2)', ...,

x(N)' получаем, что значения выходной последовательности будут также упорядо­чены:

p1' £  р2' £  … £ pN'

Что и требовалось доказать.

Следовательно, весь комплекс алгоритмов и подпрограмм пол­ностью соответствует поставленной задаче и гарантирует получение правильных результатов, при любых допустимых исходных данных.

Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим образом, при указанных исходных данных дает следующие результаты:

товары:

яблоки, 500, 200

огурцы, 400, 250

арбузы, 200, 600

персики, 800, 100

остатки:

яблоки, 2500, 100

огурцы, 2000, 150

арбузы, 1200, 200

персики, 2000, 0

выручка = 880000

сортировка:

персики, 2000, 0

яблоки, 2500, 100

огурцы, 2000, 150

арбузы, 1200, 200

 

Таким образом, выполнение программы подтверждает правиль­ность составленного комплекса алгоритмов. Полное и исчерпыва­ющее обоснование их правильности приведено выше.

 

 

 

 

В о п р о с ы

 

1. Что такое сложные алгоритмы и программы?




Начало  Назад  Вперед



Книжный магазин