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

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 является постоянной последовательностью.

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

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

Answer 2

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

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

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

Answer 3

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

Вы можете взглянуть на этот пост Everything2 , который указывает на полином Лагранжа .

Answer 4

В книге Числовые рецепты есть страницы и страницы реальных практических алгоритмов для подобных вещей. Это стоит прочитать!

Первые два случая просты:

>>> 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 5

См. Также главу «Изыскивать, откуда приходит последовательность» из книги Дугласа Хофштадтера «Концепции текучих сред и творческие аналогии: компьютерные модели основных механизмов мышления»

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

Answer 6

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

У вас есть 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-го или любого другого). , , это просто простой пример.

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

Answer 7

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

Answer 8

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

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

Answer 9

Мне нравится, что идея и последовательность 1 и 2 могут показаться мне возможными, но, опять же, вы не можете обобщать, поскольку последовательность может полностью сойти с базы. Ответ, вероятно, заключается в том, что вы не можете обобщить, что вы можете сделать, это написать алгоритм для выполнения определенной последовательности, зная (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)

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