Sierpiński trójkąt jest zbiór punktów na płaszczyźnie, która jest wykonana zaczynając od jednego trójkąta wielokrotnie podziału trójkątów na cztery przystające trójkąty i usuwania trójkąt środkową. Prawo Trójkąt Sierpińskiego ma rogi na (0,0), (0,1)i (1,0), i wygląda następująco:

Niektóre równoważne definicje tego zestawu są następujące:

• Dla wszystkich punktów w nopisanym powyżej procesie n.

• Punkty (x,y)z 0 <= x <= 1i 0 <= y <= 1takie, że dla wszystkich dodatnich liczb całkowitych n, nth w binarnym rozwinięciu x i y nie są jednocześnie 1.

• Pozwolić T = {(0,0),(1,0),(0,1)}

  Niech fbędzie funkcją na zestawach punktów 2D zdefiniowanych przez:

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

  Wówczas prawo Trójkąt Sierpińskiego jest topologiczna zamknięcie z najmniej stałego punktu (o zadanej skażenia) z f.

• Niech Sbędzie kwadrat{(x,y) | 0<=x<=1 and 0<=y<=1}

  Niech g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}(gdzie Tjest jak zdefiniowano powyżej)

  Zatem prawy trójkąt Sierpińskiego jest największym stałym punktem g.

Wyzwanie

Napisz program lub funkcję, która akceptuje 4 liczby całkowite a,b,c,di podaje prawdziwą wartość, jeśli (a/b,c/d)należy do właściwego trójkąta Sierpińskiego, a poza tym daje wartość falsey.

Punktacja

To jest golf golfowy. Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

W prawym trójkącie Sierpińskiego znajdują się:

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

W prawym trójkącie Sierpińskiego nie ma następujących elementów:

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

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

Dobry sposób sprawdzenia, czy członkostwo w uszczelce jest brzydkie. Gdybyśmy mieli gwarancję, że dane wejściowe są nieujemne i w jednostce kwadratowej, mielibyśmy 38:

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

Chodzi o to, że sprawdzamy, czy punkt znajduje się w uszczelce, sprawdzając, czy ich ułamek binarny rozszerza się bitowo-ORAZ do 0. Aby uzyskać pierwszy kznak rozszerzenia, bitowo przesuwamy kbity licznika pozostawione przed podzieleniem liczb całkowitych przez mianownik . Musimy zrobić kwystarczająco duże, aby powtórzyć. Zauważamy, że rozszerzenie binarne n/dma co najwyżej okres d, więc wspólne rozszerzenia mają co najwyżej okres d*D, więc k=d*Dwystarczy.

Resztą jest sprawdzenie, czy ułamek znajduje się w pudełku i izolacja od danych wejściowych podanych w podobny sposób -1/-3.