Имеет ли решение задача? Есть две последовательности чисел:
a1, a2, a3… an
b1, b2,b3… bn
Среднее арифметическое этих двух последовательностей равны.
Вычисляется разность между последовательностями следующим образом:
R = |a1-b1| + |a2-b2| + |a3-b3| +… + |an-bn|
Задача в том, возможно ли найти такой коэффициент k, домножив на который первую последовательность,
чтобы разница между последовательностями была минимальной.
т.е.
R = |k*a1-b1| + |k*a2-b2| + |k*a3-b3| +… + |k*an-bn|
т.е. нужно найти такой k, при котором R минимальна.
Другими словами, нужно подобрать такой масштабный коэффициент для первой последовательности, чтобы разница между последовательностями была минимальной.
Конечно, эта задача достаточно легко решается «двоичным поиском» (до определенной точности), но для этого нужно совершить некоторое количество вычислений R с разными k.
А можно ли как-то найти этот k не методом перебора?UPD. Все числа >= 0
Имеет ли решение задача? Есть две последовательности чисел:
a1, a2, a3… an
b1, b2,b3… bn
Среднее арифметическое этих двух последовательностей равны.
Вычисляется разность между последовательностями следующим образом:
R = |a1-b1| + |a2-b2| + |a3-b3| +… + |an-bn|
Задача в том, возможно ли найти такой коэффициент k, домножив на который первую последовательность,
чтобы разница между последовательностями была минимальной.
т.е.
R = |k*a1-b1| + |k*a2-b2| + |k*a3-b3| +… + |k*an-bn|
т.е. нужно найти такой k, при котором R минимальна.
Другими словами, нужно подобрать такой масштабный коэффициент для первой последовательности, чтобы разница между последовательностями была минимальной.
Конечно, эта задача достаточно легко решается «двоичным поиском» (до определенной точности), но для этого нужно совершить некоторое количество вычислений R с разными k.
А можно ли как-то найти этот k не методом перебора?UPD. Все числа >= 0
a1, a2, a3… an
b1, b2,b3… bn
Среднее арифметическое этих двух последовательностей равны.
Вычисляется разность между последовательностями следующим образом:
R = |a1-b1| + |a2-b2| + |a3-b3| +… + |an-bn|
Задача в том, возможно ли найти такой коэффициент k, домножив на который первую последовательность,
чтобы разница между последовательностями была минимальной.
т.е.
R = |k*a1-b1| + |k*a2-b2| + |k*a3-b3| +… + |k*an-bn|
т.е. нужно найти такой k, при котором R минимальна.
Другими словами, нужно подобрать такой масштабный коэффициент для первой последовательности, чтобы разница между последовательностями была минимальной.
Конечно, эта задача достаточно легко решается «двоичным поиском» (до определенной точности), но для этого нужно совершить некоторое количество вычислений R с разными k.
А можно ли как-то найти этот k не методом перебора?UPD. Все числа >= 0
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Да, данную задачу можно решить аналитически. Разберем способ нахождения оптимального коэффициента k.
Поскольку все числа в последовательностях больше или равны нулю, можно заметить, что для минимизации суммы модулей разностей можно выбрать k таким образом, чтобы a_i >= b_i для всех i. В этом случае модуль разности будет равен a_i - b_i.
Итак, чтобы минимизировать (\sum_{i=1}^{n}|k*a_i - b_i|), мы можем выбрать k таким образом, чтобы он был наименьшим коэффициентом, удовлетворяющим условию a_i >= b_i для всех i.
Таким образом, оптимальное значение k равно (k = \max\frac{b_i}{a_i}).
Это решение не требует перебора и может быть найдено аналитически.