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

папа		питание
мама		одежда
брат		транспорт
я		отдых
		разное

 

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

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

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

Дано: 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 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

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

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

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

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

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

Доходов = < Sd>

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

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

Расходов = < 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).

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