Изменения

Перейти к: навигация, поиск
Нет описания правки
'''Задача о минимуме/максимуме скалярного произведения''' - задача о нахождении минимальной/максимальной суммы попарных произведений для двух заданных упорядоченных наборов чисел.
== Решение ==Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + ... + x_m y_m</tex>{{Теорема |about=о минимуме/максимуме скалярного произведения|statement=Минимум скалярного произведения достигается при сопоставлении возрастащей последовательности <tex>x_1..x_m</tex> и убывающей последовательности <tex>y_1..y_m</tex>. При сопоставлении возрастающим <tex>x_1..x_m</tex> и <tex>y_1..y_m</tex> достигается максимум. док-во
|proof=
1. Будем считать, что <tex>x_i</tex> отсортирована по возрастанию.
4. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность.
}}
== Литература ==
1. Романовский И. В. Дискретный анализ. — 3-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 320.
Анонимный участник

Навигация