Список товаров

Do

Сls

Цикл

Нач

Цикл

Нач

Цикл

Нач

T t

Т т

T t

I I

I I

I I

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

Данные об учениках фамилия вес рост

Нач

вывод («Данные об учениках») вывод («фамилия вес рост») s: = 0 цикл

чтение fam$, r, v при fam$=«» выход вывод (fam$, v, r) s: = s + v кцикл vsum = s вывод («суммарный вec=»,vsum) кон

{

Результаты выполнения на экране и в памяти ЭВМ

S₀ = 0

<fam_k> <v_k> <r_k>

s_k = s_k-1 + v_k

[k = (1...n)] vsum = s_n

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

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

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

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

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

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

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

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

Составление программ
задача -» способы

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

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

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

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

Анализ правильности
задача <- способ

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

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

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

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

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

фамилия Иванов	должность директор	зарплата 300000
Петров	менеджер
Сидорова	секретарь

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

Метод расчета

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

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

Дано:

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

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

S0 = 0 Sk = Sk-i*(k-l)/k + Zk/k [k=(l...N)] гсредн = SN

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

{

Z - зарплата.

Треб: Zcpeдн - средняя зарплата.

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

При: N > 0.

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

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

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

S₂ = Si(2 - l)/2 + Z₂/2 = Zi/2 + Z₂/2.

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

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

Алгоритм

алг «средняя зарплата»

вывод («список сотрудников:»)

s:= 0: k:= 0

чтение (fam$, dl$, zpl) при fam$ = «» выход вывод (fam$, dl$, z) k:= k + 1

s:= s*(k - 1)/k + z/k кцикл zsr = s

вывод («средняя 3/nлama=»,zsr) кон

Программа ' средняя зарплата cls? «список сотрудников:» s = 0: k = 0 do

read fam$, dl$, zpl if fam$ = «» then exit do? fam$; dl$; z k = k + 1

s = s*(k - 1)/k + z/k loop zsr = s

? «средняя з/плата=»; zsr end

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

Алгоритм

алг «средняя зарплата»

вывод («список сотрудников:»)

s:= 0: k:= 0

чтение (fam$, dl$, z) при fam$ = «» выход вывод (fam$, dl$, z) k:=k + 1

s:= s*(k - 1)/k + z/k кцикл zsr = s

вывод («средняя з/nлama=»,zsr) кон

Результаты выполнения

список сотрудников:

S₀ = 0 [ k = 0 ]

<fam_k> <dl_k> <z_k> }* Г [ k= (l...N) ] I sk = sk - l- (k - l)/k + z_k/k

zsr = s_N

<zsr>

средняя з/плата=

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

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

товар яблоки	цена 8000	кол-во 3
бананы
арбузы

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

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

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

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

Дано:

s0 = 0 от k = 1 до N цикл sk = sk-1 + СkМk если k = 1 то mах1 = С11М11 инеc СkМk > mахk-1 то mахk = СkМk все кцикл

(Di,..., Dn) - данные о товарах,

где D = [Tov, С, М] - состав данных,

Tov - товар, С - цена товара,

М - количество товара,

Треб:

Sum - суммарная стоимость товаров,

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

стоимости.

Где:

Sum = С1М1 + С₂М₂ +... + С_NМ_N,

TovMax: CM = Мах(СiМ_b...,С_NМ_N).

При: N > 0.

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

Si = So + С1М1 = С1М1, maxi = СiМi.

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

S₂ = Si + С₂М₂ = С1М1 + С₂М₂,

max₂ = ГС₂М₂, при С₂М₂ > тахЛ = Мах(тах_ь С₂М₂), I тах_ь при С₂М₂ < maxi J = Мах(тах_ь С₂М₂). На третьем и последующих шагах в общем случае будут получаться результаты:

s_k = Sk-i + C_kM_k = CiMi +... + С_кМ_к, max_k = Max(max_k-i, С_kМ_k) = Мах(СiМ_b..., С_кМ_к). Для доказательства этих утверждений необходимо предположить, что они выполняются для случая к-1:

Sk-i =CiMi +...+ Ck-iMk-i, maxk-i = Max(CiM_b...,C_k-iM_k-i), и подставить эти выражения в соотношения для Sk и mахk:

s_k = Sk-i + C_kMk = CiMi +... Ck-iMk-i + С_кМк, maxk = Max(max_k-i, С_kМ_k) = Мах(СiМ_b..., С_кМ_к). В силу математической индукции эти утверждения верны для всех к = 1, 2,..., N. Поэтому на последнем шаге вычислений при к = N будут получены окончательные результаты:

s_N = s_N-i + C_NM_N = С1М1 +... + C_NM_N, max_N = Max(max_N_i, С_NМ_N) = Max(CiM_b..., С_NМ_N). Что и требовалось в постановке задачи. Следовательно, выбранный способ решения по­ставленной задачи правилен и на его основе можно приступать к составлению соответствующих алгоритма и программы.

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

Сценарий

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

список товаров товар цена кол-во \<товl> <сl> <т / > 1 *

сумма = <Sum>

dan: 'сведения о товарах data яблоки, 8000, 3 data бананы, 4000, 2

Максимум data арбузы, 1000, 20

<товар> <стоим> data «», 0, 0

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

ным сценарием и представлением данных.

Алгоритм

алг «сумма и максимум»

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

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

s:= 0; k = 0

чтение (тов, с, т) при тов = «» выход k:= k + 1 вывод (тов, с, т) s:=s + cm если k = 1 то max:= c⋅m ToвMax:= тов инес c(m > max то max:= c⋅m ToвMax:= тов кесли кцикл

вывод («cyммa=»,s) вывод («Максимум») вывод (ToвMax, max) кон

Программа

' сумма и максимум

? «список товаров»

? «товар цена кол-во»

s = 0: k = 0

read tv$, с, m if tv$ = «» then exit do k = k + 1? fv$; с; m s= s + c(m if k = 1 then max = c ⋅ m ТМ$ = tv$

elseif c(m > max then max = c ⋅ m TM = tv$ end if loop

? «cyммa=»,s? «Максимум»? TM$, max end

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

Алгоритм

алг «сумма и максимум» нач

вывод («список товаров») вывод («товар цена кол-во») s:= 0; k = 0 цикл

чтение (тов, с, т) при тов = «» выход k:=k+1

вывод (тов, с, т) s:= s + с⋅т если k = 1 то

тах:= c⋅m

ТовМах:= тов uнес c⋅m > тах то

тах:= с⋅т

ТовМах:= тов кесли кцикл вывод («сумма=», s)

<

Результаты выполнения