양의 정수가 주어지면 n
적분 배수 2π/n
(각각 단일 측정) 인 모든 각도를 측정 할 수있는 마크 수가 가장 적은 각도기를 설계하십시오 .
세부
출력으로, 각 마크의 위치를 나타내는 0
~ n-1
(또는 1
~ n
) 범위의 정수 목록을 출력 할 수 있습니다 . 또는 당신 출력 길이의 문자열 / 나열 할 수 있습니다 n
A를을 #
각 마크의 위치와 _
어느 곳 (밑줄)이 없습니다. (더 편리하면 두 개의 다른 문자가 있습니다.)
예 : ( 예 를 들어)에서 하나의 마크를 , 하나의 마크를 및 하나의 마크를 설정하여 n = 5
모든 각도를 측정 할 수 있으려면 정확히 3 개의 마크가 필요합니다 . 이것을리스트 나 문자열로 인코딩 할 수 있습니다 .2π/5, 4π/5, 6π/5, 8π/5, 2π
0
2π/5
6π/5
[0,1,3]
##_#_
예
출력이 반드시 고유하지는 않습니다.
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]
추신 : 이것은 희소 눈금자 문제 와 비슷 하지만 선형 스케일 (두 끝이있는) 대신 원형 (각도) 스케일을 고려합니다.
PPS :이 스크립트는 각각에 대한 마크 세트의 한 예를 계산해야합니다 n
. 온라인으로 사용해보십시오!
PPPS : @ngn이 지적했듯이이 문제는 순환 순서 그룹의 최소 차이 기반을 찾는 것과 같습니다 n
. 최소 주문은 http://oeis.org/A283297 에 나열되어 있으며 일부 이론적 범위는 https://arxiv.org/pdf/1702.02631.pdf 에 있습니다.
답변
젤리 , 13 바이트
ŒPðṗ2I%QLðÐṀḢ
작동 원리
Œ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 바이트
:qGZ^!"G:q@&-G\m?@u.
이 이상의 입력에 대한 TIO의 메모리가 부족 8
합니다.
작동 원리
이것은 [0 1 ... n-1]
지수가 있는 데카르트 힘을 생성하고 n
루프를 사용하여 각 데카르트 튜플을 테스트합니다. 시험은 튜플 경우 요소의 모든 페어의 차이를 계산하고, 그 차이가 모듈로하면보고에서 구성 n
을 포함 하는 모든 숫자 0
, 1
, …, n-1
.
조건을 충족시키는 데카르트 튜플이 발견되면 루프가 종료 되고 해당 튜플 의 고유 한 항목이 솔루션으로 인쇄됩니다.
주어진 때문에이 작품 U > V에게 하는 충분한 세트 와 튜플의 유 독특한 항목을 테스트 할 보장 이전의 어떤 튜플에 비해 V 고유 한 항목. “충분한 세트”는 해당 세트의 튜플이 솔루션이 아닌 경우 동일한 수의 고유 항목을 가진 다른 튜플이 솔루션이 아님을 의미합니다.
예를 들어, n = 3
데카르트 튜플의 경우 각 행이 튜플 인 다음과 같습니다.
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
- 첫 번째 튜플
0 0 0
은1
고유 한 값을 가진 유일한 관련 튜플입니다 . 해도1 1 1
와2 2 2
훨씬 나중에 나타납니다,0 0 0
그이있는 경우에만 경우 솔루션입니다. 따라서 튜플에 의해 형성된 싱글 톤 세트0 0 0
는 u =에 충분한 세트입니다1
. - 두 번째 및 세 번째 튜플, 즉
0 0 1
및0 0 2
를위한 충분한 세트를 형성 유 =2
; 즉, 모든2
값 을 고유 한 값으로 처리합니다. 네 번째 튜플0 1 0
은0 0 1
먼저 테스트되었으므로 솔루션으로 선택되지 않습니다 . 마찬가지로 튜플0 2 0
은 이후에 표시되므로 선택되지 않습니다0 0 2
. 와 같은 튜플2 2 1
은 솔루션으로 선택되지 않으며0 0 1
(모듈로n
및 중복 된 값까지) 먼저 나타납니다. - 기타.
주석이 달린 코드 :
: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 바이트
Åæ4&╕u◙╩►s∙Φ▬═(0~ d+Q
현재 온라인 버전에서 입력에 실패 배포 20
했지만이 버그가 수정되어 온라인 인터프리터에되지 않았습니다 . 20
사례 를 실행하는 데 시간이 걸립니다 .
설명
쌍별 차이가 계산되는 방식으로 인해 여기서 k
와 동등한 것에 대해 걱정할 필요가 없습니다 x-k
. 5 바이트 절약
압축을 푼 버전을 사용하여 설명합니다.
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.
그 요구 사항을 적용하여 0
하고 1
모두하는 답의 구성원을 우리는 함께 파워 셋을 생성 할 수 있습니다 [2..x]
대신 [0..x]
를 추가 다음과 0
하고 1
수동으로 파워 셋의 모든 요소에. 더 효율적이지만 입력을 1
특수하게 처리해야 하며 더 많은 바이트 가 필요 합니다.
답변
답변
파이썬 2 , 148 바이트
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