 |
 |
 |
 |
|
 |
 |
116
Приведем постановку задачи и описание способа ее решения.
Постановка задачи
Способ решения
Определение суммарной
и максимальной стоимости товаров.
Дано:
(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 = C1 • M1 + С2 • М2 + ... + С
N
• М
N
,
все
TovMax: C
M = Мах(С1 • М1, ... ,С
N
• М
N
).
кцикл
При: N > 0.
Прежде чем приступить к составлению алгоритмов и программ, убедимся в правильности
выбранного способа решения. Для этого проверим результаты на первых шагах, в середине и в конце
вычислений. На первом шаге при k = 1 результат
s1 = s
0
+ С1 • М1 = С1 • M1,
max1 = С1 • М1.
На втором шаге вычислений будут получены следующие значения:
s2 = s1 + С2 • М2 = C1 • M1 + С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
= C1 • M1 + … + C
k
• M
k
,
max
k
= Max(max
k-1
, С
k
• М
k
) = Мах(С1 • М1, ..., С
k
• М
k
).
Для доказательства этих утверждений необходимо предположить, что они выполняются для случая
k-1:
s
k-1
=C1 • M1 +...+ C
k-1
• M
k-1
,
max
k-1
= Max (C1 • M1, …,C
k-1
• M
k-1
),
и подставить эти выражения в соотношения для s
k
и mах
k
:
s
k
= s
k-1
+ C
k
• M
k
= C1 • M1 + … 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
= C1 • M1 + … + C
N
• M
N
,
max
N
= Max(max
N-1
, С
N
•
М
N
) = Max(C1 • M1, ... , С
N
•
М
N
).