Tantangan
Untuk tantangan ini, Anda harus menentukan apakah angka yang diberikan ada dalam set Cantor. Jadi pertama-tama, mari kita tentukan set Cantor.
Pertama, mulailah dengan angka antara 0 dan 1. Angka apa pun di luar rentang ini tidak dalam set Penyedia. Sekarang, mari kita bagi angka menjadi tiga bagian yang sama: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Angka apa pun yang tidak di dalam rentang bagian pertama dan terakhir tidak ada dalam set Penyedia. Sekarang, Anda ulangi proses ini untuk segmen [0,1 / 3] dan [2/3, 1]. Kemudian Anda ulangi apa yang tersisa. Anda terus melakukan ini selamanya. Pada akhirnya, semua angka yang tersisa berada di set Cantor. Berikut adalah diagram dari enam iterasi pertama:
Memasukkan
Dua bilangan bulat x
dan y
.
0 < y < 2^15
0 <= x <= y
Penyebut umum terbesar dari x
dan y
adalah 1, kecuali x == 0
.
Keluaran
Jujur jika x/y
ada dalam set Penyedia .
Falsy jika x/y
tidak dalam set Cantor.
Contohnya
Sekarang, mari kita lihat beberapa contoh angka yang ada di set Cantor.
1/3 -> true
Itu ada di batas, dan batas tidak pernah dihapus.
1/4 -> true
1/4
tidak pernah di sepertiga tengah segmen, meskipun tidak pernah di perbatasan juga. Jika Anda mengikuti jalannya, Anda akan benar-benar menemukan bahwa itu bergantian antara berada di pertiga bagian pertama dan terakhir.
1/13 -> true
1/13
bergantian antara bagian pertama, pertama, dan terakhir.
1/5 -> false
1/5
jatuh ke blok kosong pertama dari baris ketiga dalam diagram di atas, antara 1/9 dan 2/9.
Kasus uji lainnya:
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false
Anda dapat mencoba nomor lain dengan cuplikan ini:
Objektif
Orang dengan byte terkecil menang.
sumber
x == 0
Jawaban:
Mathematica, 54 byte
Fungsi yang tidak disebutkan namanya mengambil sebagian kecil
x/y
sebagai input, di manay > 0
dan0 ≤ x ≤ y
, dan mengembalikanTrue
atauFalse
.Bilangan real antara 0 dan 1 ada di Cantor yang diatur tepat ketika tidak ada digit dalam ekspansi basis-3 yang sama dengan 1; pengecualian adalah bahwa fraksi yang penyebutnya berkekuatan 3 (yang ekspansi basis-3nya diakhiri) dibiarkan berakhir dalam angka 1.
RealDigits[#,3][[1]]
memberikan semua digit pada ekspansi basis-3 dari input fraksional#
, dalam bentuk seperti{1, 0, 2, {0, 1, 0, 2}}
: daftar terakhir adalah bagian periodik dari ekspansi, sedangkan bilangan bulat sebelumnya adalah digit sebelum periodisitas dimulai. Jika ekspansi base-3 periodik segera, outputnya seperti{{0, 1, 0, 2}}
; jika ekspansi basis-3 berakhir, bentuknya seperti{1, 0, 2}
.Jadi kami ingin memeriksa, menggunakan
~FreeQ~1
, apakah daftar itu bebas1
atau tidak. Namun, karena penghentian ekspansi hal, kami ingin menghapus elemen terakhir dari daftar jika sama1
; itulah yangIf[Last@#===1,Most@#,#]
berhasil. (===
Diperlukan untuk membandingkan daftar potensial dengan1
:==
sendirian tetap tidak dievaluasi dalam situasi itu.)sumber
IsCantorNumber
tetapi memiliki fungsi untuk menentukan sesuatu adalah kambing .FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
1
di bagian periodik, yang mengarah pada jawaban yang salah. Misalnya, ekspansi basis-3 dari 7/8 adalah .21212121 ...., atau{{2,1}}
; tetapi aturan yang disarankan akan mengubahnya menjadi{{2}}
, yang bebas dari1
tetapi tidak seharusnya.#==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&
? Jika itu berakhir dan bukan nolRealDigits[#,3]
akan menjadi bentuk{{__Integer},-1}
dan jika itu berulang akan menjadi bentuk{{___Integer,{__Integer}},-1}
, kan? Saya sedang menggunakan ponsel sehingga sulit untuk menguji sekarang. Jika ini berhasil, gunakan notasi infiks untukRealDigits
mungkin berfungsi juga.C (gcc) ,
615958 byteMengeksploitasi simetri set Cantor. Istirahat setelah
y
iterasi untuk menghindari infinite loop.Cobalah online!
sumber
Jelly ,
22171615 byteMencetak 3 untuk truey, tidak ada untuk falsy.
Cobalah online!
Latar Belakang
Properti terkenal dari set Cantor adalah bahwa ia mengandung angka-angka antara 0 dan 1 yang dapat ditulis tanpa 1 dalam ekspansi terner mereka.
Perhatikan bahwa beberapa angka - tepatnya tepi kanan dari interval tertutup yang terlibat dalam konstruksi himpunan - dapat ditulis dengan satu (trailing) 1 atau dengan jumlah trailing 2 yang tak terbatas . Sebagai contoh, 1 = 1 3 = 0,22222 ... 3 dan 1/3 = 0,1 3 = 0,022222 ... 3 , sama seperti 0,5 10 = 0,499999 ... 10 .
Untuk menghindari casing khusus tepi kanan, kita dapat memeriksa 1 adalah ekspansi desimal terpendek di kedua x / y dan 1 - x / y = (y - x) / y , di mana x / y adalah tepi kanan jika (y - x) / y adalah tepi kiri. Jika setidaknya salah satu dari mereka mengandung angka 1 , x / y adalah milik set Cantor.
Bagaimana itu bekerja
sumber
3
adalahtrue
+1 yang benar .JavaScript (ES6), 65
67Edit 2 byte disimpan thx @ Lukas
Kurang golf
Uji
sumber
n=n%d*3
denganq=n/d|0
dan kemudian menggantiz[n]
denganz[n=n%d*3]
JavaScript (ES6), 55 byte
Gunakan dengan mencari di penyebut pertama dan pembilang kedua. Bentuk standar adalah satu byte lebih panjang:
Penjelasan
Jika sebagian kecil tidak ada dalam set Penyedia, itu harus jatuh ke salah satu bagian tengah di beberapa titik; oleh karena itu, perwakilannya dalam basis 3 harus berisi angka 1 diikuti pada titik tertentu dengan angka bukan nol. Begitulah cara kerjanya:
z
melacak apakah kami telah menemukan 1.q
adalah digit saat ini di basis 3.!z|!q
benar jikaz
salah (kami belum menemukan 1) atauq
salah (digit saat ini adalah 0).Jika
n
berjalan ke nol sebelum kami menemukan angka bukan nol di suatu tempat setelah angka 1, fraksi ada di set Penyedia dan kami kembali1
.sumber
Utilitas Bash + GNU, 62 byte
Cobalah online!
Berikan dua argumen integer dengan arg1 <= arg2 dan 0 <arg2.
Output dikembalikan dalam kode keluar (0 untuk palsu, 1 untuk kebenaran), sebagaimana diizinkan oleh metode I / O PPCG .
Saya menduga regex dapat di-golf lebih jauh, bahkan mungkin menghilangkan perintah tr yang mendukung penggunaan grep -z, tetapi ini adalah yang terpendek yang dapat saya lakukan. (Sayangnya, grep -z tidak kompatibel dengan grep -P, dan opsi -P untuk mendapatkan reg-style perl diperlukan untuk sintaks?!).
Program dan keluaran Testbed:
Penjelasan
bagian dc (argumennya adalah x dan y):
tr dan grep bagian:
Masalah kecil adalah bahwa, meskipun dc menangani bilangan bulat besar yang sewenang-wenang, ketika dc mencetak angka besar, ia akan memecahnya menjadi garis-garis 69-karakter, dengan setiap baris kecuali akhir yang terakhir dengan garis miring terbalik, dan dengan baris baru setelah setiap baris.
Perintah tr menghapus sembarang garis miring terbalik dan baris baru. Ini hanya menyisakan satu baris.
Perintah grep kemudian menggunakan reg-style perl (opsi -P, yang merupakan ekstensi GNU). Regex cocok jika baris berisi 1 tidak diikuti oleh setidaknya y 0 atau paling tidak y 2 yang kemudian mengakhiri string.
Inilah yang diperlukan untuk mengidentifikasi x / y sebagai tidak berada dalam set Cantor, karena bagian berulang dari representasi basis-3 dari bilangan rasional x / y dapat dilihat sebagai mulai dari digit # y + 1 setelah titik ternary , dan paling lama y digit.
sumber
CJam (19 byte)
Test suite online
Ini adalah blok anonim (fungsi) yang mengambil dua argumen pada stack dan daun
0
atau1
pada stack. Ia bekerja dengan basis mengubah pecahanx/y
menjadi digity
basis3
dan mengembalikan true jika mereka tidak mengandung1
atau hanya1
merupakan bagian dari akhiran1 0 0 0 ...
.sumber
Pyth , 14 byte
Berdasarkan solusi C saya.
y
pada baris input pertama,x
kedua.Jika
x/y
berada dalam set Cantor,x
tetap di antara0
dany
. Kalau tidak,x
menjadi lebih besar dariy
pada satu titik, kemudian menyimpang ke infinity negatif dalam iterasi yang tersisa.Cobalah online!
sumber
Batch, 91 byte
Menguji
y-1
basis 3 digit pertamax/y
.i
adalah jumlah digit yang diuji.n
adalah nilai selanjutnya darix
.j
benar jikan
mencapai nol (karena ekspansi berakhir) atau kami telah mengujiy-1
digit tanpa menemukan a1
.f
bernilai true jikaj
benar atau jika digit berikutnya adalah a1
, pada titik mana kita menghentikan perulangan dan keluaranj
.sumber