Задача постановка метод алгоритм

Приведем пример построения алгоритма с одновременным ана­лизом его правильности.

Задача: Определить периметр треугольника, заданного на плос­кости координатами вершин.

X_С,У_С

X_А,У_А Xв,Ув

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

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

Дано: А = (Х_А, У_А)

В = (Х_В, У_В) - координаты вершин треугольника

С = (X_С,У_С)

Треб.: Р - периметр

Метод решения

Р = L_АВ +L_ВС+L_СА

L_АВ =

L_ВС =

L_СА =

Где: Р = L(A,B) + L(B,C) + L(C,A);

здесь L[(x,y),(u,v)] = .

Приведем алгоритм, полученный из описания метода упорядоче­нием операций вычисления длин сторон треугольника с заверша­ющим вычислением периметра. Результаты выполнения алгоритма приведены справа.

Алг «периметр треугольника»

Нач

LAB: =

LBC : =

LCA : =

Р := LAB + LBC + LCA

Кон

Результаты

Р = LAB + LBC + LCA

Сравнение результатов выполнения алгоритма с описанием метода решения показывает, что это одна и та же система формул, что подтверждает правильность алгоритма.

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

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

Задача способ

¯ ¯

Постановка методы

¯ ¯

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

¯ ¯

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

Основные типы алгоритмических ошибок в программах:

· ошибки в выбранных методах решения;

· ошибки в постановке решаемых задач;

· дефекты в сценариях диалога с ЭВМ;

· ошибки организации ввода данных;

· неправильная реализация методов решения.

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

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

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

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

Фамилия рост вес

Иванов
Петрова
Сидоров

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

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

Определение суммарного веса.

Дано:Метод вычисления

(D₁,.., D_N) - данные об учениках, S₀ = 0

где D = [Fam,R,V] - состав данных, S_k = S_k-1 + v_k

Fam - фамилия, R - рост, V - вес. [k = (1 ... N)]

Треб.: V_sum - суммарный вес. V_sum = S_N

V_sum = v₁ + v₂ + ... + v_N

При: N > 0.

Правильность метода вычислений можно доказать по индукции. Рассмотрим результаты вычислений на 1-м, 2-м и k-м шагах. Отме­тим, что начальное значение S₀ = 0.

На первом шаге при k = 1 результат вычисления

S₁ = S₀ +v₁ = v₁

На следующем втором шаге при k = 2 результат

S₂ = S₁ + v₂ = v₁ + v₂.

На третьем шаге при k = 3 результат

S₃= S₂ + v₃ = v₁ + v₂ + v₃.

В общем случае можно предположить, что к k-му шагу результат вычисления

S_k-1=v₁+...+v_k-1.

Тогда результат вычислений после k-го шага (исходя из описания метода)

S_k = S_k-1 +v_k = v₁ + … + v_k-1 + v_k.

В силу принципа математической индукции утверждение верно для всех k = 1, 2,.... N. Следовательно, на последнем шаге при k = N конечный результат:

S_N = v₁ + ... + v_N.

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

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

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

Данные об учениках

фамилия вес рост

dano:'данные учеников

<Fam₁> <V₁> <R₁> data «Иванов», 185, 85

… … … data «Петрова», 165, 65

<Fam_N> <V_N> <R_N> data «Сидоров», 170, 80

data «», 0, 0

суммарный вес = <Vsum>

Алгоритм обработки данных и программа, соответствующие выбранному сценарию и методу вычисления:

АлгоритмПрограмма

алг «суммарный вес» ' суммарный вес

нач cls

вывод («Данные об учениках») ? «Данные об учениках»

вывод («фамилия вес рост») ? «фамилия вес рост»

s := 0 s = 0

цикл do

чтение famS, r, v read fam$, r, v

при fam$=«» выход if fam$=«» then exit do

вывод (fam$, v, r) ? fam$; v; r

s := s + v s = s + v

кцикл loop

vsum = s vsum = s

вывод («суммарный вec=»,vsum) ? «суммарный вес=»; vsum

кон end

Правильность приведенного алгоритма можно увидеть из описа­ния результатов его выполнения.

АлгоритмРезультаты выполнения

алг «суммарный вес» на экране и в памяти ЭВМ

Нач

вывод («Данные об учениках») Данные об учениках

вывод («фамилия вес рост») фамилия вес рост

s: = 0s₀ = 0

