С тех пор, как я начал программировать, мне было любопытно. Но мне кажется слишком сложным даже попытать.
Мне бы хотелось увидеть решение.
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)
То, что вы хотите сделать, называется полиномиальной интерполяцией. Существует много методов (см. 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, ...
Ограничение количества вышеперечисленных значений гарантирует, что ваша последовательность никогда не станет пустой при выполнении различий.
Извините, что разочаровал, но это не совсем возможно (в общем), так как существует бесконечное количество последовательностей для любых заданных значений k. Может быть, с определенными ограничениями.
Вы можете посмотреть этот Everything2 post, который указывает на полином Лагранжа.
Формально нет однозначного следующего значения для частичной последовательности. Проблема, как обычно понимается, может быть четко сформулирована как:
Предположим, что представленная частичная последовательность просто достаточна для ограничения некоторого правила генерации, вывести самое простое возможное правило и показать следующее генерируемое значение.
Проблема включает значение "простейшего" и, следовательно, не очень хорошо подходит для алгоритмических решений. Это можно сделать, если ограничить проблему определенным классом функциональных форм для правила генерации, но детали зависят от форм, которые вы готовы принять.
В книге Numericical Recipes есть страницы и страницы реальных практических алгоритмов для такого рода вещей. Это стоит того, чтобы прочитать!
Первые два случая легко:
>>> 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) и т.д....
Одна вещь, которую вы можете сделать, - это различие между элементом я и элементом я + 1 и элементом я + 2.
например, в третьем примере:
10 17 31 59 115
Разница между 17 и 10 равна 7, а разница между 31 и 17 равна 14, а разница между 59 и 31 составляет 28, а разница между 115 и 59 составляет 56.
Итак, вы заметили, что он становится элементом я + 1 = я + (7 * 2 ^ n).
So 17 = 10 + (7 * 2 ^ 0)
И 31 = 17 + (7 * 2 ^ 1)
И так далее...
Вы можете попытаться использовать экстраполяция. Это поможет вам найти формулы для описания данной последовательности.
Извините, я не могу сказать вам больше, так как мое математическое образование произошло совсем недавно. Но вы должны найти больше информации в хороших книгах.
Такие серии номеров часто являются частью "тестов интеллекта", что заставляет меня думать, что в терминах такого алгоритма есть нечто, проходящее (по крайней мере, часть) "Тест Тьюринга" , чего трудно добиться.
Для произвольной функции это не может быть сделано, но для линейной функции, такой как в каждом из ваших примеров, достаточно просто.
У вас есть 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 или что-то еще)., это простой пример.
Опять же, мы должны были сделать некоторые предположения о том, какая форма будет иметь наше решение., в этом случае считая его линейным, как в вашем примере. Можно считать, что это более общий полином, например, но в этом случае вам нужно больше членов последовательности для поиска решения в зависимости от степени полинома.
См. также главу "Искать, когда приходит последовательность" из книги "Концепции жидкости и творческие аналоги: компьютерные модели фундаментальных механизмов мышления" Дугласа Хофстадтера