Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Сортировка >> Номер 11

[Назад]    [Содержание ]    [Вперед]

  


Номер 11


  Условие: Номер 11


Задача 11. Имеются числа А1,А2,...,АN и B1,B2,...,BN. Составить из них N пар (Аi, Bj) таким образом, чтобы сумма произведений пар была максимальна (минимальна). Каждое Ai и Bj в парах встречаются ровно по одному разу.

  Решение задачи: Номер 11


Решение задачи 11. Чтобы сумма произведений пар была максимальна (минимальна) необходимо упорядочить наборы A и B одинаковым (различным) образом и пары будут составлять элементы стоящие на одинаковых позициях в упорядоченных наборах. Это следует из того факта, что если а<b и c<d,то а*с+в*d>=a*d+b*c.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017