Цикл

чтение fam$, r, v

при fam$=«» выход

вывод (fam$, v, r)<fam_k> <v_k> <r_k>

s: = s + v s_k = s_k-1 + v_k

кцикл[k = (1...n)]

vsum = svsum = s_n

вывод («суммарный вec=»,vsum) суммарный вес= <vsum>

Кон

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

В о п р о с ы

1. Когда программы содержат ошибки?

2. Что такое правильный способ решения?

3. Когда способ решения неправильный?

4. Что такое правильный метод решения?

5. Когда метод решения неправильный?

6. Что такое правильный алгоритм?

7. Когда алгоритм содержит ошибки?

8. Каковы основные типы ошибок в программах?

З а д а ч и

1. Приведите постановку задачи, сценарий, алгоритм и программу ре­шения линейного уравнения а×х + b = 0, с помощью формулы х = -b/а (при а ¹ 0).

2. Приведите постановку задачи, сценарий, алгоритм и программу решения квадратного уравнения а×х² + b×x + с = 0 с помощью формулы дискриминанта.

3. Приведите постановку задачи, сценарий, алгоритм и программу решения системы из двух уравнений с двумя неизвестными:

а×х + Ь×у = е,

с×х + d×y = f.

Примените для этой задачи вычисление корней с помощью опреде­лителей:

х = D_x/D,

y = D_y/D.

Определители D, D_x и D_y вычисляются по формулам:

D = a×d - b×c,

D_x = e×d - f×b,

D_y = a×f - c×e.

4. Приведите постановку, сценарии, алгоритм и программу решения следующих задач:

а) определение площади треугольника по длине сторон а, Ь, с по формуле Герона:

S = ,

р = (а + b + с)/2.

б) определение площади треугольника, заданного на плоскости ко­ординатами своих вершин: (х₁, у₁), (х₂, у₂), (х₃, у₃); для вычисления длин сторон треугольника воспользуйтесь формулой определения длин от­резков на плоскости, задаваемых координатами концов:

l =

5. Приведите постановку, метод, сценарий, алгоритм и программу решения следующих задач:

а) определение времени встречи пешеходов, двигающихся навстречу друг другу;

б) определение времени, которое требуется пешеходу, чтобы догнать другого пешехода;

в) определение времени движения парохода по течению и против течения реки;

г) определение времени движения пешеходов навстречу друг другу, если один из них движется с замедлением;

д) определение времени падения тела с заданной высоты;

е) определение времени полета тела, брошенного вверх;

ж) определение расстояния, на которое улетит мяч, брошенный под углом к горизонту.

6. Дана прямоугольная матрица А_NM - прямоугольная числовая таб­лица размера N ´ М. Приведите постановку, метод решения, сценарий, алгоритм и программу для решения следующих задач:

а) подсчет сумм элементов матрицы по столбцам,

б) подсчет сумм элементов матрицы по строкам,

в) нахождение минимального значения в каждом столбце,

г) нахождение минимального значения в каждой строке,

д) нахождение максимального значения в каждом столбце,

е) нахождение максимального значения в каждой строке,

ж) нахождение наибольшего из минимальных значений в столбцах,

з) нахождение наименьшего из максимальных значений в строках.

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

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

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

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

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

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

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

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

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

¯ ¯

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

¯ ¯

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

¯ ¯

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

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

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

Задача способ

­ ­

Постановка методы

­ ­

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

­ ­

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

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

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

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

Иванов	директор
Петров	менеджер
Сидорова	секретарь

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

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

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

Дано:

(D₁, ..., D_N) - данные о сотрудниках,

где D = [Fam, Т, Z] - состав данных,

Fam - фамилия, D₁- должность, S₀ = 0

Z - зарплата. S_k = S_k-1*(k-l )/k + Z_k/k

Треб: Zcpeдн - средняя зарплата. [k=(l...N)]

Где: Zcpeдн = (Z₁ +Z₂ + ... + Z_N)/N. Zcpeдн = S_N

При: N > 0.

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

При k = 1 результат

S₁=S₀(1 - 1)/1 +Z₁/1 =Z₁/1.

При k = 2 результат

S₂ = S₁(2 - 1)/2 + Z₂/2 = Z₁/2 + Z₂/2.

При k = 3 результат

S₃ = S₂(3 - 1)/3 + Z₃/3 = (Z₁ + Z₂)/3 + Z₃/3.

