|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
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],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' Что и требовалось доказать. Следовательно, весь комплекс алгоритмов и подпрограмм полностью соответствует поставленной задаче и гарантирует получение правильных результатов, при любых допустимых исходных данных. Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим образом, при указанных исходных данных дает следующие результаты: товары: Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.01 сек.) |