Есть два упорядоченных множества неотрицательных чисел А[1]..A[n] и В[1]...B[n]. Найти такие неотрицательные коэффициенты k и m, при которых максимальный элемент множества C[i] = 1-(k*A[i]+m*B[i]) будет наименьшим и множество С[i] не будет содержать отрицательных элементов.
k=0.5*(1-1/i)*1/A[i], а m=0.5*(1-1/i)*1/B[i]
Так как элементы совершенно проищвольны, то последующее значение всегда неопределено, но зато увеличивается число i... Мне кажется это тоже достаточно просто, или же это правильно?
Админ: k и m не должны зависеть от индекса. Это общие коэффициенты, дающие оптимальный расклад.
Андрей 2015-03-08 16:07:34 пишет:
А почему нет?)))
Админ: потому что легко подобрать пример, когда эти коэффициенты не дают оптимальный результат
Андрей 2015-03-08 16:06:02 пишет:
В силу произвольности массива к = 0 = м
Админ: надо найти алгоритм, при котором сумма максимально приблизится к 1. В вашем случае это будет самый плохой возможный вариант.
хмм... пока в процессе, но есть занятное наблюдение, если у нас есть такое i при котором и A[i]=0 и B[i]=0 то меньше 1 не получить никак :) Ну и разумеется при любых наборах элементарно получить эту же единичку обоими нулевыми к-тами... ушёл думать дальше...
дополнительный вопрос: в примерах видим диапазон 0-1, но в условии этого нет - это пропущено просто, или наоборот в примерах - случайность и такие значения как (2, 2) или (Pi/2, 100500) - тоже следует рассматривать? ... ... хотя... если всё поделить на "мах" и просто вынести его за скобки... я думать... :)
а если так - там где самое максимальное -там к-т =0 а в другом - 1/мах ? тоже Слишком просто? (просто пока без бумажки - первое что пришло "на пальцах") Или даже просто сравнить 0 и 1/мах против 1/мах и 0 ?
"что каждому индексу соответствует конкретное число массива"
Ну массив - это просто набор чисел. Естественно, что каждому индексу соответствует какое-то число. В чём упорядоченность-то? Массив 1, 18, 7, 12 упорядочен или нет?
Админ: например, упорядочен по неизвестному признаку. Массив и есть упорядоченное множество.
k = 1/(2*A[n]), m = 1/(2*B[n]), если множества упорядочены по возрастанию, и
k = 1/(2*A[1]), m = 1/(2*B[1]), если множества упорядочены по убыванию. Разве нет?
Админ: наверное, тут слово "упорядочены" лишнее. Имелось ввиду, что каждому индексу соответствует конкретное число массива, числа нельзя перемешивать.