Решение прикладных задач
Решение задач на ЭВМ является одним из основных источников для создания алгоритмов и программ. Экономические задачи и проблемы обработки данных - один из важнейших классов прикладных задач, решаемых на ЭВМ.
Применение компьютеров для решения экономических задач существенно упрощает работу по подготовке и обработке данных. Одной из причин в использовании ЭВМ для решения этих задач - снижение трудоемкости и уменьшение числа ошибок при обработке данных.
Для решения многих экономических задач на ЭВМ используются электронные таблицы и специальные пакеты программ. Однако решение любых новых прикладных задач на ЭВМ предполагает необходимость создания новых алгоритмов и программ на основе определенных математических методов решения и обработки данных.
Особое значение правильность алгоритмов
имеет для экономических задач, поскольку ошибки в их решении могут дорого стоить. Неправильные экономические расчеты могут нанести материальный ущерб или даже привести к банкротству целую организацию.
Для предотвращения ошибок можно использовать систематические методы конструирования алгоритмов и программ с одновременным анализом их правильности. Последовательное применение этих методов обеспечивает составление прикладных алгоритмов и программ с гарантиями их правильности.
Общий принцип систематического подхода к составлению алгоритмов и программ заключается в последовательной разработке спецификаций: постановок задач, способов и методов их решения, а также сценариев работы в процессе решения задач.
Составление программ
задача ® способы
¯ ¯
постановка ® методы
¯ ¯
сценарий ® алгоритмы
¯ ¯
ЭВМ ¬ программы
Систематический анализ правильности алгоритмов и программ сводится к сопоставлению этих спецификаций друг с другом: программ - с алгоритмами, алгоритмов - со сценариями и описаниями методов, а методы решения - с постановками задач.
Анализ правильности
задача ¬ способ
постановка ¬ методы
сценарий ¬ алгоритмы
ЭВМ ® программы
Приведем примеры систематической разработки алгоритмов и программ решения экономических задач на ЭВМ с обоснованием их правильности. Главной особенностью этих задач является то, что все они относятся к задачам обработки данных.
Первый пример экономической задачи - определение средней зарплаты в организации. Допустим, что данные о зарплате представлены таблицей:
фамилия должность зарплата
|
Иванов |
директор |
300000 |
|
Петров |
менеджер |
240000 |
|
Сидорова |
секретарь |
120000 |
Приведем постановку задачи и описание метода вычисления средней зарплаты.
Постановка задачи Метод расчета
Определение средней зарплаты.
Дано:
(D1, ..., DN) - данные о сотрудниках,
где D = [Fam, Т, Z] - состав данных,
должность, S0
= 0
Треб: Zcpeдн - средняя зарплата. [k=(l...N)]
Где:
Zcpeдн = (Z1 + Z2
+ ... + ZN)/N. Zcpeдн = SN
При: N > 0.
Прежде всего убедимся, что выбранный метод вычисления правилен. Для этого воспользуемся индукцией. Рассмотрим результаты вычислений на первых трех шагах.
При k = 1 результат
S1=S0(1 - 1)/1 +Z1/1 =Z1/1.
При k = 2 результат
S2
= S1(2 - 1)/2 + Z2/2 = Z1/2 + Z2/2.
При k = 3 результат
S3 = S2(3 - 1)/3 + Z3/3 = (Z1 + Z2)/3 + Z3/3.
По этим трем результатам можно утверждать, что в общем случае результатом k-го шага вычислений будет
Sk
= (Z1 + ... + Zk-1)/k.
Справедливость этого утверждения можно доказать по индукции. Допустим, что оно справедливо для (k-l)-ro шага:
Sk-1
= (Z1 + ... + Zk-1)/(k-l).
Тогда из описания метода вычислений очередное k-e значение будет равно
Sk = Sk-1(k-l)/k + Zk/k =
= (Z1 + ... + Zk-1)/(k-l)×(k-l)/k + Zk/k = (Z1 + ... + Zk-1)/k + Zk/k.
Что и требовалось показать. Следовательно, в силу математической индукции это утверждение справедливо для всех k = 1, 2,..., N. В частности, для последнего шага вычислений при k = N конечным результатом будет
SN
= (Z1 + ... + ZN-1)/N + ZN/N = (Z1 + ... + ZN)/N.
Таким образом, выбранный метод дает правильный результат для любой последовательности величин Z1, Z2, ..., ZN.
Для конструирования алгоритма и программы решения задачи на ЭВМ примем следующий сценарий, а для представления данных воспользуемся операторами data.
Сценарий Представление данных
список сотрудников: dan: 'данные сотрудников
{<фам> <должн> <з/плата>}* data «Иванов»,«директор», 300000
{...................} data «Петров»,«менеджер», 240000
средняя з/плата= <Zcpeд> data «Сидорова»,«секретарь», 120000
data «», «», 0
При выбранных сценарии, методе расчета и представлении данных систематическое конструирование приводит к следующим алгоритму и программе.
Алгоритм Программа
алг «средняя зарплата» ' средняя зарплата
нач cls
вывод («список сотрудников:») ? «список сотрудников:»
s
:= 0: k := 0 s = 0: k = 0
цикл do
чтение (fam$, dl$, zpl) read fam$, dl$, zpl
при fam$ = «» выход if fam$ = «» then exit do
вывод (fam$, dl$, z) ? fam$; dl$; z
k
:= k + 1 k = k + 1
s
:= s*(k - 1)/k + z/k s = s*(k - 1)/k + z/k
кцикл loop
zsr = s zsr = s
вывод («средняя 3/nлama=»,zsr) ? «средняя з/плата=»; zsr
кон end
Для полного обоснования отсутствия ошибок в приведенном алгоритме и программе приведем описание результатов их выполнения на ЭВМ.
Алгоритм Результаты выполнения
алг «средняя зарплата»
нач
s := 0: k := 0 S0 = 0 [ k = 0 ]
цикл
чтение (fam$, dl$, z)
при fam$ = «» выход
вывод (fam$, dl$, z) <famk> <dlk> <zk> }*
s := s*(k - 1)/k + z/k sk = sk - 1×(k - 1)/k + zk/k
кцикл
zsr
= s zsr = sN
вывод («средняя з/nлama=»,zsr) средняя з/плата= <zsr>
кон
Сравнение результатов выполнения программы с описанием метода вычисления и выбранного сценария подтверждает их соответствие друг другу и как следствие правильности выбранного метода вычислений - правильность составленных алгоритма и программы расчета средней зарплаты.
В качестве второго примера рассмотрим решение типичной задачи подсчета суммарной стоимости товаров с выделением товаров наибольшей стоимости. Допустим, что исходные данные представлены следующей таблицей:
товар цена кол-во
|
яблоки |
8000 |
3 |
|
бананы |
4000 |
2 |
|
арбузы |
1000 |
20 |
Приведем постановку задачи и описание способа ее решения.
Постановка задачи Способ решения
Определение суммарной
и максимальной стоимости товаров.
Дано:
(D1, ...,
DN) - данные о товарах,
где D = [Tov, C, M] - состав данных, s0 = 0
Tov - товар, С - цена товара, от k = 1 до N цикл
М - количество товара, sk
= sk-1 + СkМk
Треб: если k = 1 то
Sum - суммарная стоимость товаров, mах1
= С11М11
TovMax - товар максимальной инеc СkМk > mахk-1 то
стоимости.
Где: mахk
= СkМk
Sum = C1M1 + С2М2
+ ... + СNМN, все
TovMax: C×M = Мах(С1М1, ... ,СNМN). кцикл
При:
N > 0.
Прежде чем приступить к составлению алгоритмов и программ, убедимся в правильности выбранного способа решения. Для этого проверим результаты на первых шагах, в середине и в конце вычислений. На первом шаге при k = 1 результат
s1
= s0 + С1М1 = С1M1,
max1
= С1М1.
На втором шаге вычислений будут получены следующие значения:
s2
= s1 + С2М2 = C1M1
+ С2М2,
max1, при С2М2
£ max1 = Мах(mах1, С2М2).
На третьем и последующих шагах в общем случае будут получаться результаты:
sk
= sk-1 + CkMk = C1M1 + … + CkMk,
maxk
= Max(maxk-1, СkМk) = Мах(С1М1, ..., СkМk).
Для доказательства этих утверждений необходимо предположить, что они выполняются для случая k-1:
sk-1
=C1M1 +...+ Ck-1Mk-1,
maxk-1
= Max (C1M1, …,Ck-1Mk-1),
и подставить эти выражения в соотношения для sk и mахk:
sk
= sk-1 + CkMk = C1M1 + … Ck-1Mk-1 + CkMk,
maxk
= Max(maxk-1, СkМk) = Мах(С1М1, ..., СkМk).
В силу математической индукции эти утверждения верны для всех k = 1, 2, ..., N. Поэтому на последнем шаге вычислений при k = N будут получены окончательные результаты:
sN
= sN-1 + CNMN = C1M1 + … + CNMN,
maxN
= Max(maxN-1, СNМN) = Max(C1M1, ... , СNМN).
Что и требовалось в постановке задачи. Следовательно, выбранный способ решения поставленной задачи правилен и на его основе можно приступать к составлению соответствующих алгоритма и программы.
Для систематичности разработки примем следующий сценарий диалога и представление исходных данных в операторах data.
Сценарий Представление данных
список товаров
<тов1> <с1> <т1> * dan: 'сведения о товарах
… .... ... data яблоки, 8000, 3
сумма = <Sum> data бананы, 4000, 2
Максимум data арбузы, 1000, 20
<товар> <стоим> data «», 0, 0
Приведем алгоритм и программу решения поставленной задачи в соответствии с выбранным сценарием и представлением данных.
Алгоритм Программа
алг «сумма и максимум» '
сумма и максимум
нач сls
вывод («список товаров») ? «список товаров»
вывод («товар цена кол-во») ? «товар цена кол-во»
s := 0; k = 0 s = 0: k = 0
цикл do
чтение (тов, с, т) read tv$, с, m
при тов = «» выход if tv$ = «» then exit do
k := k + 1 k = k + 1
вывод (тов, с, т) ? fv$; с; m
s :=s + cm s= s + c(m
если k = 1 то if k = 1 then
max
:= c×m max = c×m
ToвMax
:= тов ТМ$ = tv$
инес c(m > max то elseif c(m > max then
max
:= c×m max = c×m
ToвMax := тов TM = tv$
кесли end if
кцикл loop
вывод («cyммa=»,s) ? «cyммa=»,s
вывод («Максимум») ? «Максимум»
вывод (ToвMax, max) ? TM$, max
кон end
Сравнение результатов выполнения представленных алгоритма и программы с описанием выбранного способа решения показывает их полное соответствие друг другу.
Алгоритм Результаты выполнения
алг «сумма и максимум»
нач
вывод («список товаров») список товаров
вывод («товар цена кол-во») товар цена кол-во
цикл
чтение (тов, с, т)
при тов = «» выход
k:=k+1 [k= 1,2,...,N]
вывод (тов, с, т) { <тов> <с> <m> }*
s := s + с×т sk = sk-1 + ck×mk
если k =1 то при k = 1
тах
:= c×m max1 = c1×m1,
ТовМах
:= тов ToвMaх1 = тов1
uнес c×m > тах то при сk×mk
> mах
тах
:= с×т mахk
= сk×mk
ТовМах
:= тов ТовМахk
= товk
кесли
кцикл
вывод («сумма=», s) cуммa = <sN>
вывод («Максимум») Максимум
вывод (ТовМах, тах) <ToвMaxN> <maxN>
кон
Из расмотренных примеров следует, что правильность алгоритмов и программ зависит прежде всего от правильности выбранных методов решения. Составление соответствующих им алгоритмов и программ сводится к решению технических проблем.
Можно утверждать, что правильные алгоритмы и программы - это корректная реализация правильных методов решения. Ошибки в выбранных методах решения носят не алгоритмический, а принципиальный характер и их следует искать не с помощью отладки программ на ЭВМ, а исследованием самих методов.
Рассмотрим самую популярную экономическую задачу -
расчет семейного бюджета в целях анализа достатка семьи. Напомним, что достаток семьи - это остаток от разности доходов и расходов:
достаток = доходы - расходы.
Допустим, что данные о семейном бюджете представлены двумя таблицами: - таблицей доходов и таблицей расходов:
Доходы Расходы
|
папа |
3000 |
питание |
200 |
|
мама |
1200 |
одежда |
120 |
|
брат |
2000 |
транспорт |
60 |
|
я |
600 |
отдых |
30 |
|
разное |
50 |
Приведем точную постановку задачи и опишем метод ее решения.
Постановка задачи Метод решения
Дано: S = Sd - Sr
D = (дох1, ..., дох N) - доходы, Sd = сN
где дох = (имя, d), [k = (1...N)]
расх = (стат, r). с0
= 0
Треб.:
S - достаток семьи. Sr = bM
S = Sum (d1, …, dN) - Sum (r1, .... rM). [i =
(1 ... M)]
При: N, M > 0. b0
= 0
Для решения задачи на ЭВМ в качестве представления данных примем два списка операторов data, а для организации вывода результирующих данных - следующий сценарий.
Сценарий Представление данных
Подсчет достатка 'doch: ' доходы
<имяk>
<dk> * data «мама», 120000
... ... data «брат», 200000
Доходов = <Sd> data «», 0
Расходы семьи:
... ... data «питание», 200000
Расходов = <Sd> data «одежда», 120000
Достаток = <S> data «транспорт», 60000
data «», 0
Приведем соответствующие этому сценарию и выбранному методу представления данных алгоритмы и программу на Бейсике:
алг «достаток семьи» 'достаток семьи
нач cls
вывод («Подсчет достатка»)
? «Подсчет достатка»
вывод («Доходы семьи:») ? «Доходы семьи:»
подсчет_доходов gosub dchs 'доходы
вывод («Доходов=», Sd) ? «Доходов=», Sd
вывод («Расходы семьи:») ? «Расходы семьи:»
подсчет_расходов gosub rashs 'расходы
вывод («Расходов =», Sr) ? «Расходов=», Sr
S
:= Sd - Sr S = Sd - Sr
вывод («Достаток=», S) ? «Достаток=», S
кон end
алг «подсчет доходов» dchs: 'подсчет доходов»
нач '
загрузка_доходов restore doch 'доходы
Sd := 0 Sd = 0
цикл do
чтение (имя, d) read namS, d
при имя
= «» вых if nam$ = «» then exit do
вывод (имя, d) ? nam$, d
Sd =
Sd + d Sd = Sd + d
кцикл loop
кон return
алг «подсчет расходов» rashs ' подсчет расходов
нач '
загрузка_расходов restore rach 'расходы
Sr := 0 Sr = 0
цикл do
чтение (стат, r) read stat$, r
при стат
= «» вых if st$ = «» then exit do
вывод (стат, r) ? st$, r
Sr =
Sr + r Sr = Sr + r
кцикл loop
кон return
Правильность составленного комплекса алгоритмов и программы расчета достатка семьи можно проверить по описанию результатов их выполнения:
«достаток семьи» «подсчет доходов» «подсчет расходов»
Подсчет достатка
Доходы семьи: Sd0
= 0 [k = 0] Sr0
= 0 [i = 0]
<подсчет_доходов>
Расходы семьи: [k =(1...N)] [i =(1...M)]
<подсчет_расходов> <имяk> <dk> <стат1> <r1>
Расходов = < Sr> Sdk
= Sd/k-l/+dk Sri
== Sri-1 + ri
{ S = Sd - Sr
Достаток = <S>
Для обоснования правильности всего комплекса алгоритмов и программы в целом необходимо показать правильность каждого из вспомогательных алгоритмов: «подсчет доходов» и «подсчет расходов».
Для первого алгоритма для первых шагов вычисления получаем:
Sd0 = 0,
Sd1 = Sd0 + d1 = d1,
Sd2 = Sd1
+ d2 = d1
+ d2.
Для последующих шагов можно заключить, что
Sdk = Sdk-1 + dk = d1 + d2 + ... + dk-1 + dk.
Это доказывается с помощью математической индукции. В силу этого утверждения окончательным результатом вычислений станет сумма доходов
SdN
= d1 + d2
+ ... + dN-1 + dN.
Следовательно, алгоритм подсчета доходов - правильный.
Для второго алгоритма подсчета расходов получаются аналогичные оценки:
Sr0
= 0,
Sr1 = Sr0 + r1
= r1,
Sr2 = Sr1
+ r2 = r1 + r2
и для последующих шагов вычислений:
Sri
= Sri-1 + ri = r1
+ r2 +... + ri-1+ ri.
Это доказывается также с помощью математической индукции. На основании этого утверждения можно сделать заключение о конечном результате выполнения алгоритма:
SrM = r1 + r2 + ... + rM-1+ rM.
Следовательно, алгоритм подсчет расходов правильный. Но в основном алгоритме содержится единственная расчетная формула
S = Sd - Sr.
В силу доказанных утверждений о результатах выполнения алгоритмов «подсчета доходов» и «подсчета расходов» конечным результатом вычислений станет величина
S = Sd - Sr = (d1
+ d2 + ... + dN) - (r1 + r2 + ... + rM).
Что и требовалось доказать. Следовательно, весь комплекс алгоритмов и программа в целом правильны.
В о п р о с ы
1. К чему приводят ошибки в экономических программах?
2. Кто отвечает за ошибки в экономических программах?
3. Что дают постановки задач?
4. Зачем нужны описания методов?
5. Как проверяется правильность методов?
6. Зачем нужны описания результатов?
З а д а ч и
1. В магазине имеются товары различных наименований. В течение дня каждый из М покупателей (М - заданное число) сообщил о своем намерении приобрести определенное количество товара одного из наименований. Требуется определить суммарный спрос на товары каждого наименования, расположив товары в порядке убывания дневного спроса на них.
2. Каждый из N магазинов в течение месяца работал D дней (N и D - заданные числа 1, 2, ....
N). Известна прибыль каждого магазина в каждый день его работы. Необходимо напечатать упорядоченный по месячным доходам список названий магазинов, имеющих прибыль в пересчете на один день работы выше средней дневной прибыли по всем магазинам.
3. Каждое из N предприятий города выпускает М одинаковых наименований продукции (N и М, наименования продукции и названия предприятий известны). Заданы объем выпуска и стоимость единицы продукции каждого вида для каждого из предприятий. Необходимо для каждого вида продукции определить предприятия, выпускающие наибольший объем этой продукции.
4. Из разных городов выбрали N семей (N - заданное число). Каждая семья характеризуется числом членов и доходом каждого из них. Для каждого города сформировать перечень семей с минимальным доходом в пересчете на отдельного члена семьи, указав порядковые номера семей из общего списка.
5. Ассортимент N магазинов состоит из М товаров (N, М и названия товаров заданы). Каждый товар характеризуется наличием или отсутствием его в магазине, а также наличием или отсутствием на него спроса покупателей. Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магазинов) товаров.