По этим трем результатам можно утверждать, что в общем случае результатом k-го шага вычислений будет

S_k = (Z₁ + ... + Z_k-1)/k.

Справедливость этого утверждения можно доказать по индукции. Допустим, что оно справедливо для (k-l)-ro шага:

S_k-1 = (Z₁ + ... + Z_k-1)/(k-l).

Тогда из описания метода вычислений очередное k-e значение будет равно

S_k = S_k-1(k-l)/k + Z_k/k =

= (Z₁ + ... + Z_k-1)/(k-l)×(k-l)/k + Z_k/k = (Z₁ + ... + Z_k-1)/k + Z_k/k.

Что и требовалось показать. Следовательно, в силу математичес­кой индукции это утверждение справедливо для всех k = 1, 2,..., N. В частности, для последнего шага вычислений при k = N конечным результатом будет

S_N = (Z₁ + ... + Z_N-1)/N + Z_N/N = (Z₁ + ... + Z_N)/N.

Таким образом, выбранный метод дает правильный результат для любой последовательности величин Z₁, Z₂, ..., Z_N.

Для конструирования алгоритма и программы решения задачи на ЭВМ примем следующий сценарий, а для представления данных воспользуемся операторами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 := 0S₀ = 0 [ k = 0 ]

Цикл

чтение (fam$, dl$, z)

при fam$ = «» выход

вывод (fam$, dl$, z) <fam_k> <dl_k> <z_k> }*

k:=k+ 1[ k= (1...N) ]

s := s*(k - 1)/k + z/k sk = sk - 1×(k - 1)/k + z_k/k

Кцикл

zsr = s zsr = s_N

вывод («средняя з/nлama=»,zsr) средняя з/плата= <zsr>

Кон

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

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

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

яблоки
бананы
арбузы

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

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

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

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

Дано:

(D₁, ..., D_N) - данные о товарах,

где D = [Tov, C, M] - состав данных, s₀ = 0

Tov - товар, С - цена товара, от k = 1 до N цикл

М - количество товара, s_k = s_k-1 + С_kМ_k

Треб: если k = 1 то

Sum - суммарная стоимость товаров, mах₁ = С₁₁М₁₁

TovMax - товар максимальной инеc С_kМ_k > mах_k-1 то

стоимости.

Где: mах_k = С_kМ_k

Sum = C₁M₁ + С₂М₂ + ... + С_NМ_N, все

TovMax: C×M = Мах(С₁М₁, ... ,С_NМ_N). кцикл

При: N > 0.

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

s₁ = s₀ + С₁М₁ = С₁M₁,

max₁ = С₁М₁.

На втором шаге вычислений будут получены следующие значе­ния:

s₂ = s₁ + С₂М₂ = C₁M₁ + С₂М₂,

max₂ = С₂М₂, при С₂М₂ > max₁ = Мах(mах₁, С₂М₂),

max₁, при С₂М₂ £ max₁ = Мах(mах₁, С₂М₂).

На третьем и последующих шагах в общем случае будут получать­ся результаты:

s_k = s_k-1 + C_kM_k = C₁M₁ + … + C_kM_k,

max_k = Max(max_k-1, С_kМ_k) = Мах(С₁М₁, ..., С_kМ_k).

Для доказательства этих утверждений необходимо предположить, что они выполняются для случая k-1:

s_k-1 =C₁M₁ +...+ C_k-1M_k-1,

max_k-1 = Max (C₁M₁, …,C_k-1M_k-1),

и подставить эти выражения в соотношения для s_k и mах_k:

s_k = s_k-1 + C_kM_k = C₁M₁ + … C_k-1M_k-1 + C_kM_k,

max_k = Max(max_k-1, С_kМ_k) = Мах(С₁М₁, ..., С_kМ_k).

В силу математической индукции эти утверждения верны для всех k = 1, 2, ..., N. Поэтому на последнем шаге вычислений при k = N будут получены окончательные результаты:

s_N = s_N-1 + C_NM_N = C₁M₁ + … + C_NM_N,

max_N = Max(max_N-1, С_NМ_N) = Max(C₁M₁, ... , С_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 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 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, М и названия товаров заданы). Каждый товар характеризуется наличием или отсутст­вием его в магазине, а также наличием или отсутствием на него спроса покупателей. Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магазинов) товаров.