Лекции по информатики 2 (стр. 26 из 43)

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

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

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

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

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

папа	3000	питание	200
мама	1200	одежда	120
брат	2000	транспорт	60
я	600	отдых	30
разное	50

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

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

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

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

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

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

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

Доходы семьи: 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).

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

В о п р о с ы

1. К чему приводят ошибки в экономических программах?

2. Кто отвечает за ошибки в экономических программах?

3. Что дают постановки задач?

4. Зачем нужны описания методов?

5. Как проверяется правильность методов?

6. Зачем нужны описания результатов?

З а д а ч и

1. В магазине имеются товары различных наименований. В течение дня каждый из М покупателей (М - заданное число) сообщил о своем намерении приобрести определенное количество товара одного из наименований. Требуется определить суммарный спрос на товары каждого наименования, расположив товары в порядке убывания дневного спроса на них.

2. Каждый из N магазинов в течение месяца работал D дней (N и D - заданные числа 1, 2, .... N). Известна прибыль каждого магазина в каждый день его работы. Необходимо напечатать упорядоченный по месячным доходам список названий магазинов, имеющих прибыль в пересчете на один день работы выше средней дневной прибыли по всем магазинам.

3. Каждое из N предприятий города выпускает М одинаковых наименований продукции (N и М, наименования продукции и названия предприятий известны). Заданы объем выпуска и стоимость единицы продукции каждого вида для каждого из предприятий. Необходимо для каждого вида продукции определить предприятия, выпускающие наибольший объем этой продукции.

4. Из разных городов выбрали N семей (N - заданное число). Каждая семья характеризуется числом членов и доходом каждого изних.Для каждого города сформировать перечень семей с минимальным доходом в пересчете на отдельного члена семьи, указав порядковые номера семей из общего списка.

5. Ассортимент N магазинов состоит из М товаров (N, Ми названия товаров заданы). Каждый товар характеризуется наличием или отсутствием его в магазине, а также наличием или отсутствием на него спроса покупателей. Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магазинов) товаров.

5.4. Элементы доказательного программирования

Доказательное программирование - это составление программ с доказательством их правильности. Сложность составления и доказательства правильности алгоритмов и программ состоит в следующем.

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

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