Фамилия должность зарплата
Иванов | директор | |
Петров | менеджер | |
Сидорова | секретарь |
Приведем постановку задачи и описание метода вычисления средней зарплаты.
Постановка задачиМетод расчета
Определение средней зарплаты.
Дано:
(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 := 0S0 = 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>
Кон
Сравнение результатов выполнения программы с описанием метода вычисления и выбранного сценария подтверждает их соответствие друг другу и как следствие правильности выбранного метода вычислений - правильность составленных алгоритма и программы расчета средней зарплаты.
В качестве второго примера рассмотрим решение типичной задачи подсчета суммарной стоимости товаров с выделением товаров наибольшей стоимости. Допустим, что исходные данные представлены следующей таблицей:
Товар цена кол-во
яблоки | ||
бананы | ||
арбузы |
Приведем постановку задачи и описание способа ее решения.
Постановка задачиСпособ решения
Определение суммарной
и максимальной стоимости товаров.
Дано:
(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>
Кон
Из расмотренных примеров следует, что правильность алгоритмов и программ зависит прежде всего от правильности выбранных методов решения. Составление соответствующих им алгоритмов и программ сводится к решению технических проблем.
Можно утверждать, что правильные алгоритмы и программы - это корректная реализацияправильных методов решения. Ошибки в выбранных методах решения носят не алгоритмический, а принципиальный характер и их следует искать не с помощью отладки программ на ЭВМ, а исследованием самих методов.
Рассмотрим самую популярную экономическую задачу -расчет семейного бюджета в целях анализа достатка семьи. Напомним, что достаток семьи - это остаток от разности доходов и расходов:
достаток = доходы - расходы.
Допустим, что данные о семейном бюджете представлены двумя таблицами: - таблицей доходов и таблицей расходов:
Доходы Расходы
папа | питание | ||
мама | одежда | ||
брат | транспорт | ||
я | отдых | ||
разное |
Приведем точную постановку задачи и опишем метод ее решения.
Постановка задачиМетод решения
Определение достатка семьи.
Дано: 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 := 0Sr = 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, М и названия товаров заданы). Каждый товар характеризуется наличием или отсутствием его в магазине, а также наличием или отсутствием на него спроса покупателей. Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магазинов) товаров.
Дата добавления: 2016-04-06; просмотров: 684;