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 0do n-1(lub 1do n), które reprezentują pozycję każdego znaku. Alternatywnie możesz wypisać ciąg / listę długości nze 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 = 5dokł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π/5i 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

Galaretka , 13 bajtów

ŒPðṗ2I%QLðÐṀḢ

Wypróbuj online!

Jak to działa

ŒPðṗ2I%QLðÐṀḢ  Main link. Argument: n (integer)

ŒP             Powerset; generate all subsequences of [1, ..., n].
  ð       ÐṀ   Begin a dyadic chain. Call it with all subsequences S as left
               argument and n as right one. Return the array of all sequences for
               which the chain returns the maximal result, i.e., [0, ..., n-1].
   ṗ2              Cartesian power 2; generate all pairs of elements of S.
     I             Increments; map each pair [x, y] to [y-x].
      %            Map each [y-x] to [(y-x)%n].
       Q           Unique; deduplicate the array of modular difference singletons.
        L          Take the length.
         ð     Begin a new, dyadic chain.
               Left argument: S' (filted subsequences). Right argument: n
            Ḣ  Take the first element of S'.
               Since S was sorted by length, so is S', so the first element of S'
               is the shortest subsequence that satisfies the condition.

MATL , 20 bajtów

:qGZ^!"G:q@&-G\m?@u.

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ęgi ni 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 modulo nobejmują wszystkie numery 0, 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 = 3krotek kartezjańskich są pokazane poniżej, gdzie każdy rząd jest krotką:

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
 ···
2 2 1
2 2 2

• Pierwsza krotka 0 0 0jest jedyną odpowiednią krotką o 1unikalnej wartości. Nawet jeśli 1 1 1i 2 2 2pojawi się znacznie później, 0 0 0jest rozwiązaniem wtedy i tylko wtedy, gdy są. Tak więc zestaw singletonów utworzony przez krotkę 0 0 0jest wystarczającym zestawem dla u = 1.
• Druga i trzecia krotka, mianowicie 0 0 1i 0 0 2, tworzą wystarczający zestaw dla u = 2; to znaczy, że obejmują one wszystkie przypadki o 2unikalnych wartościach. Czwarta krotka 0 1 0nigdy nie zostanie wybrana jako rozwiązanie, ponieważ 0 0 1najpierw zostanie przetestowana. Podobnie krotka 0 2 0nigdy nie zostanie wybrana, ponieważ pojawi się później niż 0 0 2. Krotki takie jak 2 2 1nigdy nie zostaną wybrane jako rozwiązanie, ponieważ 0 0 1jest równoważne (modulo ni do zduplikowanych wartości) i pojawia się jako pierwsze.
• Itp.

Skomentowany kod:

:q         % Push [0 1 ... n-1], where n is the input (implicit)
GZ^        % Cartesian power with exponent n. Gives an (n^n) × n matrix
           % where each row is a Cartesian tuple
!          % Transpose. Now each Cartesian tuple is a column
!"         % For each column (that is, each Cartesian tuple)
  G:q      %   Push [0 1 ... n-1] (*)
  @        %   Push current column
  &-       %   Matrix of pairwise differences (**)
  G\       %   Modulo n, element-wise
  m        %   Ismember function: for each entry in (*), gives true iff
           %   it is present in (**)
  ?        %   If all entries are true
    @      %     Push current column
    u      %     Unique entries. This is the solution
    .      %     Break loop
           %   End (implicit)
           % End (implicit)
           % Display (implicit)

Stax , 26 21 bajtów

Åæ4&╕u◙╩►s∙Φ▬═(0~ d+Q

Uruchom i debuguj online!

W tej chwili wersja online nie 20może zostać wprowadzona, ale ten błąd został naprawiony i nie został jeszcze wdrożony w internetowym tłumaczu wdrożonym. Uwaga: uruchomienie 20sprawy 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ść ki x-ktutaj. Zapisywanie 5 bajtów.

Używa rozpakowanej wersji do wyjaśnienia.

rS{%o~{;i@c:2{E-x%mu%x<wm
r                            [0..`x`], where `x` is input
 S                           Powerset
  {%o~                       Sort by length
      {;i@             w     For each element in the powerset
          c:2                All pairs
             {    m          Map each pair `[p,q] to
              E-                 `q-p`
                x%               `(q-p)%x`
                   u%        Count of unique modulo differences
                     x<      Loop until the count of unique modulo differences is larger than the input(`n`)
                             Now we have found a valid set in the powerset
                        m    Output the members of the set,one element per line.

Poprzez egzekwowanie wymogu, 0a 1obie są członkami odpowiedź, możemy wygenerować PowerSet ze [2..x]zamiast [0..x]a następnie dodaj 0i 1ręcznie do każdego elementu w PowerSet. Jest bardziej wydajny, ale wymaga 1specjalnej obsługi danych wejściowych i kosztuje więcej bajtów.

Galaretka , 17 bajtów

_þ¹F%³³Ḷ¤ḟ
ŒPÇÐḟḢ

Wypróbuj online!

-1 bajt dzięki Mr. Xcoder

Python 2 , 148 bajtów

from itertools import*
def f(n):
 r=range(n)
 for i in r:
  for p in combinations(r,i+1):
   if all(any((y+x)%n in p for y in p)for x in r):return p

Wypróbuj online!