Приведем теперь алгоритм и программу решения поставленной задачи в соответствии с выбранным сценарием и рассмотренным выше способом упорядочения массивов методом «пузырька».
При составлении алгоритмов и программы решения этой задачи будем использовать принцип нисходящей разработки «сверху-вниз»: от основного алгоритма и основной части программы к алгоритмам и подпрограммам решения вспомогательных подзадач.
При решении сложных задач существенным становится организация и представление данных: подбор массивов и переменных для размещения и обработки данных в памяти ЭВМ, а при выделении подпрограмм - процедуры доступа к этим данным.
Для размещения исходных данных о товарах в поставленной задаче примем пять массивов: tv(l:N), s(l:N), m(l:N), с (1:N), p(l:N). Общий размер этих массивов ограничим числом N = 200, которое явно выделено в описании массивов с тем, чтобы в дальнейшем его можно было увеличить для большего количества данных без других изменений программы.
алг «выручка и остатки товаров» 'выручка и остатки товаров
N = 100 N = 100
массив tv[1:N],s[1:N],m1l:N] dim tv$(N),s(N),m(N)
массив L[1:N],c[1:N],p[1:N] dim L(N),c(N),p(N)
нач сls
вывод («товары:»)? «товары:»
данные-товаров gosub tovar 'товары
вывод («остатки:»)? «остатки:»
данные-остатков gosub ostatok 'остатки
вывод («-----»)? «-----»
подсчет-выручки gosub vyruch 'выручка
вывод («выручка», S)? «выручка=»;S
вывод («сортировка:»)? «сортировка:»
сортировка-товаров gosub sortdan 'сортировка
кон end
По приведенному алгоритму и основной части программы видно, что последовательность ввода-вывода данных о товарах и результатов обработки полностью соответствует выбранному сценарию. Загрузку исходных данных в выбранные массивы в соответствии с принятым представлением выполнят два следующих вспомогательных алгоритма
алг «данные товаров» tovar: 'данные товаров
нач '
загрузка-товаров restore tovs
от k = 1 до N цикл for k = 1 to N
чmeнue(tv(k),s(k),m(k)) read tv$(k),s(k),m(k)
при tv(k) = «» то if tv$(k) = «» then exit for
вывод (tv(k),s(k),m(k))? tv$(k);s(k);m(k)
кцикл next k
если k< Nmo N:= k-1 if k < N then N = k-1
кон return
Последний условный оператор изменяет верхнюю границу N массивов в том случае, если фактическое число данных меньше числа мест в массивах, размещенных в памяти компьютера.
алг «данные остатков» ostatok: 'данные остатков
нач '
загрузка-остатков restore osts
от k = 1 до N цикл for k = 1 to N
чmeнue(tv(k),c(k),p(k)) read tv$(k),c(k),p(k)
при tv(k) = «» выход if tv$(k) = «» then exit for
вывод (tv(k),c(k),p(k))? tv$(k);c(k);p(k)
кцикл next k
если k < N mo N:= k-1 if k < N then N = k-1
кон return
Подсчет выручки в соответствии с постановкой задачи по данным, введенным в эти массивы, выполнят следующие вспомогательный алгоритм и подпрограмма:
алг «подсчет выручки» vyruch: 'подсчет выручки
нач '
S:= 0 S = 0
от k = 1 до N цикл for k = 1 to N
S:= S+(c(k)-s(k)) *(m(k)-p(k)) S = S+(c(k)-s(k))*(m(k)-p(k))
кцикл next k
кон return
Лемма 3. Конечным результатом выполнения данного вспомогательного алгоритма будет сумма
SN = (с(1) - s(l))×(m(l) - р(1)) +... + (c(N) - s(N))×(m(N) - p(N)).
Доказательство проводится с помощью индуктивных рассуждений. Первое присваивание S:= 0 обеспечивает начальное значение суммы S0 = 0.
О результатах k-го шага выполнения цикла можно сделать индуктивное утверждение
Sk= Sk-1 + (c(k) - s(k))-(m(k) - p(k)) = (с(1) - s(l))×(m(l) - p(l)) +... + (c(k) - s(k))×(m(k) - p(k)).
Это утверждение доказывается с помощью математической индукции. На его основании можно сделать заключение о том, что конечным результатом выполнения цикла и алгоритма в целом будет сумма
SN = (с(1) - s(l))×(m(l) - р(1)) +... + (c(N) - s(N))×(m(N) - p(N)).
Что и требовалось доказать.
Для сортировки данных воспользуемся алгоритмом упорядочения чисел по методу «пузырька», предполагая, что исходная и упорядоченная последовательность чисел r1, r2,..., rN будут записаны в массиве 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)'
и последовательность индексов в массиве L[1:N], удовлетворяющих условиям
x(k)' = p(L(k)) для всех k = 1,.... N.
Доказательство. Первое утверждение об упорядоченности значений х(1)' £ х(2)' £... £ x(N)' массива x[l:N] по завершении алгоритма следует из доказательства правильности алгоритма упорядочения последовательности чисел. Для доказательства второго утверждения рассмотрим результаты перестановок значений элементов:
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 = L(imn)
x(k):= xmn x(k)' = xmn = x(imn)
Перед началом выполнения алгоритма упорядочения массива в алгоритме сортировки данных массив индексов L[1:N] и упорядочиваемый массив x[l:N] получают значения, удовлетворяющие следующим соотношениям:
х(i)' = P(L(i) для всех i = 1,..., N.
Покажем, что эти соотношения сохраняются после каждого шага цикла. Действительно, на каждом очередном k-м шаге цикла будут получены следующие результаты:
Imn = L(imn)
xmn = x(imn) == p(L(imn))
L(imn)' = L(k)
x(imn)' = x(k) = p(L(k)) = p(L(imn)')
L(k)' = Imn = L(imn)
x(k)' = xmn = x(imn) = p(L(imn)) = p(L(k)')
Следовательно, после каждого шага цикла для переставленных элементов массивов сохраняются соотношения
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'
Что и требовалось доказать.
Следовательно, весь комплекс алгоритмов и подпрограмм полностью соответствует поставленной задаче и гарантирует получение правильных результатов, при любых допустимых исходных данных.
Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим образом, при указанных исходных данных дает следующие результаты:
товары: