태그 보관물: fibonacci

fibonacci

N- 보나 치 시퀀스 역 엔지니어 나치 시퀀스”라고

편집 : 나는 2016 년 2 월 15 일 월요일 답변을 수락 할 것입니다. 바이트가 당신에게 유리할 수 있기를 바랍니다!

그의 “N- 보나 치 시퀀스 인쇄”챌린지 에서 @DJMcGoathem 은 N- 보나 치 시퀀스를 설명하는데, 여기서 피보나치 시퀀스의 전통적인 2 개 ( ” 듀오 나치 시퀀스”라고 함) 대신 이전 N 개의 숫자가 합산됩니다 . 그런 다음 X와 N이라는 두 개의 입력을 취한 다음 X 번째 N- 나치 수 를 출력하도록 요청했습니다 .

나는 그 반대를 제안한다.
시퀀스가 주어지면 N -nacci 시퀀스가 ​​하위 집합임을 출력하십시오 . 나는 “서브셋”이라고 말합니다 :

  • A)이 시퀀스는 무한하다
  • B) 시퀀스의 시작이 주어지면 선행 1의 수를 셀 수 있습니다.

다수의 N- 나치 서열에 속할 수있는 경우 가장 낮은 것을 선택하십시오. N-nacci 시퀀스
에 속하지 않는 경우 , 프로그램은 출력으로 오인 될 수있는 것을 인쇄하는 것 이외의 다른 작업을 수행 할 수 있습니다. 이러한 동작에는 무한 루프, 오류, 충돌, 자체 삭제 (* 기침 기침 * 경계 * 기침 기침 *) 또는 블랙홀 생성 (이 블랙홀이 발생할 수있는 것을 생성하지 않는 한 )이 포함됩니다 (이에 국한되지 않음). 유효한 출력으로 오해하십시오).
이러한 도전을 위해, 이들 서열은 1로 시작한다. 이것은 N- 나치 서열이 N으로 시작 한다는 것을 의미 한다. 또한 N양의 정수 여야합니다. 따라서 -1 -nacci 등은 없습니다 .

테스트 사례 :

1,1,1 -> 1
49, 97 -> 7
55, 89, 144 -> 2
1 -> 1
6765 -> 2
12, 23, 45, 89 -> 12
100, 199 -> 100



답변

루비, 94

나는 같은 알고리즘 내에서 이것을 얼마나 멀리 골프화시킬 수 있었는지 매우 놀랐습니다! 나는 200 이상으로 시작했습니다!

->a{1.step.find{|s|x=[1]*(s+z=a.size)
x<<x[-s,s].inject(:+)while x.max<a.max&&s>1
x[-z,z]==a}}

언 골프 드 :

l=->a{
    # ooh! a built-in infinite incrementer!
    1.step.find{|s|
        # if n == 1, z is important, otherwise s.
        x=[1]*(s+z=a.size)
        ## add the next nacci number until we hit or overshot max. 
        ## if s == 1, we don't increment, so don't bother
        x<<x[-s,s].inject(:+)while x.max<g&&s>1
        # eval to true if there's a match, false if not
        x[-z,z]==a
    }
}


답변

파이썬 2, 176 바이트

def r(n,x):i,f=n,[1]*n;exec"f+=sum(f[i-n:]),;i+=1;"*(x-n);return f
l=input()
m=max(l)+len(l)
for i in range(1,m):
 if any(l==r(i,m)[b:b+len(l)]for b in range(m)):print i;break;

여기에는 다음 형식의 입력이 필요합니다.

[1, 1, 2, 3...]

오히려

1, 1, 2, 3...

물건을 구르기 위해 아주 간단한 해결책입니다. 다른 사람이 대답하면 골프를 치는 데 더 많은 노력을 기울일 것입니다. 이것은 @ Data ‘s answer 에서 약간 수정 된 N-Bonnaci 생성기 버전을 사용하므로 그에게 전파 됩니다. 그런 다음 입력 범위의 각 N-Bonnaci에 대해 입력이 그 하위 시퀀스인지 확인합니다.


답변

루아, (324) 323 바이트

다른 제출을 볼 때 코드에 문제가있는 것 같습니다 …하지만 Lua라는 것을 기억하고 이러한 멋진 기능이 모두 없습니다 : ‘(

그것은 많은 재미이었다, 실제로 시간이 좀 걸렸다.

편집 : 간단한 트릭으로 1 바이트를 절약했습니다. ::label::+ goto label대신 무한 루프를 사용하십시오 while''.

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

언 골프 및 설명

Lua는 집합 / 집합을 정의하거나 배열 / 테이블에 색인 / 키를 사용하지 않고 값이 포함되어 있는지 확인할 방법이 없습니다. 그것이 내가 매개 변수로 취하는 배열에서 요소를 제거하기로 결정한 이유입니다. 이것이 내가 이미 계산 한 요소와 일치하는 요소를 기록하는 방법입니다.

  function f(l)
  c=2
  y,z=table.remove,os.exit           -- Create pointers on table.remove and os.exit
                                     -- saves a total of 9 bytes
  while(l[1]<2)                      -- loop used to remove leading 1
  do
    y(l,1)
    if(#l<1)                         -- we also check if it was a 1-only array
    then
      print(1)                       -- if so, we print 1 and exit
      z()
    end
  end

  ::q::                              -- label q, start of the infinite loop
    a={}for i=1,c do a[i]=1 end      -- fill an array with c 1s
    b={}for i=1,#l do b[i]=l[i]end   -- copy the sequence array
    while(a[#a]<b[1])                -- while max(a)<min(b)
    do
      x=0 for i=(#a-c+1>0            -- iterate from index a.length-c to
                    and #a-c+1       -- to a.length
                    or 1),#a
      do
        x=x+a[i]                     -- summing a's elements
      end
      a[#a+1]=x                      -- append x to a
      if a[#a]==b[1]then y(b,1)end   -- if x is equal ot a member of the sequence
                                     -- remove it
      if #b<1 then print(c)z()end    -- if b is empty, it means the subset is in a
                                     -- we print c and exit
    end                              -- else we loop again
    c=c+1                            -- with c+1
  goto q                             -- return to the start of this block
end

Lua online을 사용해 볼 수 있으며 다음 코드 샘플을 복사 / 붙여 넣기하여 테스트를 실행할 수 있습니다. 이 함수가 답을 찾으면 종료되므로 (그렇지 않으면 무한 루프), test[]사용 된 인덱스를 변경해야합니다 (루아가 1 인덱싱 된 것을 잊지 마십시오 :).

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

test={{1,1,1},
{49, 97},
{55, 89, 144},
{1},
{6765},
{12, 23, 45, 89},
{100, 199}}

print(f(test[1]))


답변