Biorąc pod uwagę pewną dodatnią liczbę całkowitą n
, zaprojektuj kątomierz z najmniejszą liczbą znaczników, która pozwoli ci zmierzyć wszystkie kąty, które są integralną wielokrotnością 2π/n
(każdy w jednym pomiarze).
Detale
Jako wynik możesz wypisać listę liczb całkowitych z zakresu 0
do n-1
(lub 1
do n
), które reprezentują pozycję każdego znaku. Alternatywnie możesz wypisać ciąg / listę długości n
ze znakiem #
w pozycji każdego znaku i _
(podkreślenie) tam, gdzie go nie ma. (Lub dwa różne znaki, jeśli jest to wygodniejsze.)
Przykład: Aby n = 5
dokładnie zmierzyć wszystkie kąty, potrzebujesz dokładnie 3 znaków, 2π/5, 4π/5, 6π/5, 8π/5, 2π
ustawiając (na przykład) jeden znak o 0
, jeden znak o 2π/5
i jeden znak o 6π/5
. Możemy zakodować to jako listę [0,1,3]
lub ciąg znaków ##_#_
.
Przykłady
Zauważ, że wyniki niekoniecznie są unikalne.
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: Jest to podobne do problemu rzadkiej linijki , ale zamiast skali liniowej (z dwoma końcami) rozważamy skalę kołową (kątową).
PPS: Ten skrypt powinien obliczyć jeden przykład zestawu znaków dla każdego n
. Wypróbuj online!
PPPS: Jak wskazał @ngn, ten problem jest równoważny ze znalezieniem podstawy minimalnej różnicy w cyklicznej grupie zamówień n
. Minimalne zamówienia są wymienione w http://oeis.org/A283297, a niektóre teoretyczne granice znajdują się w https://arxiv.org/pdf/1702.02631.pdf
n = q^2 + q + 1
o moc pierwszorzędnąq
.Odpowiedzi:
Galaretka , 13 bajtów
Wypróbuj online!
Jak to działa
źródło
MATL , 20 bajtów
W przypadku TIO zabrakło pamięci na wejścia poza nią
8
.Wypróbuj online!
Jak to działa
To generuje potęgę kartezjańską
[0 1 ... n-1]
z wykładnikiem potęgin
i używa pętli do testowania każdej krotki kartezjańskiej. Badanie polega na obliczaniu wszystkie różnice parami pierwiastka jeśli krotki, i zobaczyć, czy te różnice modulon
obejmują wszystkie numery0
,1
, ...,n-1
.Gdy tylko krotka kartezjańska spełniająca warunek zostanie znaleziona, pętla zostanie zamknięta, a unikalne wpisy w krotce zostaną wydrukowane jako rozwiązanie.
To działa, ponieważ podane u > v , jest wystarczający zestaw krotek o kształcie U unikalnych wpisów zagwarantowane mają być testowane wcześniej niż krotki z v unikalnych wpisów. „Zestaw wystarczający” oznacza, że jeśli żadna z krotek w tym zestawie nie jest rozwiązaniem, to żadna inna kratka z taką samą liczbą unikalnych wpisów nie jest rozwiązaniem.
Na przykład dla
n = 3
krotek kartezjańskich są pokazane poniżej, gdzie każdy rząd jest krotką:0 0 0
jest jedyną odpowiednią krotką o1
unikalnej wartości. Nawet jeśli1 1 1
i2 2 2
pojawi się znacznie później,0 0 0
jest rozwiązaniem wtedy i tylko wtedy, gdy są. Tak więc zestaw singletonów utworzony przez krotkę0 0 0
jest wystarczającym zestawem dla u =1
.0 0 1
i0 0 2
, tworzą wystarczający zestaw dla u =2
; to znaczy, że obejmują one wszystkie przypadki o2
unikalnych wartościach. Czwarta krotka0 1 0
nigdy nie zostanie wybrana jako rozwiązanie, ponieważ0 0 1
najpierw zostanie przetestowana. Podobnie krotka0 2 0
nigdy nie zostanie wybrana, ponieważ pojawi się później niż0 0 2
. Krotki takie jak2 2 1
nigdy nie zostaną wybrane jako rozwiązanie, ponieważ0 0 1
jest równoważne (modulon
i do zduplikowanych wartości) i pojawia się jako pierwsze.Skomentowany kod:
źródło
Stax ,
2621 bajtówUruchom i debuguj online!
W tej chwili wersja online nietłumaczu wdrożonym. Uwaga: uruchomienie20
może zostać wprowadzona, ale ten błąd został naprawiony i nie został jeszcze wdrożony w internetowym20
sprawy zajmuje trochę czasu .Wyjaśnienie
Okazuje się, że ze względu na sposób obliczania różnicy par, nie muszę się martwić o równoważność
k
ix-k
tutaj. Zapisywanie 5 bajtów.Używa rozpakowanej wersji do wyjaśnienia.
Poprzez egzekwowanie wymogu,
0
a1
obie są członkami odpowiedź, możemy wygenerować PowerSet ze[2..x]
zamiast[0..x]
a następnie dodaj0
i1
ręcznie do każdego elementu w PowerSet. Jest bardziej wydajny, ale wymaga1
specjalnej obsługi danych wejściowych i kosztuje więcej bajtów.źródło
Galaretka , 17 bajtów
Wypróbuj online!
-1 bajt dzięki Mr. Xcoder
źródło
R
.Python 2 , 148 bajtów
Wypróbuj online!
źródło