Определить, находятся ли рациональные координаты в правом треугольнике Серпинского

9

Треугольник Серпинский представляет собой набор точек на плоскости , которая строится, начиная с одного треугольником и неоднократно разделив все треугольники на четыре конгруэнтных треугольники и удаление центрального треугольника. Право Серпинского треугольник имеет углы в (0,0), (0,1)и (1,0), и выглядит следующим образом :

Треугольник Серпинского

Некоторые эквивалентные определения этого набора следующие:

  • Очки в nитерации описанного выше процесса для всех n.

  • Точки (x,y)с 0 <= x <= 1и так 0 <= y <= 1, что для всех натуральных чисел n, nth-й бит в двоичном разложении x и y не совпадает 1.

  • Позволять T = {(0,0),(1,0),(0,1)}

    Позвольте fбыть функцией на наборах 2D точек, определяемых следующим:

    f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}

    Тогда правый Серпинский треугольник является топологическим замыканием по меньшей мере , неподвижной точки (по заданной локализации) из f.

  • Пусть Sбудет квадрат{(x,y) | 0<=x<=1 and 0<=y<=1}

    Позвольте g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}(где T, как определено выше)

    Тогда правый треугольник Серпинского является самой большой неподвижной точкой g.

Вызов

Напишите программу или функцию, которая принимает 4 целых числа a,b,c,dи дает истинное значение, если (a/b,c/d)принадлежит правому треугольнику Серпинского, а в противном случае дает ложное значение.

счет

Это код гольф. Самый короткий код в байтах побеждает.

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

В правом треугольнике Серпинского:

0 1 0 1
0 1 12345 123456
27 100 73 100
1 7 2 7
8 9 2 21
8 15 20 63
-1 -7 2 7

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

1 1 1 1
-1 100 1 3
1 3 1 3
1 23 1 7
4 63 3 66
58 217 4351 7577
-1 -7 3 7
code-golf fractal rational-numbers картонная коробка
источник
Является -1 -3 1 1действительным вход?
xnor
Да, это верный ввод. Я добавил тестовые случаи, чтобы прояснить это.
картонная

Ответы:

5

Python 2, 68

lambda n,d,N,D:1>=n/d>=0<=N/D<=1and(n<<abs(D*d))/d&(N<<abs(D*d))/D<1

Хороший способ проверить членство на прокладке, сделанный безобразным. Если бы мы были гарантированы, что входные данные неотрицательны и в единичном квадрате, у нас было бы 38:

lambda n,d,N,D:(n<<D*d)/d&(N<<D*d)/D<1

Идея состоит в том, что мы проверяем, находится ли точка внутри прокладки, проверяя, растянуты ли их двоичные дроби поразрядно-И до 0. Чтобы получить первый kсимвол расширения, мы сдвигаем kбиты числителя влево перед делением целого числа на знаменатель , Нам нужно сделать kдостаточно большой, чтобы поймать повторение. Отметим, что бинарное расширение n/dимеет период не более d, поэтому совместные расширения имеют период не более d*D, поэтому k=d*Dдостаточно.

Остальное, чтобы проверить, находится ли фракция в поле и изолировать от вводимых данных, как -1/-3.

XNOR
источник