Dengan bilangan bulat positif n
, rancang busur derajat dengan jumlah tanda paling sedikit yang memungkinkan Anda mengukur semua sudut yang merupakan kelipatan integral 2π/n
(masing-masing dalam satu pengukuran tunggal).
Detail
Sebagai output, Anda dapat menampilkan daftar bilangan bulat dalam rentang 0
ke n-1
(atau 1
ke n
) yang mewakili posisi setiap tanda. Atau Anda dapat menampilkan string / daftar panjang n
dengan #
di posisi masing-masing tanda dan _
(garis bawah) di mana tidak ada. (Atau dua karakter berbeda jika lebih mudah.)
Contoh: Untuk n = 5
Anda membutuhkan tepat 3 tanda untuk dapat mengukur semua sudut 2π/5, 4π/5, 6π/5, 8π/5, 2π
dengan mengatur (misalnya) satu tanda pada 0
, satu tanda pada 2π/5
dan satu tanda pada 6π/5
. Kami dapat menyandikan ini sebagai daftar [0,1,3]
atau sebagai string ##_#_
.
Contohnya
Perhatikan bahwa output tidak harus unik.
n: output:
1 [0]
2 [0,1]
3 [0,1]
4 [0,1,2]
5 [0,1,2]
6 [0,1,3]
7 [0,1,3]
8 [0,1,2,4]
9 [0,1,3,4]
10 [0,1,3,6]
11 [0,1,3,8]
20 [0,1,2,3,6,10]
PS: Ini mirip dengan masalah penggaris jarang , tetapi alih-alih skala linier (dengan dua ujung) kami menganggap skala melingkar (sudut).
PPS: Skrip ini harus menghitung satu contoh dari serangkaian tanda untuk masing-masing n
. Cobalah online!
PPPS: Seperti yang ditunjukkan oleh @ngn, masalah ini setara dengan menemukan basis perbedaan minimal dari grup urutan siklik n
. Pesanan minimal tercantum di http://oeis.org/A283297 dan beberapa batasan teoretis ditemukan di https://arxiv.org/pdf/1702.02631.pdf
n = q^2 + q + 1
untuk kekuatan utamaq
.Jawaban:
Jelly , 13 byte
Cobalah online!
Bagaimana itu bekerja
sumber
MATL , 20 byte
Ini kehabisan memori pada TIO untuk input di luar
8
.Cobalah online!
Bagaimana itu bekerja
Ini menghasilkan kekuatan Cartesian
[0 1 ... n-1]
dengan eksponenn
, dan menggunakan loop untuk menguji setiap tuple Cartesian. Tes terdiri dalam menghitung semua perbedaan berpasangan elemen jika tupel, dan melihat jika perbedaan modulon
termasuk semua nomor0
,1
, ...,n-1
.Segera setelah tuple Cartesian memenuhi persyaratan ditemukan loop keluar, dan entri unik dalam tuple dicetak sebagai solusi.
Ini berfungsi karena mengingat u > v , satu set tupel yang cukup dengan u entri unik dijamin akan diuji lebih awal daripada tupel dengan v entri unik. "Set yang memadai" berarti bahwa jika tidak ada tupel dalam set tersebut yang merupakan solusi, maka tidak ada tuple lain dengan jumlah entri unik yang sama adalah solusi.
Misalnya, untuk
n = 3
tupel Cartesian adalah seperti yang ditunjukkan di bawah ini, di mana setiap baris adalah tupel:0 0 0
,, adalah satu-satunya tuple yang relevan dengan1
nilai unik. Bahkan jika1 1 1
dan2 2 2
akan muncul jauh kemudian,0 0 0
adalah solusi jika dan hanya jika ada. Jadi set singleton yang dibentuk oleh tuple0 0 0
adalah set yang cukup untuk u =1
.0 0 1
dan0 0 2
, membentuk set yang cukup untuk u =2
; yaitu, mereka menutupi semua kasing dengan2
nilai unik. Tuple keempat,,0 1 0
tidak akan pernah dipilih sebagai solusi, karena0 0 1
akan telah diuji terlebih dahulu. Demikian pula, tuple0 2 0
tidak akan pernah dipilih karena muncul paling lambat0 0 2
. Tuples seperti2 2 1
tidak akan pernah dipilih sebagai solusi karena0 0 1
setara (modulon
dan hingga nilai duplikat) dan muncul terlebih dahulu.Kode yang dikomentari:
sumber
Stax ,
2621 byteJalankan dan debug online!
Saat ini versi online gagal untuk inputDigunakan. Hati-hati, butuh waktu untuk menjalankan20
tetapi bug ini telah diperbaiki dan belum akan digunakan untuk penerjemah online yang20
kasing.Penjelasan
Ternyata karena perbedaan cara berpasangan dihitung, saya tidak perlu khawatir tentang kesetaraan
k
dan dix-k
sini. Menyimpan 5 byte.Gunakan versi yang belum dibongkar untuk menjelaskan.
Dengan memberlakukan persyaratan yang
0
dan1
keduanya menjadi anggota dari jawaban, kita dapat menghasilkan PowerSet dengan[2..x]
alih - alih[0..x]
lalu menambahkan0
dan1
secara manual ke setiap elemen di PowerSet. Ini lebih efisien tetapi perlu menangani input1
khusus dan biaya lebih banyak byte.sumber
Jelly , 17 byte
Cobalah online!
-1 byte terima kasih kepada Tn. Xcoder
sumber
R
.Python 2 , 148 byte
Cobalah online!
sumber