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

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

Спасибо!


person mring    schedule 03.06.2010    source источник
comment
Попробуйте определить шаблон здесь: 111314113612314...   -  person Hamish Grubijan    schedule 03.06.2010
comment
@Hamish, ответ: кумулятивная последовательность подсчета: метод A (прилагательное, существительное) - пары с первым термином 1. (Последовательность A055187)   -  person aioobe    schedule 03.06.2010
comment
Я проверил это на себе, я очень впечатлен. Я полагаю, что это просто гигантская база данных, которую они заполнили и по которой выполняют поиск. Было бы забавно использовать совершенно случайные последовательности для этой штуки. Хорошее шахматное программное обеспечение также имеет большую базу данных сохраненных позиций, ну, оно полагается на это, по крайней мере, частично.   -  person Hamish Grubijan    schedule 03.06.2010


Ответы (2)


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

Даны a1, a2, ..., an

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

P(i) = ai

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

Проверьте: http://en.wikipedia.org/wiki/Polynomial_interpolation

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

person Community    schedule 03.06.2010
comment
+1: Хороший вопрос. Учитывая список целых чисел, не существует абсолютно правильного ответа на вопрос «Какое следующее число в последовательности?». - person Troubadour; 03.06.2010
comment
Но полином имеет n параметров. С таким же успехом можно сказать, что P(i)=ai для i‹=n, P(i)=0 для i›n. Лучше задаться вопросом, какая формула дает эту последовательность с наименьшим количеством очевидных способов ее настройки для получения другой последовательности? - person Beta; 03.06.2010
comment
@Beta: «наименее очевидный» - очень субъективный термин, который не имеет смысла для компьютера, которому нужно придумать формулу. Может быть, вы можете дать ему определение и придать ему больше смысла... - person ; 03.06.2010

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

person aioobe    schedule 03.06.2010
comment
+1: у меня складывается впечатление, что это просто база данных, тем более что вы можете отправить последовательность. - person Troubadour; 03.06.2010
comment
Я застрял в своих лотерейных номерах, которые повторно использую каждую неделю, и это зашло в тупик. Наверное, потому что я еще не выиграл. - person Troubadour; 03.06.2010
comment
Ха, у них даже есть потерянные номера. Введите 4 8 15 16 23 42 - person mring; 03.06.2010