태그 보관물: integer-partitions

integer-partitions

피 실레 번호 / | \

OEIS의 Evolution 작업 중에이 시퀀스를 찾았 지만 답으로 게시하지 않았습니다. Mathematica에서 참조 구현을 작성한 후에는 이것이 별도의 도전으로 할 수있는 재미있는 운동이라고 생각했습니다.

수치 핵분열 원자로를 건설합시다! 양의 정수를 고려하십시오 N. 예를 들어을 살펴 보겠습니다 24. 이 숫자를 핵분열시키기 위해서는 합이되는 가장 큰 연속 양수 를 찾아야합니다 N. 이 경우에는입니다 7 + 8 + 9 = 24. 그래서 우리는 24세 개의 새로운 숫자로 나 ve 습니다. 그러나 이것은 연쇄 반응이없는 핵분열 원자로가 아닙니다. 따라서 이러한 구성 요소에 대한 프로세스를 반복적으로 반복합시다.

       24
       /|\
      / | \
     /  |  \
    7   8   9
   / \     /|\
  3   4   / | \
 / \     /  |  \
1   2   2   3   4
           / \
          1   2

숫자를 더 작은 연속 정수로 분해 할 수 없을 때마다 프로세스를 중지합니다. 또한 우리가 쓴 수 있습니다 9으로 4 + 5하지만, 2 + 3 + 4이상의 구성 요소가 있습니다. 분열 횟수N현재 포함한이 공정에서 얻어진 정수 개수로 정의된다 N자체. 위의 트리에는 13 개의 노드가 F(24) = 13있습니다.

이 순서는 OEIS 항목 A256504 입니다.

에서 시작하는 처음 40 개의 용어 N = 1

1, 1, 3, 1, 5, 6, 5, 1, 6, 7, 12, 10, 12, 11, 12, 1, 8, 16, 14, 17, 18, 18,
23, 13, 21, 18, 22, 23, 24, 19, 14, 1, 22, 20, 23, 24, 31, 27, 25, 26

첫 번째 1000 개의 용어는 이 pastebin에서 찾을 수 있습니다 .

도전

양의 정수가 주어지면 N핵분열 수를 결정하십시오 F(N). (따라서 0OEIS에 나와 있는 주요 내용을 다룰 필요는 없습니다 .)

STDIN (또는 가장 가까운 대안), 명령 행 인수 또는 함수 인수를 통해 입력을 받고 STDOUT (또는 가장 가까운 대안), 함수 리턴 값 또는 함수 (out) 매개 변수를 통해 결과를 출력하는 프로그램 또는 함수를 작성할 수 있습니다.

이것은 코드 골프이므로 가장 짧은 대답 (바이트)이 이깁니다.

보너스 질문 : 이 시퀀스의 흥미로운 속성을 찾을 수 있습니까?



답변

Pyth, 23 22 21 바이트

Lh&lJfqbsT.:tUb)syMeJ

이것은 재귀 함수를 정의합니다 y. 온라인으로 사용해보십시오 : 데모

설명:

L                      define a function y(b): return ...
            tUb          the list [1, 2, ..., b-1]
          .:   )         generate all consecutive sub-sequences
     f                   filter for sub-sequences T, which satisfy:
      qbsT                   b == sum(T)
    J                    and store them in J

                         return
   lJ                        len(J)
  &                        and (if len(J) == 0 then 0 else ...)
                    eJ       last element of J (=longest sub-sequence)
                  yM         recursive calls for all these numbers
                 s           sum
 h                         incremented by one (counting the current node)


답변

분열 , 1328 989 887 797 바이트

이 답변은 부당하게 길다 (우리가 접을 수있는 지역 이 있었으면 좋겠다 ) … 이걸 지나서 스크롤하고 다른 답변에 사랑을 보여주십시오.

이 코드를 다루는 것이이 도전에 영감을주었습니다. EOEIS에 Fission에 대한 답변을 추가하고 싶었습니다. 그러나 실제로 Fission을 배우고이를 구현하는 데 몇 주가 걸렸습니다. 그 사이에 시퀀스가 ​​실제로 커져서 별도의 챌린지를 게시하기로 결정했습니다. (그리고 이것은 어쨌든 EOEIS의 트리에서 그리 멀지 않았습니다).

나는 당신에게 괴물을 선물합니다.

 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
