Wyzwanie

Napisz funkcję / program, który wypisuje albo ten nelement, albo pierwsze nelementy, w dobrze znanej sekwencji liczb:

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

Och, czekaj ... Zapomniałem kilku pierwszych cyfr:

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

Do licha, dodam jeszcze kilka dla dobrego pomiaru:

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

Liczby są uogólnionymi liczbami katalońskimi podanymi według formuły (indeksowanej zerem):

gdzie

To jest OEIS A004149 .

Możesz wybrać, czy chcesz, aby sekwencja była zerowa czy indeksowana jednokrotnie. Sekwencja musi oczywiście być taka sama, więc musisz przepisać formułę, jeśli masz indeksowanie jednoindeksowe.

Python , 51 bajtów

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

Wypróbuj online!

Trochę upraszcza formułę:

Perl 6 , 44 bajtów

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

Wypróbuj online!

Anonimowy blok kodu, który zwraca leniwą nieskończoną sekwencję wartości. To prawie implementuje sekwencję, jak opisano, za pomocą skrótu, który zip powoduje pomnożenie wszystkich elementów do tej pory po drugim elemencie z odwrotnością listy, zaczynając od czwartego elementu i dodając dodatkowy 1na końcu.

Wyjaśnienie:

{                                          }  # 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 bajtów

$ƒˆ¯Âø¨¨¨PO

Wypróbuj online!

Zwraca n-ty element indeksowany według 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

JavaScript (ES6), 42 bajty

Port rozwiązania xnor .

0-indeksowane.

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

Wypróbuj online!

JavaScript (ES6),  83  75 bajtów

Szybsze, mniej rekurencyjne, ale znacznie dłuższe rozwiązanie.

0-indeksowane.

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)])

Wypróbuj online!

Haskell, 49 43 39 bajtów

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

Wypróbuj online!

Dla jest 0, więc podnosi go don<3summax ... 11 .

Edycja: -6 bajtów dzięki @Jo King.

Wolfram Language (Mathematica) , 36 bajtów

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

Wypróbuj online!

1-indeksowany.

2-indeksowane sekwencja 4 bajty krótszy: Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&. Wypróbuj online!

05AB1E , 17 13 bajtów

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

Nie krótszy niż istniejąca odpowiedź 05AB1E , ale chciałem wypróbować rekurencyjną funkcjonalność nowej wersji 05AB1E jako praktykę dla siebie. Może być golfem o kilka bajtów. EDYCJA: I rzeczywiście może, zobacz rekurencyjną wersję odpowiedzi 05AB1E @Grimy poniżej, która ma 13 bajtów .

$n$

$n$£è
£ .

Wyjaśnienie:

$a(n)= a(n-1) + \sum_{k=2}^{n-1}(a(k)\cdot a(n-1-k))$

$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)

13 bajtów wersję @Grimy (upewnij się upvote jego odpowiedź , jeśli nie masz jeszcze!):

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

$n$

Można ponownie zmienić na indeksowanie 0 lub nieskończoną listę:
- Indeksowanie (0) 1λèλ1šÂ¨¨¨øPO: Wypróbuj online ;
- Nieskończona lista λλ1šÂ¨¨¨øPO: Wypróbuj online . (Zauważ, że zapisywane są tutaj 2 bajty zamiast 1, ponieważ środowisko rekurencyjne zaczyna się od$a(0)=1$ domyślnie.)

Wyjaśnienie:

Zamiast tego implementuje formułę znalezioną przez @xnor dla jego odpowiedzi w języku Python w następujący sposób:
$a(n) = \sum_{k=2}^{n-1}(a(k)\cdot a(n-2-k))$

$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)

Python 3 , 59 bajtów

naprawdę nieefektywny, a(13)nie kończy się na TIO.

a=lambda n,k=2:n<4or(n-k<2)*a(n-1)or a(k)*a(n-k-2)+a(n,k+1)

Wypróbuj online!

Galaretka , 17 bajtów

1WṪ;+¥×Uṫ3SƲ;@Ʋ⁸¡

Wypróbuj online!

Monadyczny link przyjmujący indeksowane zero $n$ i zwracając listę uogólnionych liczb katalońskich z $0$ do $n$.

Haskell , 76 bajtów

1:1:1:f[1,1,1]
f(x:z)|y<-x+sum(zipWith(*)(init$init z)$reverse z)=y:f(y:x:z)

Wypróbuj online!

APL (Dyalog Extended) , 34 bajty ^SBCS

-2 dzięki dzaima.

Anonimowy przedrostek lambda.

{⍵≤3:1⋄+/(∇⍵-1),⍵(-×⍥∇¯2+⊢)¨4…⍵}

Wypróbuj online!

Japt , 19 17 16 bajtów

Wysyła nth termin, indeksowany 1.

@Zí*Zz2)Ťx}g4Æ1

Spróbuj

@Zí*Zz2)Ťx}g4Æ1     :Implicit input of integer U
@                    :Function taking an array as an argument via parameter Z
 Zí                  :  Interleave Z with
    Zz2              :  Z rotated clockwise by 180 degrees (simply reversing would be a bye shorter but would modify the original array)
   *                 :  Reduce each pair by multiplcation
       )             :  End interleave
        Å            :  Slice off the first element
         ¤           :  Slice off the first 2 elements
          x          :  Reduce by addition
           }         :End function
            g        :Pass the following as Z, push the result back to it and repeat until it has length U
             4Æ1     :Map the range [0,4) to 1s
                     :Implicit output of the last element

