Товар цена остаток

Товар стоим кол-во

Нач

от k = 1 до N - 1 цикл

xmn:=х_k

............... { xmn = Min (х_k, ..., х_i) }

х¢_k = xmn_N

хmп¢ = х_k

кцикл { х_k' = Min (х_k, ..., х_N) }

кон { х₁' £ х₂' £ ... £ х_k' }

На первом шаге при k = 1 первый элемент последовательности

х₁' = Min (x₁, х₂, ..., х_N),

На втором шаге второй элемент последовательности

x₂' = Min (х₂, ..., х_N).

В силу свойств минимума последовательности чисел будем иметь

х₁' = Min(x₁, x₂, ..., х_N) = min (x₁, Min (х2, ..., хN) £ (Min (х2, ..., хN) = x₂'.

Таким образом, при k = 2 результатом станут значения х₁' и x₂', такие что

х₁' £ x₂'

На третьем шаге выполнения основного цикла результатом станет

х₃ = Мin(х₃, ..., х_N).

Опять же в силу свойств минимума последовательности имеем

х₂' = Min (х₂, х₃, ..., х_N) = min (x₂, Min (x₃, ..., х_N)) £ Min (x₃, ..., х_N) = x₃'.

Таким образом, после третьего шага при k = 3 первые три значе­ния последовательности х₁', x₂', x₃' будут удовлетворять условию

х₁'£ x₂'£ x₃'

Из приведенных выкладок можно сделать индуктивное предположение, что на каждом очередном k-м шаге выполнения основного цикла первые k членов последовательности х₁', x₂', .... х_k' будут удов­летворять условию

х₁'£ x₂'£ … £ 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 и в силу индуктивного предположения получаем, что

x₁' £ х₂' £ ... £ х_k' £ x_k+'₁.

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

Осталось уточнить результаты выполнения последнего шага цикла при k = N - 1. В силу леммы 2 результатом будет значение

x_N-'₁ = Min (x_N-1, x_N) £ х_N'.

Таким образом, после N - 1 шагов выполнения основного цикла для последовательности в целом будут выполнены соотношения упорядоченности

x₁' £ x₂' £ ... £ х_N' .

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

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

Данные о товарах представлены двумя таблицами:

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

Постановка задачиСценарий

Сортировка товаров по остатку.

Дано: товары:

D = (d₁, d₂, .... d_N) - данные товара, <товар₁> <s₁> < m ₁> *

d = (товар, s, m), ...... ... ...

s - стоимость, m - кол-во, остатки:

R = (r₁, r₂, ..., r_N) - данные об остатках, <товap₁> <c₁> < р₁> *

г = (товар, с, р), ...... ... ...

с - цена, р - остаток.

Треб.: S - сумма выручки, выручка = <S>

R' = (r₁', ..., r_N') - упорядоченные данные, сортировка:

Где: <товар₁'> <с₁'> <р₁'> *

S = (c₁-s₁)×(m₁-p₁) +...+ (с_N-s_N)×(m_N-р_N), ............

р₁' £ р₂' £ ... £ р_N',

р_k' = р_i для k = 1 ... N и i = 1 ... N.

При: N > 0.

Для представления исходных данных в программе примем опера­торы data:

tovs: 'товары: osts: 'остатки:

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'

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

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

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

товары: