Data «яблоки», 500, 200 data «яблоки», 2500, 100

Data «огурцы», 400, 250 data «огурцы», 2000, 150

Data «арбузы», 200, 600 data «арбузы», 1200, 200

Data «персик», 800, 100 data «персик», 2000, 0

Data «», 0, 0 data «», 0, 0

Приведем теперь алгоритм и программу решения поставленной задачи в соответствии с выбранным сценарием и рассмотренным выше способом упорядочения массивов методом «пузырька».

При составлении алгоритмов и программы решения этой задачи будем использовать принцип нисходящей разработки «сверху-вниз»: от основного алгоритма и основной части программы к алгоритмам и подпрограммам решения вспомогательных подзадач.

При решении сложных задач существенным становится органи­зация и представление данных: подбор массивов и переменных для размещения и обработки данных в памяти ЭВМ, а при выделении подпрограмм - процедуры доступа к этим данным.

Для размещения исходных данных о товарах в поставленной задаче примем пять массивов: 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],m[1: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. Конечным результатом выполнения данного вспомога­тельного алгоритма будет сумма

 

S_N = (с(1) - s(l))×(m(l) - р(1)) +... + (c(N) - s(N))×(m(N) - p(N)).

Доказательство проводится с помощью индуктивных рассужде­ний. Первое присваивание S:= 0 обеспечивает начальное значение суммы S₀ = 0.

О результатах k-го шага выполнения цикла можно сделать индук­тивное утверждение

 

S_k= S_k-1 + (c(k) - s(k))-(m(k) - p(k)) = (с(1) - s(l))×(m(l) - p(l)) +... + (c(k) - s(k))×(m(k) - p(k)).

 

Это утверждение доказывается с помощью математической индукции. На его основании можно сделать заключение о том, что конечным результатом выполнения цикла и алгоритма в целом будет сумма

 

S_N = (с(1) - s(l))×(m(l) - р(1)) +... + (c(N) - s(N))×(m(N) - p(N)).

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

Для сортировки данных воспользуемся алгоритмом упорядочения чисел по методу «пузырька», предполагая, что исходная и упорядоченная последовательность чисел r₁, r₂,..., 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)'

 

и последовательность индексов в массиве 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.

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

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

 

p₁' £ р₂' £ … £ p_N'

Доказательство. В соответствии с доказанной выше леммой 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]. Таким образом, очередные значения последовательности p₁', p₂',... будут равны:

 

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

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

 

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

 

p₁' £ р₂' £ … £ p_N'

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

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

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

товары:

Яблоки, 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. Что такое сложные алгоритмы и программы?

2. Что такое упорядоченная последовательность?

3. Что такое упорядочение методом «пузырька»?

4. Как доказывается правильность сложных программ?

5. Что такое разработка программ «сверху-вниз»?

 

Задания

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

а) подсчет планируемых доходов от продажи товаров;

б) подсчет начальной суммы вложений реализации товаров;

в) подсчет планируемой прибыли от продажи товаров;

г) подсчет текущей задолженности.

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

а) сортировка данных по начальному количеству;

б) сортировка данных по остаточному количеству;

в) сортировка данных по начальной стоимости;

г) сортировка данных по продажной цене.

3. Составьте алгоритм и программу сортировки данных о товарах по следующим признакам и приведите обоснование их правильности:

а) по доле планируемых доходов от реализации товаров;

б) по доле прибыли от реализации товаров;

в) по доле убыточности реализации товаров.