Дан массив вещественных чисел. Назовите это [[]. Теперь рассмотрим другой массив B [] целых чисел. Найдите наименьшее абсолютное значение sum_i (a_i * b_j), где a_i = A [i] и b_j = B [j] для 0 <= i <N и 0 <j <M для некоторого N, M. </strong>
Похоже, что это можно сделать с помощью рекурсии (возможно, с запоминанием, чтобы уменьшить сложность). Я просто не могу придумать способ сформировать рекурсивное отношение. Могу ли я получить подсказку?
Пример: возьмите A = {1.2, 3} и B = {-1, 2, 1}. Затем мы можем сгенерировать 3 * 3 = 9 (не обязательно отличных) возможных сумм (например, для abs (1.2 * -1 + 3 * 1) или abs (1.2 * 2 + 3 * 2) и т. Д. c). Вам нужно найти наименьшее такое абсолютное значение.
Вот одна из идей:
Создать вектор Res [].
Используя A [0], умножьте каждый элемент из B [] и запишите результат в Res []. Res имеет M элементов сейчас.
Возьмите A [1] сейчас. Умножьте его на каждый B [j] и добавьте к каждому элементу Res []. Удалить первые М элементов. Res теперь имеет M ^ 2 элементов.
Возьмите A [2] сейчас. Умножьте его на каждый B [j] и добавьте к каждому элементу Res []. Удалите первые M ^ 2 элементов сейчас. Res [] теперь имеет M ^ 3 элементов.
Продолжайте до тех пор, пока в Res [] не будет M ^ N элементов.
Выполните линейное сканирование сейчас, чтобы найти наименьшее абсолютное значение.
Следующие вопросы уже давно вызывают у меня проблемы:
Может ли этот подход быть изменен на рекурсивный? Лучше, рекурсия с запиской в некотором роде.
Может ли быть не грубое (более эффективное) решение?
Примечание Это не может быть "напрямую" сделано неравенством Перестановки, так как мы обеспокоены абсолютной величиной. Модификация этого может быть полезна; Сейчас я не могу придумать ничего лучшего.