21
правка
Изменения
Новая страница: «'''Задача о минимуме/максимуме скалярного произведения''' - задача о нахождении минимальной…»
'''Задача о минимуме/максимуме скалярного произведения''' - задача о нахождении минимальной/максимальной суммы попарных произведений для двух заданных упорядоченных наборов чисел.
== Теорема ==
Минимум скалярного произведения достигается при сопоставлении возрастащей последовательности <tex>x_1..x_m</tex> и убывающей последовательности <tex>y_1..y_m</tex>. При сопоставлении возрастающим <tex>x_1..x_m</tex> и <tex>y_1..y_m</tex> достигается максимум.
док-во
1. Будем считать, что <tex>x_i</tex> отсортирована по возрастанию.
2. Покажем, что если существуют пары чисел <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>. Так так
<tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j x_j > x_j y_i + x_i y_j</tex>.
3.Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_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>. В результате получится отсортированная по возрастанию последовательность.
== Теорема ==
Минимум скалярного произведения достигается при сопоставлении возрастащей последовательности <tex>x_1..x_m</tex> и убывающей последовательности <tex>y_1..y_m</tex>. При сопоставлении возрастающим <tex>x_1..x_m</tex> и <tex>y_1..y_m</tex> достигается максимум.
док-во
1. Будем считать, что <tex>x_i</tex> отсортирована по возрастанию.
2. Покажем, что если существуют пары чисел <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>. Так так
<tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j x_j > x_j y_i + x_i y_j</tex>.
3.Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_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>. В результате получится отсортированная по возрастанию последовательность.