9\   ;    7A9
SQS  {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \  D /8/
~4X /A@[  %5                   /; &    K  } [S//~KSA /
  3    \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ { +X
W7           X  X    /> \      +\ A\ /   \ /6~@/ \/
        /   ~A\;     +;\      /@
    ZX [K    / {/  / @  @ }  \ X @
       \AS   </      \V /    }SZS S/
         X   ;;@\   /;X  /> \ ; X X
 ;       \@+  >/ }$S SZS\+;    //\V
           / \\  /\; X X @  @  \~K{
           \0X /     /~/V\V /   0W//
    \        Z      [K \  //\
W       /MJ $$\\ /\7\A  /;7/\/ /
       4}K~@\ &]    @\  3/\
 /     \{   }$A/1 2  }Y~K <\
[{/\  ;@\@  /   \@<+@^   1;}++@S68
@\ <\    2        ;   \    /
$  ;}++ +++++++L
%@A{/
M  \@+>/
~     @
SNR'0YK
  \  A!/

입력에 후행 줄 바꿈이 없을 것으로 예상하므로 다음과 같이 호출 할 수 echo -n 120 | ./Fission oeis256504.fis있습니다.

레이아웃은 여전히 ​​더 효율적일 수 있으므로 여기에는 여전히 개선의 여지가 많이 있다고 생각합니다 (예 : 여기에는 911 581 461 374 개의 공백 이 포함되어 있음 ).

설명을하기 전에 이것을 테스트 할 때주의해야합니다. 공식 통역사 는 전적으로 작동하지 않습니다. a) Mirror.cpp많은 시스템에서 컴파일되지 않습니다. 해당 문제가 발생하면 문제를 일으키는 행을 주석 처리하십시오. 영향을받는 구성 요소 (임의 미러)는이 코드에서 사용되지 않습니다. b) 정의되지 않은 동작으로 이어질 수있는 몇 가지 버그가 있습니다 (이 복잡한 프로그램의 경우). 이 패치 를 적용 하여 수정할 수 있습니다. 일단 그렇게하면, 인터프리터를 컴파일 할 수 있어야합니다.

g++ -g --std=c++11 *.cpp -o Fission

재미있는 사실 :이 프로그램은 #(랜덤 미러), :(하프 미러) -또는 |(일반 미러) 및 "(인쇄 모드)를 제외하고 Fission이 제공해야하는 거의 모든 구성 요소를 사용 합니다.

지구상에서 무엇?

경고 : 이 과정은 꽤 길어질 것입니다 … 저는 여러분이 Fission의 작동 방식과 프로그래밍 방법에 진심으로 관심이 있다고 가정합니다. 당신이 확실하지 않다면, 나는 이것을 어떻게 요약 할 수 있는지 잘 모르겠습니다. (다음 단락에서는 언어에 대한 일반적인 설명을 제공합니다.)

핵분열은 2 차원 프로그래밍 언어로, 데이터와 제어 흐름 모두 그리드를 통해 움직이는 원자로 표시됩니다 . 이전에 Marbelous 를 보거나 사용한 적이 있다면 그 개념은 모호하게 익숙해야합니다. 각 원자에는 음이 아닌 질량과 임의의 에너지라는 두 가지 정수 속성이 있습니다. 질량이 음수가되면 그리드에서 원자가 제거됩니다. 대부분의 경우 질량을 원자의 “값”으로 간주하고 에너지를 원자의 흐름을 결정하기 위해 여러 구성 요소에서 사용하는 일종의 메타 속성으로 취급 할 수 있습니다 (즉, 대부분의 스위치는 에너지). (m,E)필요한 경우 원자를로 표시 합니다. 프로그램이 시작될 때 그리드는(1,0)네 가지 구성 요소의 어느 위치에서든 원자 UDLR(문자는 원자가 처음에 움직이는 방향을 나타냄). 그런 다음 보드 에는 원자의 질량과 에너지를 바꾸거나 방향을 바꾸거나 더 정교한 작업을 수행하는 구성 요소가 모두 포함되어 있습니다. 전체 목록을 보려면 esolangs 페이지를 참조하십시오. 그러나이 설명에서 대부분을 소개하겠습니다. 프로그램이 여러 번 사용하는 또 다른 중요한 점은 격자가 환상 형이라는 점입니다. 어떤면에 부딪친 원자가 반대 방향으로 다시 나타나고 같은 방향으로 움직입니다.

프로그램을 여러 개의 작은 부분으로 작성하고 마지막에 모아서 설명을하겠습니다.

atoi

이 구성 요소는 다소 흥미롭지 않을 수 있지만 훌륭하고 간단하며 Fission의 산술 및 제어 흐름의 중요한 개념을 많이 소개 할 수 있습니다. 따라서이 부분을 아주 세밀하게 다룰 것이므로 다른 부분을 줄여 새로운 핵분열 역학을 도입하고 세부적인 제어 흐름을 수행 할 수있는 고급 구성 요소를 찾아 낼 수 있습니다.

