태그 보관물: recursion

recursion

1, 2, 4, 8, 16,… 33? 추가 할 것입니다

도전

잘 알려진 숫자 순서로 n‘번째 요소 또는 첫 번째 요소’ 를 출력하는 함수 / 프로그램을 작성하십시오 n.

         1, 2, 4, 8, 16 ...

아, 잠깐만 요. 처음 몇 개의 숫자를 잊었습니다.

1, 1, 1, 1, 2, 4, 8, 16 ...

도대체, 나는 좋은 측정을 위해 몇 가지를 더 추가 할 것입니다 :

1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705 ...

숫자는 (0 인덱스) 공식으로 주어진 일반화 된 카탈로니아 어 숫자입니다.

a(n+1)=a(n)+k=2n1a(k)a(n1k)

어디에

a(0)=a(1)=a(2)=a(3)=1

이다 OEIS A004149 .

시퀀스를 0 또는 1 인덱스로 만들 것인지 선택할 수 있습니다. 시퀀스는 물론 동일해야하므로 수식이 하나 인 경우 수식을 다시 작성해야합니다.



답변

파이썬 , 51 바이트

f=lambda n,k=2:n<3or k<n and f(k)*f(n-k-2)+f(n,k+1)

온라인으로 사용해보십시오!

수식을 약간 단순화합니다.

a(n)=k=2n1a(k)a(n2k)

a(1)=a(0)=a(1)=a(2)=1


답변

펄 6 , 44 바이트

{1,1,1,1,{sum @_[2..*]Z*@_[@_-4...0,0]}...*}

온라인으로 사용해보십시오!

게으른 무한 값 시퀀스를 반환하는 익명 코드 블록입니다. 이것은 설명 된대로 시퀀스를 거의 구현하며, zip 바로 가기는 두 번째 요소 이후까지 모든 요소에 네 번째 요소부터 시작하여 목록의 반대 부분을 추가 1하고 끝에 추가 요소를 추가합니다 .

설명:

{                                          }  # Anonymous code block
                                       ...*   # Create an infinite sequence
 1,1,1,1,                                     # Starting with four 1s
         {                            }       # Where each new element is:
          sum                                   # The sum of
              @_[2..*]                          # The second element onwards
                      Z*                        # Zip multiplied with
                        @_[@_-4...0  ]          # The fourth last element backwards
                                   ,0           # And 1


답변

05AB1E , 14 13 11 바이트

$ƒˆ¯Âø¨¨¨PO

온라인으로 사용해보십시오!

n 번째 요소 (0 인덱스)를 출력합니다.

$                # push 1 and the input
 ƒ               # repeat (input+1) times
  ˆ              #  add the top of the stack (initially 1) to the global array
   ¯             #  push the global array
    Â            #  and a reversed copy of it
     ø           #  zip the two together, giving a list of pairs
      ¨¨¨        #  drop the last 3 pairs
         P       #  take the product of each pair (or 1 if the list is empty)
          O      #  take the sum of those products
                 #  after the last iteration, this is implicitly output;
                 #  otherwise, it's added to the global array by the next iteration


답변

자바 스크립트 (ES6), 42 바이트

xnor의 솔루션 포트 .

인덱스가 0입니다.

f=(n,k=2)=>n<3||k<n&&f(k)*f(n+~++k)+f(n,k)

온라인으로 사용해보십시오!


자바 스크립트 (ES6),  83  75 바이트

더 빠르고 덜 재귀하지만 훨씬 더 긴 솔루션입니다.

인덱스가 0입니다.

f=(n,i,a=[p=1])=>a[n]||f(n,-~i,[...a,p+=(h=k=>k<i&&a[k]*a[i-++k]+h(k))(2)])

온라인으로 사용해보십시오!


답변

하스켈, 49 43 39 바이트

a n=max(sum[a k*a(n-2-k)|k<-[2..n-1]])1

온라인으로 사용해보십시오!

들어 n<3(가) sum0, 그래서 max ... 1그것을가 발생합니다 1.

편집 : @Jo King 덕분에 -6 바이트.


답변

Wolfram Language (Mathematica) , 36 바이트

Sum[#0@i#0[#-i-1],{i,3,#-1}]/. 0->1&

온라인으로 사용해보십시오!

1- 색인.

2- 인덱싱 된 시퀀스는 4 바이트 더 짧습니다 Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&.
온라인으로 사용해보십시오!


답변

05AB1E , 17 13 바이트

4Å1λ£₁λ¨Â¦¦s¦¦*O+

기존 05AB1E 답변 보다 짧지는 않지만 새로운 05AB1E 버전의 재귀 기능을 직접 연습 해보고 싶었습니다. 아마도 몇 바이트 정도 골프를 쳤을 것입니다. 편집 : 그리고 그것은 사실의 재귀 버전을 볼 수 있습니다 @Grimy 입니다 아래의 05AB1E 응답, 13 바이트를 .

n

n

£è
£

설명:

a(n)=a(n1)+k=2n1(a(k)a(n1k))

a(0)=a(1)=a(2)=a(3)=1

   λ               # Create a recursive environment,
    £              # to output the first (implicit) input amount of results after we're done
4Å1                # Start this recursive list with [1,1,1,1], thus a(0)=a(1)=a(2)=a(3)=1
                   # Within the recursive environment, do the following:
      λ            #  Push the list of values in the range [a(0),a(n)]
       ¨           #  Remove the last one to make the range [a(0),a(n-1)]
        Â          #  Bifurcate this list (short for Duplicate & Reverse copy)
         ¦¦        #  Remove the first two items of the reversed list,
                   #  so we'll have a list with the values in the range [a(n-3),a(0)]
           s       #  Swap to get the [a(0),a(n-1)] list again
            ¦¦     #  Remove the first two items of this list as well,
                   #  so we'll have a list with the values in the range [a(2),a(n-1)]
              *    #  Multiply the values at the same indices in both lists,
                   #  so we'll have a list with the values [a(n-3)*a(2),...,a(0)*a(n-1)]
               O   #  Take the sum of this list
               +  #  And add it to the a(n-1)'th value
                   # (afterwards the resulting list is output implicitly)

@Grimy의 13 바이트 버전 ( 아직 대답 하지 않았다면 을 올리십시오 !) :

1λ£λ1šÂ¨¨¨øPO

n

1λèλ1šÂ¨¨¨øPO
λλ1šÂ¨¨¨øPO

a(0)=1

설명:


a(n)=k=2n1(a(k)a(n2k))

a(1)=a(0)=a(1)=a(2)=1

 λ             # Create a recursive environment,
  £            # to output the first (implicit) input amount of results after we're done
1              # Start this recursive list with 1, thus a(0)=1
               # Within the recursive environment, do the following:
   λ           #  Push the list of values in the range [a(0),a(n)]
    1š         #  Prepend 1 in front of this list
      Â        #  Bifurcate the list (short for Duplicate & Reverse copy)
       ¨¨¨     #  Remove (up to) the last three value in this reversed list
          ø    #  Create pairs with the list we bifurcated earlier
               #  (which will automatically remove any trailing items of the longer list)
           P   #  Get the product of each pair (which will result in 1 for an empty list)
            O  #  And sum the entire list
               # (afterwards the resulting list is output implicitly)