Pertama, mari kita bicara tentang urutan Beatty . Diberikan bilangan irasional positif r , kita dapat membangun urutan tak terbatas dengan mengalikan bilangan bulat positif menjadi r dalam urutan dan mengambil dasar setiap perhitungan yang dihasilkan. Sebagai contoh,
Jika r > 1, kami memiliki kondisi khusus. Kita dapat membentuk nomor lain irasional s sebagai s = r / ( r - 1). Ini kemudian dapat menghasilkan urutan Beatty sendiri, B s . Trik rapi adalah bahwa B r dan B s adalah saling melengkapi , yang berarti bahwa setiap bilangan bulat positif adalah persis salah satu dari dua sekuens.
Jika kita menetapkan r = ϕ, rasio emas, maka kita mendapatkan s = r + 1, dan dua urutan khusus. The rendah Wythoff urut untuk r :
1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ...
dan urutan Wythoff atas untuk s :
2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ...
Ini adalah urutan A000201 dan A001950 di OEIS, masing-masing.
Tantangan
Diberikan integer input positif 1 <= n <= 1000
, output salah satu dari dua nilai berbeda yang menunjukkan apakah input berada di urutan Wythoff yang lebih rendah atau urutan atas . Nilai output dapat berupa -1
dan 1
, true
dan false
, upper
dan lower
, dll.
Meskipun algoritme yang Anda kirim harus bekerja secara teoritis untuk semua input, dalam praktiknya hanya bekerja dengan 1000 angka input pertama.
I / O dan Aturan
- Input dan output dapat diberikan dengan metode apa pun yang mudah .
- Input dan output dapat dianggap sesuai dengan jenis nomor asli bahasa Anda.
- Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
- Celah standar dilarang.
- Ini adalah kode-golf sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.
sumber
Jawaban:
JavaScript (ES6),
5035 byteOutput
1
untuk yang lebih rendah dan yang lebih0
tinggi. Penjelasan: daftar Partial nilai boolean dapat dibangun menggunakan Fibonacci seperti identitas: diberikan dua daftar, dimulai dengan1
dan10
, setiap daftar berikutnya adalah gabungan dari dua sebelumnya, sehingga101
,10110
,10110101
dll Dalam hal ini itu sedikit Golfier untuk memiliki entri 0 palsu0
dan menggunakannya untuk membangun elemen kedua dari daftar.sumber
Haskell , 26 byte
Cobalah online!
Tidak ada pelampung, presisi tak terbatas. Terima kasih atas H.PWiz untuk dua byte.
sumber
~(x:t)
. Terima kasihundefined
. Fakta bahwa ada dua definisi yang berbeda juga hanya kebetulan.Python , 25 byte
Cobalah online!
Gunakan kondisi yang sangat sederhana:
Perhatikan bahwa hasil modulo positif meskipun
-n
negatif, cocok dengan bagaimana Python melakukan modulo.Ini sesuai dengan kode ini:
Cobalah online!
Kami menyimpan byte dengan menggandakan ke
-(n*2)%(phi*2)<2
.sumber
05AB1E , 9 byte
Cobalah online!
0 berarti atas, 1 berarti lebih rendah. Coba 100 yang pertama: Coba online!
Dump Perintah Baku:
sumber
ï
:)5t>;
untuk byter 2 mungkin tidak sepadan ...ï
dan¢
lol :) Semua solusi kami sangat erat terkaitJelly , 5 byte
Cobalah online!
Disimpan 1 byte berkat xnor's Python golf .
Jelly , 6 byte
Cobalah online!
Mengembalikan 1 untuk lebih rendah dan 0 untuk atas.
sumber
Øp
5t>;
Brain-Flak , 78 byte
Cobalah online!
Output apa-apa untuk yang lebih rendah dan
0
atas. Mengubah skema output yang lebih masuk akal akan menelan biaya 6 byte.sumber
Python 2 ,
393332 byte-6 byte terima kasih kepada Tn. Xcoder
-1 byte terima kasih kepada Zacharý
Cobalah online!
Pengembalian
False
untuk yang lebih rendah danTrue
atassumber
lambda n,r=(1+5**.5)/2:-~n//r<n/r
menghemat 6 byte.lambda n,r=.5+5**.5/2:-~n//r<n/r
harus bekerja juga untuk mencukur satu byteJulia 0,6 , 16 byte
Cobalah online!
Sambil bermain-main dengan angka-angka, saya menemukan properti ini: lantai (n / φ) == lantai ((n + 1) / φ) jika n berada di urutan Wythoff atas, dan lantai (n / φ) <lantai ( (n + 1) / φ) jika n berada di urutan Wythoff yang lebih rendah. Saya belum menemukan bagaimana properti ini muncul, tetapi memberikan hasil yang benar setidaknya hingga n = 100000 (dan mungkin di luar).
Jawaban lama:
Julia 0,6 , 31 byte
Cobalah online!
Mengembalikan
true
untukfalse
urutan Wythoff yang lebih rendah dan atas.sumber
Pyth , 8 byte
Coba di sini!
Mengembalikan 1 untuk lebih rendah dan 0 untuk atas.
sumber
Bahasa Wolfram (Mathematica) , 26 byte
Cobalah online!
Integer
n
ada di Wythoff Sequence iffceil(n/phi) - 1/phi < n/phi
.Bukti itu
ceil(n/phi) - 1/phi < n/phi
adalah ...Cukup:
Mari
ceil(n/phi) - 1/phi < n/phi
.Lalu
ceil(n/phi) * phi < n + 1
,.Catatan
n == n/phi * phi <= ceil(n/phi) * phi
.Karenanya
n <= ceil(n/phi) * phi < n + 1
,.Karena
n
danceil(n/phi)
bilangan bulat, kami menerapkan definisi lantai dan negara bagianfloor(ceil(n/phi) * phi) == n
, dann
berada dalam urutan Wythoff yang lebih rendah.Perlu; bukti oleh kontrapositif:
Mari
ceil(n/phi) - 1/phi >= n/phi
.Lalu
ceil(n/phi) * phi >= n + 1
,.Catatan
n + phi > (n/phi + 1) * phi > ceil(n/phi) * phi
Oleh karena itu
n > (ceil(n/phi) - 1) * phi
.Karena
(ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi
,n
tidak dalam urutan Wythoff yang lebih rendah.sumber
Japt , 10 byte
Mengembalikan nilai true untuk lower dan false untuk upper.
Cobalah online!
Penjelasan:
sumber
Java 10,
775352 bytePelabuhan @ Rod's Python 2 menjawab .
-1 byte terima kasih kepada @ Zacharý .
Cobalah online.
Tua
Jawaban7776 byte:-1 byte terima kasih @ovs untuk sesuatu yang saya rekomendasikan sendiri minggu lalu .. xD
Pengembalian
1
untuk yang lebih rendah;0
untuk atas.Cobalah online.
Penjelasan:
i*Phi
dihitung dengan mengambil(sqrt(5)+1)/2 * i
, dan kami kemudian lantai itu dengan melemparkannya ke integer untuk memotong desimal.sumber
++i<=n
pada jawaban lama Anda bisai++<n
.n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;}
Haskell ,
15313912679 bytePresisi Tanpa Batas!
Cobalah online!
Penjelasan
Alih-alih menggunakan perkiraan rasio emas untuk menghitung makna hasil, mereka cenderung mengalami kesalahan saat ukuran input naik. Jawaban ini tidak. Sebaliknya ia menggunakan rumus yang disediakan pada OEIS yang
a
merupakan urutan unik sehinggadi mana
b
pujian dipesan.sumber
Brachylog , 8 byte
Cobalah online!
Predikat berhasil jika input berada di urutan Wythoff yang lebih rendah dan gagal jika berada di urutan Wythoff atas.
Jika kegagalan untuk mengakhiri adalah metode output yang valid, byte pertama dapat dihilangkan.
sumber
φ
digunakan dalam program Brachylog. Akhirnya!MATL , 8 byte
Cobalah online!
Penjelasan
sumber
K (oK) , 20 byte
Larutan:
Cobalah online!
Penjelasan:
sumber
TI-BASIC (TI-84), 18 byte
Input di
Ans
.Keluaran dalam
Ans
dan secara otomatis dicetak.Mencetak
1
jika input berada di urutan bawah atau0
jika berada di urutan atas.Contoh:
Penjelasan:
Catatan: TI-BASIC adalah bahasa tokenized. Jumlah karakter tidak sama dengan jumlah byte.
sumber
cQuents , 5 byte
Cobalah online!
Penjelasan
sumber