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

Справедливость этого утверждения можно доказать по индукции. Допустим, что оно справедливо для (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 := 0s = 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>

кон

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

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

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

яблоки	8000	3
бананы	4000	2
арбузы	1000	20

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

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

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

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

Дано:

(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×mmax = c×m

ToвMax := товTM = tv$

кеслиend if

кциклloop

вывод («cyммa=»,s)? «cyммa=»,s

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

вывод (ToвMax, max)? TM$, max

кон end

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

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

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

нач

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

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

s :=0;k = 0s₀=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×mmax₁ = 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>

кон

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