Haskell , 65 bajtów

f a|a<4=1|z<-g[2..a]=sum$zipWith(*)z$reverse(1:g[0..a-4])
g=map f

Wypróbuj online!

Możesz użyć albo, faby uzyskać pojedynczy element sekwencji, lub przekazać listę wartości gi uzyskać wszystkie indeksy dla tej listy.

Dalej (gforth) , 99 81 bajtów

: f recursive dup 4 > if 0 over 3 do over 1- i - f i f * + loop else 1 then nip ;

Wypróbuj online!

Dane wyjściowe to n-ty termin, a dane wejściowe mają indeks 1

Edycja: Zapisano 17 bajtów, przechodząc do formuły xnor. Zapisano kolejny 1 bajt za pomocą 1-indeksowanego

Objaśnienie kodu

: f                     \ start a new word definition
  recursive             \ mark that this word will be recursive
  dup 4 >               \ duplicate the input and check if it is greater than 4
  if                    \ if it is:
    0 over              \ create an accumulator and copy n to top of stack
    3 do                \ start counted loop from 3 to n-1
      over 1- i - f     \ recursively calculate f(n-1-i)
      i f               \ recursively calculate f(i)
      * +               \ multiply results and add to accumulator
    loop                \ end the counted loop        
  else                  \ otherwise, if n < 5
    1                   \ put 1 on the stack
  then                  \ end the if block
  nip                   \ drop n from the stack
;                       \ end the word definition

Węgiel drzewny , 26 bajtów

Ｆ⁵⊞υ¹ＦＮ⊞υΣ✂Ｅ⮌υ×κ§υλ³→Ｉ§υ±⁴

Wypróbuj online! Link jest do pełnej wersji kodu. Wyświetla n-tą indeksowaną liczbę 0, chociaż oblicza się ją przy użyciu wewnętrznego indeksowania 1. Wyjaśnienie:

Ｆ⁵⊞υ¹

Zacznij od a[0] = a[1] = a[2] = a[3] = a[4] = 1. Tak, jest to indeks 1, ale z dodatkową wartością zerową. To dla ciebie kod golfowy.

ＦＮ

Oblicz dodatkowe nwarunki. Jest to przesada, ale ułatwia znalezienie pożądanego terminu n<5.

⊞υΣ✂Ｅ⮌υ×κ§υλ³

Dla każdego terminu oblicz następny termin jako sumę dotychczasowych warunków pomnożoną termicznie przez odwrotność dotychczasowych warunków, z wyłączeniem trzech terminów.

→

To nie jest operacja używana do oszukiwania Węgla w analizie 2-argumentowej formy Slice, w przeciwnym razie musiałbym użyć mniej golfowego sposobu usunięcia trzech terminów.

Ｉ§υ±⁴

Wyjście 4. ostatniego terminu.

Pyth , 30 bajtów

J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<J

Wypróbuj online!

Zwraca pierwszy $n$ elementy sekwencji.

J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<JQ # Full program, last Q = input (implicitly added)
J*4]1                  # J = 4 * [1] (=[1,1,1,1])
VQ                     # for N in range(Q):
  =+J                  #  J +=
     +eJ               #   J[-1] + 
        s              #    sum(                           )
           *M          #     map(__operator_mul,          )
             .t      0 #      transpose(          , pad=0)
               ,       #       [       ,         ]
                PJ     #         J[:-1] 
                  _PJ  #                 J[1::-1]
<JQ                    # J[::Q]

Alternatywa: Wymień <się @do powrotu$n$-ty element sekwencji, indeksowany 0.

Rubin , 42 41 bajtów

f=->n{n<4?1:(4..n).sum{|i|f[i-1]*f[n-i]}}

Wypróbuj online!

1 indeksowany (aby zapisać 1 bajt)

Oktawa , 73 bajty

g=(1:4).^0;for(i=3:(n=input('')))g(i+2)=g(4:i+1)*g(i-(2:i-1))';end;g(end)

Wypróbuj online!

-2 bajty dzięki Stewie Griffin. Po raz kolejny podejście imperatywne wygrywa z funkcjonalnym podejściem rekurencyjnym. Ten pokazano poniżej.

Oktawa , 75 bajtów

f(f=@(a)@(n){@()sum(arrayfun(@(k)a(a)(k)*a(a)(n-2-k),2:n-1)),1}{2-(n>3)}())

Wypróbuj online!

Captcha chciał sprawdzić, czy opublikowałem to jako człowiek. Szczerze mówiąc, nie jestem tego taki pewien .

Perl 5 -MList::Util=sum , 61 bajtów

sub a{my$b=-2+pop;$b<2||sum a($b+1),map{a($_)*a($b-$_)}2..$b}

Wypróbuj online!

C / C ++ , 70 69 67 bajtów

-1 bajty dzięki Jonathanowi.

int a(int n){int k=2,s=0;while(++k<n)s+=a(k)*a(n+~k);return s?s:1;}

Wypróbuj online!