Представьте себе прямую реку и дорогу, которая проходит через реку n раз через мосты. Дорога не петляет сама по себе и бесконечно длинна. Эта дорога будет считаться открытым меандром. Открыт меандром является открытой кривым, которая не пересекается с самими собой и простирается бесконечно на обоих концах, которые пересекают линию п раз.

Действительный меандр может быть полностью описан порядком точек пересечения, которые он посещает.

Число различных шаблонов пересечения с n пересечениями, которыми может быть меандр, является n-м меандрическим числом . Например, n = 4:

Первые несколько чисел этой последовательности:

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...

Это последовательность OEIS A005316 .

Вызов

Напишите программу / функцию, которая принимает положительное целое число n в качестве входных данных и печатает n-е меандрическое число .

Характеристики

• Стандартные правила ввода / выводаПрименяются .
• Стандартные лазейки будут запрещены .
• Ваше решение может быть либо 0-индексированным, либо 1-индексированным но укажите, какое именно.
• Эта задача не в том, чтобы найти кратчайший подход на всех языках, а в том, чтобы найти кратчайший подход на каждом языке. .
• Ваш код будет оцениваться в байтах , обычно в кодировке UTF-8, если не указано иное.
• Встроенные функции, которые вычисляют эту последовательность, разрешены но приветствуется решение, которое не зависит от встроенного.
• Пояснения, даже для «практических» языков, приветствуются .

Контрольные примеры

Это 0-индексированные. Обратите внимание, что вам не нужно обрабатывать такие большие числа, если ваш язык не может по умолчанию.

Input      Output

1          1
2          1
11         1828
14         30694
21         73424650
24         1649008456
31         5969806669034

В нескольких лучших форматах:

1 2 11 14 21 24 31
1, 2, 11, 14, 21, 24, 31

Python 3 , 208 188 187 184 180 177 171 байт

lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

Попробуйте онлайн!

Теперь 1-индексированный (ранее был 0-индексированный, но 1-индексный сохранил байт из-за удачной особенности поведения меандров).

объяснение

Это может быть то же самое, что и ссылка, опубликованная Jenny_mathy , но я не стал читать статью, так что это просто логика моего метода.

Я буду использовать следующую иллюстрацию, представленную на OEIS , чтобы визуализировать результаты.

Каждый действительный меандр может быть полностью описан порядком точек пересечения, которые он посещает. Это может быть тривиально наблюдается на изображении; входной сегмент всегда находится на одной стороне (иначе число будет двойным). Мы можем представить тенденцию сегментов входа и выхода к их соответствующим бесконечностям, просто добавляя к каждому ордеру точку с любой стороны, то есть ордер (2, 1, 0)станет (-1, 2, 1, 0, 3).

Имея это в виду, задача состоит в том, чтобы найти количество порядков или перестановок диапазона до n, которые не пересекаются между собой. Пересечения являются проблемой только между парами точек, для которых соединительный сегмент лежит на одной стороне. Для любых двух пар последовательных точек в перестановке, чьи сегменты имеют общую сторону, независимо от того, пересекаются они или нет, эквивалентно тому, находится ли одна и только одна из точек одной пары между двумя элементами другой пары. Таким образом, мы можем определить, является ли ордер действительным, если нет пар с одной точкой, содержащихся в другой паре с сегментом на той же стороне.

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

Haskell , 199 байт

1!x=x
-1!(-1:x)=1:x
n!(i:x)=i:(n-i)!x
0#([],[])=1
0#_=0
n#(a,b)=sum$((n-1)#)<$>(-1:a,-1:b):[(a,-i:b)|i:a<-[a]]++[(-j:a,b)|j:b<-[b]]++[(j!a,i!b)|i:a<-[a],j:b<-[b],i+j>=0]
f n=n#([],[-1,1])+n#([1],[1])

Попробуйте онлайн!

Основано на распространении идей Ивана Дженсена, « Перечень меандров плоскости» , 1999 г., на случай открытых меандров. Это проходит через n = 1,…, 16 примерно за 20 секунд на TIO.

APL (Дьялог Классик) , 127 115 байтов

⊃⊃⌽{↓⍉(⊃,/c),∘(+/)⌸(≢¨c←{1↓¨⍳¨⍨0,¨((×2↑¯1⌽⍵)/¯1 1⌽¨⊂⍵),(⊂∊#⍵#),(××/m,≠/m)/⊂1↓¯1↓(⊢-⍵×~)⍵∊m←2↑¯1⌽⍵}¨⊃⍵)/⊃⌽⍵}⍣⎕⌽1,⊂⍳2

Попробуйте онлайн!