Алгоритм для нахождения следующего числа в последовательности
С тех пор, как я начал программировать, это было чем-то, на предмет чего мне было любопытно. Но кажется слишком сложным, чтобы я даже попытался.
Я хотел бы видеть решение.
1, 2, 3, 4, 5 // returns 6 (n + 1)
10, 20, 30, 40, 50 //returns 60 (n + 10)
10, 17, 31, 59, 115 //returns 227 ((n * 2) - 3)
9 ответов
То, что вы хотите сделать, называется полиномиальной интерполяцией . Существует множество методов (см. http://en.wikipedia.org/wiki/Polynomial_interpolation ), но вы должны иметь верхнюю границу U степени полинома и по крайней мере U + 1 значения.
Если у вас есть последовательные значения, тогда есть простой алгоритм.
Для данной последовательности x1, x2, x3, ... пусть Delta (x) будет последовательностью разностей x2 - x1, x3 - x2, x4 - x3, .... Если у вас есть последовательные значения многочлена степени n, то n-я итерация Delta является постоянной последовательностью.
Например, многочлен n ^ 3:
1, 8, 27, 64, 125, 216, ...
7, 19, 37, 61, 91, ...
12, 18, 24, 30, ...
6, 6, 6, ...
Чтобы получить следующее значение, введите еще 6 и затем двигайтесь в обратном направлении.
6, 6, 6, 6 = 6, ...
12, 18, 24, 30, 36 = 30 + 6, ...
7, 19, 37, 61, 91, 127 = 91 + 36, ...
1, 8, 27, 64, 125, 216, 343 = 216 + 127, ...
Указанное выше ограничение на количество значений гарантирует, что ваша последовательность никогда не станет пустой при выполнении различий.
Формально не существует уникального следующего значения для частичной последовательности. Проблема, как обычно понимается, может быть четко сформулирована следующим образом:
Предположим, что показанная частичная последовательность достаточна только для ограничения некоторого порождающего правила, вывести простейшее возможное правило и показать следующее сгенерированное значение.
Проблема включает в себя значение слова «простейший» и, таким образом, не очень хорошо подходит для алгоритмических решений. Это можно сделать, если вы ограничите проблему определенным классом функциональных форм для правила генерации, но детали зависят от того, какие формы вы готовы принять.
Такого рода числовые ряды часто являются частью «тестов интеллекта», что заставляет меня думать в терминах такого алгоритма как нечто, проходящее (по крайней мере, часть) тест Тьюринга, что довольно трудно выполнить.
Вы можете попробовать использовать экстраполяцию. Она поможет вам найти формулы для описания заданной последовательности.
Извините, я не могу рассказать вам больше, так как мое математическое образование было получено довольно давно. Но вы должны найти больше информации в хороших книгах.
В книге Числовые рецепты есть страницы и страницы с реальными практическими алгоритмами для выполнения такого рода вещей. Его стоит прочитать!
Первые два случая просты:
>>> seq1 = [1, 2, 3, 4, 5]
>>> seq2 = [10, 20, 30, 40, 50]
>>> def next(seq):
... m = (seq[1] - seq[0])/(1-0)
... b = seq[0] - m * 0
... return m*len(seq) + b
>>> next(seq1)
6
>>> next(seq2)
60
Третий случай потребует решения для нелинейной функции.
Мне нравится эта идея, и последовательность один и два кажется мне возможной, но опять же, вы не можете обобщить, так как последовательность может полностью сойти за базовую. Ответ, вероятно, заключается в том, что вы не можете обобщить, что вы можете сделать, так это написать алгоритм для выполнения определенной последовательности, зная (n+1) или (2n+2) и т. д...
Одна вещь, которую вы можете сделать, это взять разность между элементом i и элементом i+1 и элементом i+2.
например, в вашем третьем примере:
10 17 31 59 115
Разница между 17 и 10 равна 7, а разница между 31 и 17 равна 14, а разница между 59 и 31 равна 28, а разница между 115 и 59 равна 56.
Таким образом, вы замечаете, что получается элемент i+1 = i + (7*2^n).
Так 17 = 10 + (7*2^0)
И 31 = 17 + (7*2^1)
И так далее...
См. Также главу «Искать, откуда приходит последовательность» из книги «Гибкие концепции и творческие аналогии: компьютерные модели фундаментальных механизмов мышления» Дуглас Хофштадтер
Извините за разочарование, но это не совсем возможно (в общем случае), поскольку существует бесконечное количество последовательностей для любого заданного k значений. Может быть, с некоторыми ограничениями ..
Вы можете взглянуть на этот пост Everything2 , который указывает на многочлен Лагранжа .
Для произвольной функции это сделать невозможно, но для линейной функции, как в каждом из ваших примеров, это достаточно просто.
У вас есть f(n+1) = a*f(n) + b, и задача сводится к нахождению a и b.
Учитывая по крайней мере три члена последовательности, вы можете это сделать (вам нужно три, потому что у вас есть три неизвестных - начальная точка, a и b). Например, предположим, у вас есть f(0), f(1) и f(2).
Мы можем решить уравнения:
f(1) = a*f(0) + b
f(2) = a*f(1) + b
Решение для:
a = (f(2)-f(1))/(f(1)-f(0))
b = f(1) - f(0)*(f(2)-f(1))/(f(1)-f(0))
(Вы захотите отдельно решить случай, когда f(0) = f(1), чтобы избежать деления на ноль.)
Как только вы получите a и b, вы можете многократно применять формулу к начальному значению, чтобы получить любой член в последовательности.
Можно также написать более общую процедуру, которая работает при задании любых трех точек в последовательности (например, 4-й, 7-й, 23-й или любой другой)... Это всего лишь простой пример.
Хотя, опять же, мы должны были сделать некоторые предположения о том, какую форму будет иметь наше решение... в данном случае, если оно будет линейным, как в вашем примере. Можно взять, например, более общий полином, но в этом случае для нахождения решения потребуется больше членов последовательности, в зависимости от степени полинома.