Я только что получил этот вопрос в интервью по позиции SE, и я не совсем уверен, как ответить на него, кроме грубой силы:
Учитывая натуральное число N, найдем два числа A и P такие, что:
N = A + (A + 1) + (A + 2) +... + (A + P-1)
P должно быть максимально возможным.
Ex: для N = 14 A = 2 и P = 4
N = 2 + (2 + 1) + (2 + 2) + (4 + 2-1) N = 2 + 3 + 4 + 5
Любые идеи?
Если N четно/нечетно, нам нужно четное/нечетное число нечетных чисел в сумме. Это уже уменьшает количество возможных решений. Например. для N = 14 нет смысла проверять любые комбинации, где P нечетно.
Переписывая приведенную формулу, получим:
N = A + (A+1) + (A+2) + ... + (A+P-1)
= P*A + 1 + 2 + ... + (P-1)
= P*A + (P-1)P/2 *
= P*(A + (P-1)/2)
= P/2*(2*A + P-1)
Последняя строка означает, что N должно делиться на P/2, это также исключает ряд возможностей. Например. 14 имеют только эти делители: 1, 2, 7, 14. Таким образом, возможные значения для P будут равны 2, 4, 14 и 28. 14 и 28 управляются по понятным причинам (на самом деле любой P выше N/2 может быть игнорируется).
Это должно быть намного быстрее, чем метод грубой силы.
(* Сумма первых n натуральных чисел равна n (n + 1)/2)
С вопросами интервью часто бывает разумно думать о том, что, вероятно, является целью вопроса. Если бы я задавал вам этот вопрос, это не потому, что я думаю, что вы знаете решение, но я хочу, чтобы вы нашли решение. Реформируя проблему, делая выводы, разрабатывая то, что известно... это то, что я хотел бы видеть.
Если вы просто сидите и говорите мне: "Я не знаю, как это решить", вы сразу же не сдаете интервью.
Если вы скажете: я знаю, как решить это грубой силой, и я знаю, что это будет, вероятно, медленным, я дам вам несколько советов или поможет вам начать работу. Если это не поможет, вы, скорее всего, потерпите неудачу (если вы не продемонстрируете некоторые необычные навыки, чтобы компенсировать тот факт, что вам, вероятно, не хватает чего-то в области общего анализа проблем, например, вы покажете, как реализовать решение, парализованное для многих ядер или реализовано на GPU).
Если вы принесете мне готовое решение, но вы не сможете его получить, я дам вам еще одну аналогичную проблему, потому что меня не интересует решение, меня интересует ваше мышление.
/li > A + (A+1) + (A+2) + ... + (A+P-1) упрощается до P*A + (P*(P-1)/2) resp P*(A+(P-1)/2).
Таким образом, вы можете просто перечислить все делители N, а затем проверить каждый делитель P на следующее:
Является ли A = (N-(P*(P-1)/2))/P (разрешено первое упрощение для A) целочисленным числом? (Я предполагаю, что это должно быть целое число, иначе это было бы тривиально.) Если да, верните его как решение.
Может быть решена с помощью решения 0-1 Knapsack.
Наблюдение: N/2 + N/2 + 1 > N
поэтому наш ряд равен 1,2,..., N/2
Рассмотрим ограничения W = N и vi = 1 для всех элементов, я думаю, что это тривиально отображает рюкзак 0-1, O (n ^ 2)
Вот решение O (n).
Он использует свойство суммы арифметической прогрессии. S = разность * (first_term + last_term)/2
Здесь наша сумма равна N, разность P и первый член A.
Манипулируя приведенным выше уравнением, получаем некоторые уравнения, и мы можем перебирать P от 1 до n - 1, чтобы получить действительный A.
def solve(n,p):
return (2*n - (p**2) + p)/(2*p)
def condition(n,p,a):
if (2*n == (2*a*p) + (p**2) - p) and (a*-1 < 0):
return True
else:
return False
def find(n):
for x in xrange(n,-1,-1):
a = solve(n,x)
if condition(n,x,a):
return n,x,a