Название: Информатика

Жанр: Информатика

Рейтинг:

Просмотров: 3382

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

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

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

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

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

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

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

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

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

¯                         ¯

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

¯                          ¯

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

¯                          ¯

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

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

Анализ правильности

задача                    ¬            способ

­                                  ­

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

­                                  ­

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

­                                  ­

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

Приведем примеры систематической разработки алгоритмов и программ решения экономических задач на ЭВМ с обоснованием их правильности. Главной особенностью этих задач является то, что все они относятся к задачам обработки данных.

Первый пример экономической задачи - определение средней зарплаты в организации. Допустим, что данные о зарплате представлены таблицей:

фамилия               должность            зарплата

Приведем постановку задачи и описание метода вычисления средней зарплаты.

Постановка задачи                                                             Метод расчета

Определение средней зарплаты.

Дано:

(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

средняя з/плата=                                                 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)                                              }*

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)      средняя з/плата=

кон

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

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

        товар                         цена                    кол-во

Приведем постановку задачи и описание способа ее решения.

Постановка задачи                                                             Способ решения

Определение суммарной

и максимальной стоимости товаров.

Дано:

(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

   сумма =                                                                                 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]

вывод (тов, с, т)                                                   { <тов> <с> }*

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 =

вывод («Максимум»)                                        Максимум

вывод (ТовМах, тах)                                          

кон

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

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

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

достаток = доходы - расходы.

Допустим, что данные о семейном бюджете представлены двумя таблицами: - таблицей доходов и таблицей расходов:

Доходы                                  Расходы   

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

Постановка задачи                                                             Метод решения

Определение достатка семьи.

Дано:                                                                                     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>     *                                                                              data «мама», 120000

                                ... ...                                                                                         data «брат», 200000

Доходов =                                                                    data «», 0

Расходы семьи:

   <статk>    *                                                                 rash: ' расходы

                                ... ...                                                                                         data «питание», 200000

Расходов =                                                                   data «одежда», 120000

Достаток =                                                                     data «транспорт», 60000