Лекции по информатики 2 (стр. 30 из 43)

Таким образом, после третьего шага при 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' .

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

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

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

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

яблоки	500	200
огурцы	400	250
арбузы	200	600

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

яблоки	2500	100
огурцы	2000	150
арбузы	1200	200

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

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

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

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

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 = 100N = 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. Конечным результатом выполнения данного вспомогательного алгоритма будет сумма

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] получает следующий вид: