Какой будет хороший общий алгоритм для решения задач с целочисленными последовательностями?

Question

Скажем, что на входе всегда будет одно и то же число N чисел (например, 5) и предположим, что целые числа на самом деле имеют математическое отношение (без длин чисел 'один', 'два', дни в n-м месяце и т. Д. .). Результатом будет либо следующее целое число и обнаруженное правило, либо сообщение о том, что правило не может быть обнаружено. Я думал о том, чтобы иметь в порядке один-два-три модуль, который пытается найти правила арифметической последовательности, выполняя суммы и / или различия между числами, расположенными рядом, один, два и т. Д., Ищет шаблоны, а затем фокусирует модуль. для геометрических последовательностей путем умножения и / или деления таким же образом, а затем, если есть общий подход, модуль для обнаружения рекурсивных последовательностей.

Спасибо!

Answer 1

Онлайн-энциклопедия целочисленных последовательностей решает именно эту проблему: -)

Answer 2

Учитывая любую последовательность чисел, мы можем придумать формулу, которая «подходит»!

Учитывая a1, a2, ..., an

Все, что вам нужно сделать, это найти многочлен n-1 градуса (используя полиномиальную интерполяцию), чтобы

P (i) = ai

и все, у вас есть формула. Полиномиальная интерполяция может быть такой же простой, как решение матричного уравнения Ax = b (где A является матрицей Vandermonde ).

Выезд: http://en.wikipedia.org/wiki/Polynomial_interpolation

Это одна из причин, по которой я нахожу эти проблемы «угадать следующее число» несколько глупыми (читай: жалкие тесты IQ). Не все так думают.