The Sierpinski segitiga adalah satu set poin di pesawat yang dibangun dengan memulai dengan segitiga tunggal dan berulang kali membelah semua segitiga menjadi empat segitiga kongruen dan menghapus segitiga pusat. Segitiga Sierpinski kanan memiliki sudut di (0,0)
, (0,1)
dan (1,0)
, dan terlihat seperti ini:
Beberapa definisi yang setara dari set ini adalah sebagai berikut:
Poin dalam
n
iterasi proses yang dijelaskan di atas, untuk semuan
.Poin
(x,y)
dengan0 <= x <= 1
dan0 <= y <= 1
sedemikian rupa sehingga untuk semua bilangan bulat positifn
,n
bit th dalam ekspansi biner dari x dan y tidak keduanya1
.Membiarkan
T = {(0,0),(1,0),(0,1)}
Membiarkan
f
menjadi fungsi pada set poin 2D yang ditentukan oleh yang berikut ini:f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}
Kemudian segitiga Sierpinski kanan adalah penutupan topologi dari titik yang paling tidak pasti (dengan set kontainment) dari
f
.Membiarkan
S
menjadi persegi{(x,y) | 0<=x<=1 and 0<=y<=1}
Biarkan
g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}
(di manaT
seperti yang didefinisikan di atas)Maka segitiga Sierpinski kanan adalah titik tetap terbesar
g
.
Tantangan
Tulis program atau fungsi yang menerima 4 bilangan bulat, a,b,c,d
dan berikan nilai kebenaran jika (a/b,c/d)
milik segitiga Sierpinski kanan, dan jika tidak berikan nilai falsey.
Mencetak gol
Ini adalah kode golf. Kode terpendek dalam byte menang.
Uji kasus
Berikut ini adalah dalam segitiga Sierpinski kanan:
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
Berikut ini tidak dalam segitiga Sierpinski kanan:
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
sumber
-1 -3 1 1
input yang valid?Jawaban:
Python 2, 68
Cara yang bagus untuk memeriksa keanggotaan gasket dibuat jelek. Jika kami dijamin bahwa inputnya tidak negatif dan di unit square, kami akan memiliki 38:
Idenya adalah bahwa kita memeriksa apakah suatu titik terletak di dalam paking dengan memeriksa apakah fraksi biner mereka ekspansi bitwise-DAN ke 0. Untuk mendapatkan
k
karakter pertama dari ekspansi, kita menggeser-geserk
bit pembilang yang tersisa sebelum pembagi-bilangan bulat oleh penyebut. . Kita harus membuatk
ukuran yang cukup besar untuk mendapatkan pengulangan. Kami mencatat bahwa ekspansi binern/d
memiliki periode paling banyakd
, jadi ekspansi gabungan memiliki periode paling banyakd*D
, jadik=d*D
cukup.Sisanya adalah untuk memeriksa apakah fraksi ada di dalam kotak dan melindungi terhadap input yang diberikan seperti
-1/-3
.sumber