분열은 정수가 아닌 개별 문자의 바이트 값만 읽을 수 있습니다. 그것이 여기 에서 용납 할 수있는 연습이지만 , 내가있는 동안 나는 그것을 올바르게하고 STDIN의 실제 정수를 구문 분석 할 수 있다고 생각했습니다. atoi코드 는 다음과 같습니다 .

     ;
 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
           O

핵분열에서 가장 중요한 두 성분은 핵분열 및 핵융합로입니다. 핵분열 원자로 임의이다 V^<>(위의 코드를 사용 <하고 >). 핵분열 원자는 원자를 (캐릭터의 웨지로 보내서) 기본값으로을 저장할 수 있습니다 (2,0). 원자가 캐릭터의 정점에 닿으면 두 개의 새로운 원자가 측면으로 보내집니다. 그들의 질량은 들어오는 질량을 저장된 질량으로 나눠서 결정합니다 (즉, 기본적으로 반으로 줄임). 왼쪽으로가는 원자는이 값을 얻고, 오른쪽으로가는 원자는 질량의 나머지를 얻습니다 (즉, 질량은 분열에 보존 됨) . 나가는 원자 둘 다 들어오는 에너지 빼기저장된 에너지. 이것은 우리가 산술에 핵분열 원자로를 사용할 수 있음을 의미합니다. 핵분열로가 현장에서 닿으면 원자는 단순히 대각선으로 반사되어 캐릭터의 정점 방향으로 움직입니다.

