Информатика

         

Решение прикладных задач


Решение задач на ЭВМ является одним из основных источников для создания алгоритмов и программ. Экономические задачи и про­блемы обработки данных - один из важнейших классов приклад­ных задач, решаемых на ЭВМ.

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

Для решения многих экономических задач на ЭВМ используются электронные таблицы и специальные пакеты программ. Однако решение любых новых прикладных задач на ЭВМ предполагает необ­ходимость создания новых алгоритмов и программ на основе опре­деленных математических методов решения и обработки данных.

Особое значение правильность алгоритмов

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

Для предотвращения ошибок можно использовать систематические методы конструирования алгоритмов и программ с одновременным анализом их правильности. Последовательное применение этих методов обеспечивает составление прикладных алгоритмов и про­грамм с гарантиями их правильности.

Общий принцип систематического подхода к составлению алго­ритмов и программ заключается в последовательной разработке спецификаций: постановок задач, способов и методов их решения, а также сценариев работы в процессе решения задач.

Составление программ

задача          ®    способы

¯                         ¯

постановка ®   методы

¯                          ¯

сценарий         ®   алгоритмы



¯                          ¯

         ЭВМ       ¬   программы

Систематический анализ правильности алгоритмов и программ сводится к сопоставлению этих спецификаций друг с другом: про­грамм - с алгоритмами, алгоритмов - со сценариями и описаниями методов, а методы решения - с постановками задач.


 
 
 
 
Анализ правильности
задача                        ¬        способ
­                                  ­
постановка   ¬        методы
­                                  ­
сценарий        ¬        алгоритмы
­                                  ­
ЭВМ                ®        программы
Приведем примеры систематической разработки алгоритмов и программ решения экономических задач на ЭВМ с обоснованием их правильности. Главной особенностью этих задач является то, что все они относятся к задачам обработки данных.
Первый пример экономической задачи - определение средней зарплаты в организации. Допустим, что данные о зарплате представ­лены таблицей:
фамилия        должность     зарплата

Иванов
директор
300000
Петров
менеджер
240000
Сидорова
секретарь
120000

 
Приведем постановку задачи и описание метода вычисления сред­ней зарплаты.
Постановка задачи                                                    Метод расчета
Определение средней зарплаты.
Дано:
(D1, ..., DN) - данные о сотрудниках,
где D = [Fam, Т, Z] - состав данных,
Fam - фамилия, D1-
должность,                                 S0
= 0
Z - зарплата.                                                                    Sk = Sk-1*(k-l )/k + Zk/k
Треб: 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> }*
k:=k + 1                                                    [ k= (1...N) ]
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,
max2 =    С2М2, при С2М2 > max1      = Мах(mах1, С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
 
Сравнение результатов выполнения представленных алгоритма и программы с описанием выбранного способа решения показывает их полное соответствие друг другу.
 
 
 
 
 
 
 
 
 
 
 
Алгоритм                                                      Результаты выполнения
алг «сумма и максимум»
нач
вывод («список товаров»)                           список товаров
вывод («товар цена кол-во»)                              товар цена кол-во


s :=0; k = 0                                                 s0 =0 [k = 0]
цикл
чтение (тов, с, т)
при тов = «» выход
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
R = (расх1, ..., расхМ) - расходы,                                  сk = сk-1 + dk
где дох = (имя, d),                                                        [k = (1...N)]
расх = (стат, r).                                                           с0
= 0
Треб.:
S - достаток семьи.                                         Sr = bM
Где:                                                                                bi = bi-1 + ri
S = Sum (d1, …, dN) - Sum (r1, .... rM).                          [i =
(1 ... M)]
 При: N, M > 0.                                                          b0
= 0
Для решения задачи на ЭВМ в качестве представления данных примем два списка операторов data, а для организации вывода ре­зультирующих данных - следующий сценарий.
Сценарий                                                       Представление данных

Подсчет достатка                                                  'doch: ' доходы
Доходы семьи:                                                           data «папа», 300000
    <имяk>
<dk>    *                                                    data «мама», 120000
                        ... ...                                                                 data «брат», 200000
Доходов = <Sd>                                                        data «», 0
Расходы семьи:
   <статk> <rk>   *                                                    rash: ' расходы


                        ... ...                                                                 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]
<подсчет_доходов>
Доходов = <Sd>
Расходы семьи:                         [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, М и названия товаров заданы). Каждый товар характеризуется наличием или отсутст­вием его в магазине, а также наличием или отсутствием на него спроса покупателей. Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магазинов) товаров.

Содержание раздела