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

Кон

Кцикл

Кесли

Чтение (тов, с, т)

Цикл

Нач

вывод («список товаров») список товаров

вывод («товар цена кол-во») товар цена кол-во

s :=0; k = 0 s₀ =0 [k = 0]

при тов = «» выход

k:=k+1 [k= 1,2,...,N]

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

s := s + с×тs_k = s_k-1 + c_k×m_k

если k =1 то при k = 1

тах := c×m max₁ = c₁×m₁

ТовМах := тов ToвMaх₁ = тов₁

uнес c×m > тах то при с_k×m_k > mах

тах := с×т mах_k = с_k×m_k

ТовМах := тов ТовМах_k = тов_k

вывод («сумма=», s) cуммa = <sN>

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

вывод (ТовМах, тах) <ToвMaxN> <maxN>

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

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

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

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

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

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

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

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

Дано: S = Sd - Sr

D = (дох₁, ..., дох _N) - доходы, Sd = с_N

R = (расх₁, ..., расх_М) - расходы, с_k = с_k-1 + d_k

где дох = (имя, d), [k = (1...N)]

расх = (стат, r). с₀ = 0

Треб.: S - достаток семьи. Sr = b_M

Где: b_i = b_i-1 + r_i

S = Sum (d₁, …, d_N) - Sum (r₁, .... r_M). [i ⁼ (1 ... M)]

При: N, M > 0. b₀ = 0

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

СценарийПредставление данных

Подсчет достатка 'doch: ' доходы

Доходы семьи:data «папа», 300000

<имя_k> <d_k> *data «мама», 120000

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

Доходов = <Sd>data «», 0

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

<стат_k> <r_k>* 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 nam$, 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

Правильность составленного комплекса алгоритмов и программы расчета достатка семьи можно проверить по описанию результатов их выполнения:

«достаток семьи»«подсчет доходов»«подсчет расходов»

Подсчет достатка

Доходы семьи: Sd₀ = 0 [k = 0] Sr₀ = 0 [i = 0]

<подсчет_доходов>

Доходов = <Sd>

Расходы семьи: [k =(1...N)] [i =(1...M)]

<подсчет_расходов> <имя_k> <d_k> <стат_i> <r_i>

Расходов = < Sr> Sd_k = Sd_/k-l/+d_k Sr_i == Sr_i-1 + r_i

{ S = Sd - Sr

Достаток = <S>

Для обоснования правильности всего комплекса алгоритмов и программы в целом необходимо показать правильность каждого из вспомогательных алгоритмов: «подсчет доходов» и «подсчет расходов».

Для первого алгоритма для первых шагов вычисления получаем:

Sd₀ = 0,

Sd₁ = Sd₀ + d₁ = d₁,

Sd₂ = Sd₁ + d₂ = d₁ + d₂.

Для последующих шагов можно заключить, что

Sd_k = Sd_k-1 + d_k = d₁ + d₂ + ... + d_k-1 + d_k.

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

Sd_N = d₁ + d₂ + ... + d_N-1 + d_N.

Следовательно, алгоритм подсчета доходов правильный.

Для второго алгоритма подсчета расходов получаются аналогич­ные оценки:

Sr₀ = 0,

Sr₁ = Sr₀ + r₁ = r₁,

Sr₂ = Sr₁ + r₂ = r₁ + r₂,

и для последующих шагов вычислений:

Sr_i = Sr_i-1 + r_i = r₁ + r₂ +... + r_i-1+ r_i.

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

Sr_M = r₁ + r₂ + ... + r_M-1+ r_M.

Следовательно, алгоритм подсчет расходов правильный. Но в основном алгоритме содержится единственная расчетная формула

S = Sd - Sr.

В силу доказанных утверждений о результатах выполнения алго­ритмов «подсчета доходов» и «подсчета расходов» конечным резуль­татом вычислений станет величина

S = Sd - Sr = (d₁ + d₂ + ... + d_N) - (r₁ + r₂ + ... + r_M).

Что и требовалось доказать. Следовательно, весь комплекс алго­ритмов и программа в целом правильны.