핵융합은 임의이다 YA{}(위의 코드를 사용 Y하고 {). 그들의 기능은 비슷합니다 : 그들은 원자를 저장할 수 있으며 (기본값 (1,0)) 정점에서 충돌하면 두 개의 새로운 원자가 측면으로 보내집니다. 그러나이 경우 두 원자는 동일하며 항상 들어오는 에너지를 유지하고 들어오는 질량에 저장된 질량을 곱합니다. 즉, 기본적으로 핵융합 반응기는 정점에 닿은 원자를 복제합니다. 측면에서 공격 할 때, 융합 원자로는 좀 더 복잡 : 원자는 또한원자가 반대편에 닿을 때까지 (다른 메모리와 독립적으로) 저장됩니다. 그것이 일어날 때, 새로운 원자는 질량과 에너지가 두 개의 오래된 원자의 합인 정점 방향으로 방출됩니다. 일치하는 원자가 반대편에 도달하기 전에 새 원자가 같은면에 닿으면 기존 원자를 덮어 씁니다. 융합 반응기는 덧셈 및 곱셈을 구현하는 데 사용될 수 있습니다.

내가 비켜 할 또 다른 간단한 구성 요소입니다 [그리고 ]이는 단순히 오른쪽에있는 원자의 방향을 설정하고 (관계없이 들어오는 방향의) 각각 떠났다. 수직 등가물은 M(아래쪽) 및 W(위쪽)이지만 atoi코드 에는 사용되지 않습니다 . 초기 원자를 방출 한 후에도 UDLR작용 WM][합니다.

어쨌든 코드를 살펴 보자. 이 프로그램은 5 개의 원자로 시작합니다.

  • RL하단에 간단하게 (과의 대량 증가 얻을 +)이 될 (10,0)다음 각각 핵분열과 핵융합에 저장됩니다. 이 리액터를 사용하여 base-10 입력을 구문 분석합니다.
  • L오른쪽 상단은 질량 (도착으로 감소 _되기) (0,0)및 핵융합 측에 저장된다 Y. 이것은 우리가 읽고있는 숫자를 추적하는 것입니다. 숫자를 읽을 때 점차적으로 증가하고 곱할 것입니다.
  • R왼쪽 상단 모서리에있는 그것의 질량의 문자 코드로 설정됩니다 0(48)와 '0다음 질량과 에너지로 바뀌 었는지, @그리고 마지막으로 대량 한 번에 증가 +(1,48). 그 다음 대각선 거울 리디렉션 \/핵분열 원자로에 저장한다. 우리는을 사용합니다 48숫자의 실제 값에 ASCII 입력을 설정하는 공제. 또한 1로 나누지 않기 위해 질량을 늘려야 했습니다 0.
  • 마지막으로, U왼쪽 하단 모서리는 실제로 모든 동작을 설정하고 처음에는 제어 흐름에만 사용됩니다.

오른쪽으로 방향을 바꾼 후, 제어 원자가 충돌 ?합니다. 이것은 입력 구성 요소입니다. 문자를 읽고 원자의 질량을 읽은 ASCII 값으로 설정하고 에너지를로 설정 0합니다. 대신 EOF를 누르면 에너지가로 설정됩니다 1.

원자는 계속되고 때린다 %. 이것은 미러 스위치입니다. 비 양성 에너지의 경우 /거울 처럼 작동합니다 . 그러나 긍정적 인 에너지의 경우 에너지처럼 작용 \하며 에너지를 1만큼 감소시킵니다. 문자를 읽는 동안 원자는 위쪽으로 반사되어 문자를 처리 할 수 ​​있습니다. 그러나 입력을 마치면 원자가 아래쪽으로 반사되고 다른 논리를 적용하여 결과를 검색 할 수 있습니다. 참고로, 반대 성분은 &입니다.

우리는 지금 원자가 움직이고 있습니다. 각 문자에 대해 원하는 것은 숫자 값을 읽고이를 누적 합계에 더한 다음 그 합계에 10을 곱하여 다음 숫자를 준비하는 것입니다.

캐릭터 원자는 먼저 (기본) 퓨전 리액터에 충돌합니다 Y. 이렇게하면 원자가 분할되고 왼쪽으로 이동하는 사본을 제어 원자로 사용하여 입력 구성 요소로 되돌아가 다음 문자를 읽습니다. 올바른 사본이 처리됩니다. 우리가 문자를 읽은 경우를 고려하십시오 3. 우리의 원자 될 것입니다 (51,0). 질량과 에너지를와 교환 @하여 다음 핵분열 원자로의 빼기를 이용할 수 있습니다. 원자로 48는 에너지를 빼고 (질량을 바꾸지 않고) 두 개의 사본을 보냅니다 (0,3). 에너지는 이제 읽은 숫자에 해당합니다. 다가오는 사본은 단순히 ;모든 들어오는 원자를 파괴하는 구성 요소로 버려집니다 . 우리는 계속해서 다운 사본으로 작업 할 것입니다. 당신은 통해 경로를 따라야합니다/그리고 \약간의 거울.

@직전 핵융합로는 우리가 추가 할 것 같은 것을 다시 질량과 에너지를 교환합니다 (3,0)우리의 누적 합계로 Y. 따라서 누적 합계 자체에는 항상 0에너지가 있습니다.

이제 J점프입니다. 그것이하는 일은 에너지로 들어오는 원자를 앞으로 뛰어 넘는 것입니다. 인 경우 0원자는 계속 직진합니다. 그렇다면 1하나의 셀을 2건너 뛰고 두 개의 셀을 건너 뛸 수 있습니다. 에너지는 점프에 소비되므로 원자는 항상 에너지로 끝납니다 0. 누적 합계의 에너지가 0이므로 현재 점프는 무시되고 원자는 핵융합 반응기로 재 지정되며,이 원자에 {질량을 곱합니다 10. 다운 고잉 카피는 폐기 ;되고, 업 고잉 카피는 Y새로운 누적 합계로서 반응기로 다시 공급된다 .

위의 내용은 EOF에 도달 할 때까지 계속 반복됩니다 (이전 숫자가 처리되기 전에 새로운 숫자가 처리되는 재미있는 파이프 라인 방식으로). 이제는 %원자를 아래쪽으로 보냅니다. 아이디어는 (0,1)총 원자로에 도달하기 전에이 원자를 지금 으로 바꾸어 a) 총계가 영향을받지 않고 (제로 질량) b) 우리는 1을 뛰어 넘을 에너지를 얻는 것이다 [. 로 에너지를 쉽게 관리 할 수있어 에너지가 $증가합니다.

문제는 ?EOF를 칠 때 질량을 재설정하지 않기 때문에 질량은 여전히 ​​마지막 문자 읽기의 질량이되고 에너지는 0( 뒤로 %감소 하기 때문에 )입니다. 그래서 우리는 그 질량을 제거하고 싶습니다. 이를 위해 우리는 질량과 에너지를 다시 교환 합니다.10@

이 섹션을 마치기 전에 하나 이상의 구성 요소를 소개해야합니다 Z. 이것은 본질적으로 동일하다 %&. 차이점은 양의 에너지 원자가 에너지를 감소시키면서 직선으로 통과하게하고 비 양성 에너지의 원자는 왼쪽으로 90도 편향 시킨다는 것입니다. 이것을 사용하여 원자의 에너지를 반복해서 반복함으로써 원자의 에너지를 제거 할 수 있습니다 Z. 에너지가 사라지면 원자는 편향되어 루프를 떠납니다. 이것이이 패턴입니다 :

/ \
[Z/

에너지가 0이되면 원자가 위로 이동합니다. 이 패턴을 프로그램의 다른 부분에서 한 형태로 여러 번 사용합니다.

원자는이 작은 루프를 남긴다 그래서 때, 그것은 것입니다 (1,0)및로 스왑 (0,1)바이 @입력의 최종 결과를 발표 할 융합 반응기를 타격하기 전에. 그러나 우리는 이미 다른 숫자에 대해 곱하기 때문에 누적 합계는 10 배가됩니다.

이제 에너지 1로이 원자는를 건너 뛰고 [로 뛰어들 것 /입니다. 이것은 우리가 핵분열 반응기로 편향 시켜서 우리가 10으로 나누고 외적 곱셈을 고치기 위해 준비했습니다. 다시, 우리는 절반을 버리고 다른 하나 ;를 출력으로 유지합니다 (여기서 표현 O하면 해당 문자를 단순히 인쇄하고 원자를 파괴합니다-전체 프로그램에서 원자를 대신 사용합니다).

itoa

           /     \
input ->  [{/\  ;@
          @\ <\
          $  ;}++ +++++++L
          %@A{/
          M  \@+>/
          ~     @
          SNR'0YK
            \  A!/

물론 결과를 다시 문자열로 변환하여 인쇄해야합니다. 이것이 바로이 부분입니다. 이것은 입력이 틱 10 정도 전에 도착하지 않지만 쉽게 제공되는 전체 프로그램으로 도착한다고 가정합니다. 이 비트는 전체 프로그램의 하단에서 찾을 수 있습니다.

이 코드는 새로운 매우 강력한 핵분열 성분 인 stack을 소개 K합니다. 스택은 처음에 비어 있습니다. 음이 아닌 에너지를 가진 원자가 스택에 닿으면 원자는 단순히 스택으로 밀립니다. 음의 에너지를 가진 원자가 스택에 도달하면 질량과 에너지는 스택의 상단에있는 원자로 대체됩니다 (따라서 터짐). 그래도 스택이 비어 있으면 원자의 방향이 바뀌고 에너지가 양이됩니다 (즉, 곱하기 -1).

자, 실제 코드로 돌아갑니다. itoa스 니펫 의 아이디어는 다음 반복을 위해 입력을 10으로 정수로 나누면서 다음 자리를 찾기 위해 입력 모듈로 10을 반복적으로 취하는 것입니다. 이렇게하면 모든 자릿수가 역순으로 표시됩니다 (최하위에서 최상위까지). 순서를 수정하기 위해 모든 숫자를 스택에 넣고 끝까지 하나씩 인쇄하여 인쇄합니다.

코드의 상단 절반은 숫자 계산을 수행합니다. L더하기 (+)를 사용하면 복제하고 핵분열과 핵융합로로 공급하는 10을 제공하므로 10을 나누고 곱할 수 있습니다. 루프는 기본적으로 [왼쪽 상단에서 시작합니다 . . 현재 값은 분할됩니다. 한 사본에 10을 나눈 다음 10을 곱한 후 핵분열 반응기에 저장 한 다음 정점에서 다른 사본에 부딪칩니다. 이것은로 계산 i % 10됩니다 i - ((i/10) * 10). 또한 A나누기 후와 곱하기 전에 중간 결과를 나누 i / 10므로 다음 반복에 피드 할 수 있습니다 .

%이 다소간 DO-while 루프이기 때문에 반복 변수가 0에 도달하면,이 코드도 인쇄 작업 것이다 루프를 중단 0(선두 제로를 별도로 만들지 않고). 루프를 떠나면 스택을 비우고 숫자를 인쇄하려고합니다. S의 반대이므로 Z, 양의 비 에너지로 들어오는 원자를 오른쪽으로 90도 돌리는 스위치입니다. 따라서 원자는 실제로 모서리에서 S직선으로 이동 K하여 숫자가 튀어 나오게합니다 ( ~이를 통해 들어오는 원자에 에너지가 있음을 확인하십시오 -1). 해당 숫자는 48해당 숫자의 ASCII 코드를 얻기 위해 증가 합니다. A분할이 숫자는 하나 개의 사본을 인쇄하기!그리고 다른 사본을 Y다음 자리 의 반응기 로 다시 공급하십시오 . 인쇄 된 사본은 스택의 다음 트리거로 사용됩니다 (미러는 또한 M왼쪽에서 닿도록 가장자리 주위로 전송합니다 ).

스택이 비면 K원자는 원자를 반사하고 에너지를으로 변환 +1하여을 통과합니다 S. N줄 바꿈을 인쇄합니다 (단지 깔끔하기 때문에). 그리고 원자는 R'0다시 옆으로 Y갑니다. 주변에 더 이상 원자가 없기 때문에 결코 해제되지 않고 프로그램이 종료됩니다.

분열 수 계산 : 프레임 워크

프로그램의 실제 고기를 보자. 코드는 기본적으로 Mathematica 참조 구현의 포트입니다.

fission[n_] := If[
  (div =
    SelectFirst[
      Reverse@Divisors[2 n],
      (OddQ@# == IntegerQ[n/#]
       && n/# > (# - 1)/2) &
    ]
  ) == 1,
  1,
  1 + Total[fission /@ (Range@div + n/div - (div + 1)/2)]
]

여기서 div최대 파티션의 정수 수입니다.

주요 차이점은 Fission에서 반정 수 값을 처리 할 수 ​​없으므로 2를 곱한 많은 작업을 수행하고 Fission에는 재귀가 없다는 것입니다. 이 문제를 해결하기 위해 큐에서 파티션의 모든 정수를 푸시하여 나중에 처리합니다. 처리하는 각 번호에 대해 카운터를 하나씩 증가시키고 대기열이 비면 카운터를 해제하여 인쇄를 위해 발송합니다. 대기열 은 FIFO 순서 Q와 똑같이 작동합니다 K.

이 개념의 프레임 워크는 다음과 같습니다.

                      +--- input goes in here
                      v

                     SQS ---> compute div from n          D /8/
                     ~4X               |                /~KSA /
                       3               +----------->    { +X
initial trigger ---> W                               6~@/ \/
                              4
                     W        ^                     /
                              |              3
                     ^     generate range    |
                     |     from n and div  <-+----- S6
                     |         -then-
                     +---- release new trigger

가장 중요한 새로운 구성 요소는 숫자입니다. 이들은 텔레 포터입니다. 숫자가 같은 모든 텔레 포터는 함께 속해 있습니다. 원자가 텔레 포터에 부딪히면 같은 그룹에서 다음 텔레 포터를 즉시 이동 시키며, 여기서 다음 은 일반적인 왼쪽에서 오른쪽, 위에서 아래 순서로 결정됩니다. 이것들은 필요하지 않지만 레이아웃에 도움이됩니다 (따라서 약간의 골프를 치십시오). 또한이 X단순히 똑바로하고 다른 뒤로 사본을 보내 원자를 복제한다.

이제는 대부분의 프레임 워크를 직접 정렬 할 수 있습니다. 왼쪽 상단에는 처리 할 값 대기열이 있으며 한 번 n에 하나씩 해제 됩니다. 하나의 사본은 n범위를 계산할 때 필요하기 때문에 맨 아래로 순간 이동되고 다른 사본은 맨 위의 블록으로 이동합니다 div(이것은 코드의 가장 큰 단일 섹션입니다). 일단 div계산 되면 복제됩니다. 한 사본은 오른쪽 상단에 카운터를 증분하여에 저장됩니다 K. 다른 사본은 맨 아래로 순간 이동됩니다. divwas 1인 경우 즉시 위쪽으로 편향시키고 새 값을 큐에 넣지 않고 다음 반복의 트리거로 사용합니다. 그렇지 않으면 우리가 사용 div하고n 하단의 섹션에서 새 범위 (즉, 큐에 배치되는 해당 질량을 가진 원자 스트림)를 생성 한 다음 범위가 완료된 후 새 트리거를 해제합니다.

대기열이 비면 트리거가 반영되어 S오른쪽 상단에 똑바로 지나가고 오른쪽 상단에 다시 나타나 카운터가 (최종 결과)를 해제 A한 다음 itoavia 로 순간 이동됩니다 8.

분열 수 계산 : 루프 바디

남은 것은 div범위 를 계산 하고 생성하는 두 섹션 입니다. 컴퓨팅 div은이 부분입니다.

 ;
 {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \
/A@[  %5                   /; &    K  } [S/
   \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \
         X  X    /> \      +\ A\ /   \ /
    /   ~A\;     +;\      /@
ZX [K    / {/  / @  @ }  \ X @
   \AS   </      \V /    }SZS S/
     X   ;;@\   /;X  /> \ ; X X
     \@+  >/ }$S SZS\+;    //\V
       / \\  /\; X X @  @  \~K{
       \0X /     /~/V\V /   0W//
\        Z      [K \  //\
           \ /\7\A  /;7/\/

아마도 인내심을 가지고 스스로를 해결할 수있을만큼 충분히 보았을 것입니다. 높은 수준의 분석은 다음과 같습니다. 처음 12 개 열은 약수의 제수를 생성합니다 2n. 다음 10 개의 열은 만족하지 않는 열을 필터링합니다 OddQ@# == IntegerQ[n/#]. 다음 8 개의 열은 만족하지 않는 열을 필터링합니다 n/# > (# - 1)/2). 마지막으로 유효한 모든 제수를 스택에 넣고 완료되면 전체 스택을 융합 반응기로 비우고 (마지막 / 최대 제수를 제외한 모든 것을 덮어 씁니다) 결과를 방출 한 다음 에너지를 제거합니다 부등식을 확인하는 -zero).

실제로 아무것도하지 않는 많은 미친 길이 있습니다. 주로 \/\/\/\/상단 의 광기 ( 5들도 그 일부 임)와 하단 주위의 한 경로 ( 7s를 통과하는 경로 ). 나는 불쾌한 경쟁 조건을 처리하기 위해 이것을 추가해야했습니다. 핵분열은 지연 성분을 사용할 수 있습니다 …

새로운 범위를 생성하는 코드 는 다음 ndiv같습니다.

 /MJ $$\
4}K~@\ &]    @\  3/\
\{   }$A/1 2  }Y~K <\
 \@  /   \@<+@^   1;}++@
  2        ;   \    /

먼저 계산하고 n/div - (div + 1)/2(두 층 모두 동일한 결과를 산출 함) 나중에 저장합니다. 그런 다음 div아래에서 범위를 생성 1하고 저장된 값을 각각에 추가합니다.

이 두 가지 모두에 두 가지 새로운 공통 패턴이 있습니다. 하나는 아래에서 SX또는 ZX히트 (또는 회전 된 버전)입니다. 이 방법은 하나의 사본을 똑바로 진행하려는 경우 원자를 복제 할 수있는 좋은 방법입니다 (융합 반응기의 출력을 리디렉션하는 것이 때때로 번거로울 수 있기 때문에). S또는 Z로 원자를 회전 X하고 위로 전파의 원래 방향으로 미러 카피를 회전시킨다.

다른 패턴은

[K
\A --> output

값을 저장 하면 상단에서 음의 에너지를 K쳐서 반복적으로 검색 할 수 있습니다 K. A중복 값을 우리는 관심과 우리가 다음에 필요할 때를위한 스택에 바로 다시 복사 무엇을 보냅니다.

글쎄요, 그건 꽤 큰 주제 였지만 … 만약 당신이 실제로 이것을 통과했다면, 당신은 Fission i͝s̢̘̗̗ ͢i̟nç̮̩r̸̭̬̱͔e̟̹̟̜͟d̙i̠͙͎̖͓̯b̘̠͎̭̰̼l̶̪̙̮̥̮y̠̠͎̺͜ ͚̬̮f̟͞u̱̦̰͍n͍ ̜̠̙t̸̳̩̝o ̫͉̙͠ṕ̢̢̢̯̱̭̱̭̜̙̙̤̙r̢̙r̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢̢͍͔̘̟̤̜̜̤̜̙̜̙̜̤̙̜̙̤̙̙̙̙̤̙̜̙̙̤̙̜̙̙̤̙̜̙̤̙̜̙̤̙̜̙̙̙̳̭͔̙̙̙̳̭͔̳̭͔̳̭͔̙̙̳̭͔̳̭͔̳̭͔̙̳̭͔̳̭͔ͅͅͅͅͅͅͅͅͅͅB̳̭͔ͅB͍͔̘̟ͅB͍͔̘̟ͅB͍͔̘̟ͅB͍͔̘̟ͅB̫̞B͍͔̘̟ͅB͍͔̘̟ͅB̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̗̳͇̹B̢̙B̗̳͇̹B̳̭͔ͅB̗̳͇̹B̢̙B̗̳͇̹B̢̙B̢̙B̢̙B̢̙B̢̙B̳̭͔ͅB̢̙B̳̭͔ͅB̢̙B̳̭͔ͅB̢̙B̳̭͔ͅB̢̙B̳̭͔ͅB̢̙B̢̙B̢̙B̢̙B̳̭͔ͅB̳̭͔ͅB̳̭͔ͅB̳̭͔ͅB̳̭͔ͅB̳B̳B̳B̳B̳B̳̭͔ͅB̳B̳B̳B̳B̳B̳B̳B̳B̳B̳B̳B̳B̳B̳B̳̗̳͇̹̳


답변

CJam, 42 41 바이트

ri]{_{:X,:)_few:+W%{1bX=}=}%{,(},e_}h]e_,

간단한 너비 우선 순회 및 다음 레벨이 비어있는 정지 조건.

작동 방식 :

ri]                                       e# This represents the root of the fissile tree
   {                               }h     e# Now we run a do-while loop
    _{                    }%              e# Copy the nodes at the current level and map them
                                          e# via this code block to get next level nodes
      :X,:)                               e# Store the node value in X and get array [1..X]
           _few                           e# Copy the array and get continuous slices of
                                          e# length 1 through X from the array [1..X]
               :+W%                       e# Right now, we have an array of array with each
                                          e# array containing slice of same length. We join
                                          e# those arrays and reverse them to get slices of
                                          e# higher length in front of lower lengths
                   {1bX=}=                e# Choose the first slice whose sum is same as X
                                          e# The reversal above makes sure that we give
                                          e# preference to slice of higher length in case of
                                          e# multiple slices add up to X
                            {,(},         e# Filter out slices of length 1 which basically
                                          e# mean that the current node cannot be split up
                                 e_       e# Join all slices in a single array. This is our
                                          e# next level in the Fissile tree. If this is empty
                                          e# it means that all no further node can be
                                          e# decomposed. In an {}h do-while loop, this fact
                                          e# itself becomes the stopping condition for the
                                          e# loop
                                     ]e_, e# Wrap all levels in an array. Flatten the array
                                          e# and take its length

여기에서 온라인으로 사용해보십시오


답변

파이썬 3, 112 바이트

def f(n,c=0):
 d=n-c;s=(n-d*~-d/2)/d
 return(s%1or s<1)and f(n,c+1)or+(d<2)or-~sum(f(int(s)+i)for i in range(d))

@FryAmTheEggman 덕분에 4 바이트가 절약되었습니다.

나중에 설명 …

보너스 사실 : 2의 모든 거듭 제곱은 1의 핵분열 수를 갖습니다. 이는 짝수 길이 시퀀스의 합이 항상 두 중간 숫자의 합이므로 홀수, 시퀀스 길이의 절반을 곱한 정수입니다. . 홀수 길이 시퀀스의 합은 중간 길이에 시퀀스 길이를 곱한 값이며 홀수입니다. 따라서 2의 거듭 제곱에는 홀수 제수가 없으므로 자체 합으로 만 표현할 수 있습니다.


답변

파이썬 (2), 111 (102) 97 바이트

다소 읽기 쉬운 :

def f(n,c=0):a=n-c;b=n-a*~-a/2;return 1/a or-~sum(map(f,range(b/a,b/a+a)))if b>b%a<1else f(n,c+1)

읽을 수없는 내용 :

def f(n,a=0):b=n-a*~-a/2;return b>0and(f(n,a+1)or b%a<1and(1/a or-~sum(map(f,range(b/a,b/a+a)))))

두 97 바이트

b는 IS n마이너스를 (a-1)th삼각형 수. 경우 b % a == 0, 다음 n의 합계입니다 a부터 연속 번호 b.


답변

파이썬 2, 86

f=lambda n,R={1}:n-sum(R)and f(n,R^{[min(R),max(R)+1][n>sum(R)]})or-~sum(map(f,R-{n}))

덜 골프 :

def f(n,R={1}):
    d=sum(R)-n
    if d==0:return (sum(map(f,R-{n}))
    if d<0:return f(n,R|{max(R)+1})
    if d>0:return f(n,R-{min(R)})

아이디어는에 합산되는 연속 정수의 잠재적 실행을 테스트하는 것입니다 n. 실행은 R엔드 포인트를 통하지 않고 세트로 직접 저장됩니다 .

우리는 현재 런의 합계 n가 차이를 통해 원하는 합계 와 어떻게 비교되는지 확인합니다 .

  • 합이 너무 크면 런에서 가장 작은 요소를 자릅니다.
  • 합이 너무 작 으면 최대 값을 1만큼 크게하여 런을 연장합니다.
  • 합이 정확하면 재귀 f하고 실행에 매핑 하고 합산하여 현재 노드에 1을 더합니다. run이 {n}인 경우 사소한 가능한 합계를 모두 시도한 후 n먼저 제거하여 재귀를 중지하십시오 .

3자를 절약 한 Sp3000에 감사합니다.


답변

파이썬 2, 85

이 답변은 n = 9의 경우 수십 초가 걸리고 n = 10의 경우 5-10 분이 걸리기 때문에이 답변을 매우 자랑스럽게 생각합니다. 코드 골프에서 이것은 프로그램의 바람직한 속성으로 간주됩니다.

f=lambda n,a=1,d=1:a/n or[f(a)+f(n-a,1+1%d*a)+1/d,f(n,a+d/n,d%n+1)][2*n!=-~d*(2*a+d)]

너무 오래 걸리지 않고 동일한 양의 바이트를 사용하는 단락 버전도 있습니다.

f=lambda n,a=1,d=1:a/n or~d*(2*a+d)+n*2and f(n,a+d/n,d%n+1)or f(a)+f(n-a,1+1%d*a)+1/d 

더 빠를 수 있지만 n이 40을 약간 초과하면 최소한 기본 재귀 제한을 초과합니다.

아이디어는 숫자에 대한 무력 검색하는 것입니다 ad같은 것을 a + a+1 + ... + a+d == n1 사이의 값을, n. f(n,a+d/n,d%n+1)재귀 의 분기는 (a, d)쌍을 통해 반복됩니다 . 평등이 충족되는 경우 map(range(...))시퀀스 길이에 관계없이 두 개의 지점으로 분할 하여 비싼 통화 를 피할 수 있습니다. 매개 변수 를 설정 하여 시퀀스를 나누는 다른 방법을 사용할 수 없도록 한 번의 호출로 숫자 a+1d묶 습니다.fa