Решение задачи 10.
Основная идея состоит в неиспользовании операции умножения двух чисел. Легко понять, что если числа натуральные, то одна из пар должна содержать максимальное и минимальное числа. Рассуждая таким образом для оставшихся чисел, приходим к простому алгоритму. Упорядочиваем числа в порядке неубывания. Тогда пары составляют первое и последнее, второе и предпоследнее и т.д. Ситуация немного изменяется, если числа целые. В этом случае возможны три варианта:
1. Произведение равно 0. В этом случае существует хотя бы N нулевых элементов. Поэтому пары будут организованы из одного ненулевого элемента и одного нулевого или из двух нулевых элементов.
2. Произведение положительно. В этом случае перемножаются положительные с положительными, а отрицательные с отрицательными, по правилу как и в случае с натуральными числами.
3. Произведение отрицательно. В этом случае перемножается минимальное положительное число с минимальным отрицательным и т.д.
Для определения ситуаций достаточно подсчитать количество нулевых, положительных и отрицательных элементов.
Если есть нулевые элементы, то возможен только вариант 1. Если количество положительных не равно количеству отрицательных, то возможен только вариант 2. В других случаях возможна ситуация 2 и 3.
Для определения знака произведения рассмотрим четверку чисел: максимальный положительный (пусть a), минимальный положительный (b), минимальный отрицательный(c), максимальный отрицательный (d). Понятно, что решением могут быть только пары (a,b),(c,d) или (a,d),(b,c). Если a не равно -c, то в паре с элементом a должен быть меньший по модулю из элементов c, d, если a>-c и наоборот. В случае, если a=-c и b=-d, эта четверка не дает никакой информации о знаке произведения, поэтому можно перейти к следующей четверке чисел и т.д. пока не будет установлен знак произведения. Если же просмотрены все числа, а знак не установлен, то он может быть как плюс, так и минус.
|
