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
n
opisanym powyżej procesien
.Punkty
(x,y)
z0 <= x <= 1
i0 <= y <= 1
takie, że dla wszystkich dodatnich liczb całkowitychn
,n
th w binarnym rozwinięciu x i y nie są jednocześnie1
.Pozwolić
T = {(0,0),(1,0),(0,1)}
Niech
f
bę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
S
będzie kwadrat{(x,y) | 0<=x<=1 and 0<=y<=1}
Niech
g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}
(gdzieT
jest 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,d
i 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
źródło
-1 -3 1 1
jest poprawny wpis?Odpowiedzi:
Python 2, 68
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:
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
k
znak rozszerzenia, bitowo przesuwamyk
bity licznika pozostawione przed podzieleniem liczb całkowitych przez mianownik . Musimy zrobićk
wystarczająco duże, aby powtórzyć. Zauważamy, że rozszerzenie binarnen/d
ma co najwyżej okresd
, więc wspólne rozszerzenia mają co najwyżej okresd*D
, więck=d*D
wystarczy.Resztą jest sprawdzenie, czy ułamek znajduje się w pudełku i izolacja od danych wejściowych podanych w podobny sposób
-1/-3
.źródło