Алгоритм для поиска следующего числа в последовательности

Question

С тех пор, как я начал программировать, мне было любопытно. Но мне кажется слишком сложным даже попытать.

Хотелось бы увидеть решение.

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) 

Answer 1

То, что вы хотите сделать, называется полиномиальная интерполяция. Существует много методов (см. http://en.wikipedia.org/wiki/Polynomial_interpolation), но вы должны иметь верхнюю границу U от степени полинома и не менее U + 1 значений.

Если у вас есть последовательные значения, то есть простой алгоритм.

Учитывая последовательность x1, x2, x3, ..., пусть Delta (x) - последовательность разностей x2 - x1, x3 - x2, x4 - x3, .... Если у вас есть последовательные значения полинома степени n, то n-я итерация Delta является постоянной последовательностью.

Например, многочлен п^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, ... 

Ограничение на количество приведенных выше значений гарантирует, что ваша последовательность никогда не станет пустой при выполнении различий.

Answer 2

Жаль разочаровать, но это не вполне возможно (в целом), так как существует бесконечное число последовательностей для любых заданных значений k. Возможно, с определенными ограничениями.

Вы можете посмотреть сообщение Everything2, которое указывает на Lagrange polynomial.

Answer 3

Мне нравится идея и последовательность одного и двух, как мне кажется, что это возможно, но с другой стороны, вы не можете обобщить, так как последовательность может полностью покинуть базу. Ответ, вероятно, заключается в том, что вы не можете обобщить, что вы можете сделать, это написать алгоритм для выполнения определенной последовательности, зная (n + 1) или (2n + 2) и т. Д.

Одна вещь, do принимает разницу между элементом i и элементом i + 1 и элементом i + 2.

, например, в своем третьем примере:

10 17 31 59 115 

Разница между 17 и 10: 7, а разница между 31 и 17 составляет 14, а разница между 59 и 31 составляет 28, а diffeerence между 115 и 59 составляет 56.

Итак, обратите внимание, что он становится элементом i + 1 = i + (7 * 2^n).

Так 17 = 10 + (7 * 2^0)

И 31 = 17 + (7 * 2^1)

И так далее ...

Answer 4

Вы можете попробовать использование extrapolation. Это поможет вам найти формулы для описания данной последовательности.

Прошу прощения, я не могу сказать вам больше, поскольку мое математическое образование произошло довольно давно. Но вы должны найти больше информации в хороших книгах.

Answer 5

Такие серии номеров часто являются частью «тестов интеллекта», что заставляет меня думать в терминах такого алгоритма, что-то проходящее (по крайней мере, часть) Turing Test, чего трудно сделать.

Answer 6

Формально нет однозначного следующего значения для частичной последовательности. Задача, как обычно понимается, может быть четко обозначена как:

Предположим, что представленная частичная последовательность достаточно для ограничения некоторого правила генерации, выведите самое простое возможное правило и выведите следующее генерируемое значение.

Проблема включает значение «простейшего» и, следовательно, не очень хорошо подходит для алгоритмических решений. Это можно сделать, если ограничить проблему определенным классом функциональных форм для правила генерации, но детали зависят от форм, которые вы готовы принять.

Answer 7

В книге Numerical 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 

Третий случай потребует решения для нелинейной функции.

Answer 8

Для произвольной функции это невозможно, но для линейной функции, как в каждом из ваших примеров, достаточно просто.

У вас есть 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 

Раствор для является следующим: (. Вы хотите отдельно решить случай, когда f(0) = f(1), чтобы избежать деления на ноль)

a = (f(2)-f(1))/(f(1)-f(0)) 
b = f(1) - f(0)*(f(2)-f(1))/(f(1)-f(0)) 

Как только у вас есть a и b, вы можете повторно применять формулу к исходному значению для генерации любого члена в se ствие.

Можно также написать более общую процедуру, которая работает при задании любых трех точек в последовательности (например, 4-й, 7-й, 23-й или любой другой). , , это просто простой пример.

Опять же, мы должны были сделать некоторые предположения о том, какая форма будет иметь наше решение. , ,в этом случае считая его линейным, как в вашем примере. Можно считать, что это более общий полином, например, но в этом случае вам нужно больше термов последовательности, чтобы найти решение, в зависимости от степени полинома.

Answer 9

Смотрите также глава «искать откуда приходит в Sequence» из книги «Fluid понятий и творческих аналогий: компьютерные модели фундаментальных механизмов мышления» Дуглас Хофстадтер

http://portal.acm.org/citation.cfm?id=218753.218755&coll=GUIDE&dl=GUIDE&CFID=80584820&CFTOKEN=18842417