Étant donné un nombre entier positif n, concevez un rapporteur avec le moins de marques qui vous permet de mesurer tous les angles qui sont un multiple entier de 2π/n(chacun dans une seule mesure).

Détails

En sortie, vous pouvez sortir une liste d'entiers dans la plage 0à n-1(ou 1à n) qui représentent la position de chaque marque. Alternativement, vous pouvez sortir une chaîne / liste de longueur navec un #à la position de chaque marque et un _(trait de soulignement) là où il n'y en a pas. (Ou deux caractères différents si cela vous convient plus.)
Exemple: Pour n = 5vous avez besoin exactement de 3 marques pour pouvoir mesurer tous les angles 2π/5, 4π/5, 6π/5, 8π/5, 2πen définissant (par exemple) une marque à 0, une marque à 2π/5et une marque à 6π/5. Nous pouvons coder cela sous forme de liste [0,1,3]ou de chaîne ##_#_.

Exemples

Notez que les sorties ne sont pas nécessairement uniques.

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: Ceci est similaire au problème de la règle clairsemée , mais au lieu d'une échelle linéaire (avec deux extrémités), nous considérons une échelle circulaire (angulaire).

PPS: ce script doit calculer un exemple d'un ensemble de marques pour chacun n. Essayez-le en ligne!

PPPS: Comme l'a souligné @ngn, ce problème équivaut à trouver une base de différence minimale d'un groupe cyclique d'ordre n. Les commandes minimales sont répertoriées dans http://oeis.org/A283297 et certaines limites théoriques se trouvent dans https://arxiv.org/pdf/1702.02631.pdf

Gelée , 13 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Œ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 octets

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

Cela manque de mémoire sur TIO pour les entrées au-delà 8.

Essayez-le en ligne!

Comment ça fonctionne

Cela génère la puissance cartésienne de [0 1 ... n-1]avec exposant net utilise une boucle pour tester chaque tuple cartésien. Le test consiste à calculer toutes les différences de paires d'éléments si le tuple, et de voir si ces différences modulo ncomprennent tous les nombres 0, 1..., n-1.

Dès qu'un tuple cartésien remplissant la condition est trouvé, la boucle est quittée et les entrées uniques de ce tuple sont imprimées comme solution.

Cela fonctionne car étant donné u > v , un ensemble suffisant de tuples avec u entrées uniques est garanti pour être testé plus tôt que tout tuple avec v entrées uniques. Un «ensemble suffisant» signifie que si aucun des tuples de cet ensemble n'est une solution, aucun autre tuple avec le même nombre d'entrées uniques n'est une solution.

Par exemple, pour n = 3les tuples cartésiens sont comme indiqué ci-dessous, où chaque ligne est un tuple:

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

• Le premier tuple,, 0 0 0est le seul tuple pertinent avec 1une valeur unique. Même si 1 1 1et 2 2 2apparaîtra beaucoup plus tard, 0 0 0est une solution si et seulement si c'est le cas. Ainsi, l'ensemble singleton formé par le tuple 0 0 0est un ensemble suffisant pour u = 1.
• Les deuxième et troisième tuples, à savoir 0 0 1et 0 0 2, forment un ensemble suffisant pour u = 2; c'est-à-dire qu'ils couvrent tous les cas avec 2des valeurs uniques. Le quatrième tuple,, 0 1 0ne sera jamais sélectionné comme solution, car 0 0 1il aura été testé en premier. De même, le tuple 0 2 0ne sera jamais sélectionné car il apparaît après 0 0 2. Des tuples tels que 2 2 1ne seront jamais sélectionnés comme solution car le 0 0 1est équivalent (modulo net jusqu'aux valeurs dupliquées) et apparaît en premier.
• Etc.

Code commenté:

: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 octets

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

Exécutez et déboguez en ligne!

À l'heure actuelle, la version en ligne échoue pour la saisie, 20mais ce bogue a été corrigé et doit encore être déployé sur l'interpréteur en ligne déployé. Attention, il faut du temps pour exécuter le 20dossier.

Explication

Il s'avère qu'en raison de la façon dont la différence par paire est calculée, je n'ai pas à me soucier de l'équivalence de ket x-kici. Enregistrement de 5 octets.

Utilise la version décompressée pour expliquer.

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.

En appliquant l'exigence selon laquelle 0et les 1deux doivent être membres de la réponse, nous pouvons générer le jeu de pouvoirs avec [2..x]au lieu de [0..x], puis ajouter le 0et 1manuellement à chaque élément du jeu de pouvoirs. Il est plus efficace mais doit gérer l'entrée en 1particulier et coûte plus d'octets.

Gelée , 17 octets

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

Essayez-le en ligne!

-1 octet merci à M. Xcoder

Python 2 , 148 octets

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

Essayez-le en ligne!