 |
 |
 |
 |
|
 |
 |
83
В качестве второго примера рассмотрим решение типичной задачи подсчета суммарной
стоимости товаров с выделением товаров наибольшей стоимости. Допустим, что исходные данные
представлены следующей таблицей:
товар
цена
кол-во
яблоки
8000
3
бананы
4000
2
арбузы
1000
20
Приведем постановку задачи и описание способа ее решения.
Постановка задачи
Способ решения
Определение суммарной
и максимальной стоимости товаров.
Дано:
(D1, ..., D
N
) - данные о товарах,
где D = [Tov, C, M] - состав данных,
s
0
= 0
Tov - товар, С - цена товара,
от k = 1 до N цикл
М - количество товара,
s
k
= s
k-1
+ С
k
М
k
Треб:
если k = 1 то
Sum - суммарная стоимость товаров,
mах1 = С
11
М
11
TovMax - товар максимальной
инеc С
k
М
k
> mах
k-1
то
стоимости.
Где:
mах
k
= С
k
М
k
Sum = C1M1 + С2М2 + ... + С
N
М
N
,
все
TovMax: C
M = Мах(С1М1, ... ,С
N
М
N
).
кцикл
При: N > 0.
Прежде чем приступить к составлению алгоритмов и программ, убедимся в правильности
выбранного способа решения. Для этого проверим результаты на первых шагах, в середине и в
конце вычислений. На первом шаге при k = 1 результат
s1 = s
0
+ С1М1 = С1M1,
max1 = С1М1.
На втором шаге вычислений будут получены следующие значения:
s2 = s1 + С2М2 = C1M1 + С2М2,
max2 = С2М2, при С2М2 > max1
= Мах(mах1, С2М2),
max1, при С2М2
max1
= Мах(mах1, С2М2).
На третьем и последующих шагах в общем случае будут получаться результаты:
s
k
= s
k-1
+ C
k
M
k
= C1M1 + … + C
k
M
k
,
max
k
= Max(max
k-1
, С
k
М
k
) = Мах(С1М1, ..., С
k
М
k
).
Для доказательства этих утверждений необходимо предположить, что они выполняются
для случая k-1:
s
k-1
=C1M1 +...+ C
k-1
M
k-1
,
max
k-1
= Max (C1M1, …,C
k-1
M
k-1
),
и подставить эти выражения в соотношения для s
k
и mах
k
:
s
k
= s
k-1
+ C
k
M
k
= C1M1 + … C
k-1
M
k-1
+ C
k
M
k
,
max
k
= Max(max
k-1
, С
k
М
k
) = Мах(С1М1, ..., С
k
М
k
).
В силу математической индукции эти утверждения верны для всех k = 1, 2, ..., N. Поэтому
на последнем шаге вычислений при k = N будут получены окончательные результаты:
s
N
= s
N-1
+ C
N
M
N
= C1M1 + … + C
N
M
N
,
max
N
= Max(max
N-1
, С
N
М
N
) = Max(C1M1, ... , С
N
М
N
).
Что и требовалось в постановке задачи. Следовательно, выбранный способ решения по-
ставленной задачи правилен и на его основе можно приступать к составлению соответствующих
алгоритма и программы.
Для систематичности разработки примем следующий сценарий диалога и представление
исходных данных в операторах data.