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

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

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

gdzie

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

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

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.

— Stewie Griffin
źródło

Popraw mnie, jeśli się tu mylę, ale modyfikacja formuły z jednym indeksem polega na zmianie a(n-1-k)na a(n-k), prawda?

— Sumner18

9

To przypomina mi silne prawo małych liczb

— Luis Mendo

23

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łę:

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

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

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

$a(-1) = a(0)= a(1)= a(2) = 1$

— xnor
źródło

8

Gratulacje na 100 000 !!

— Stewie Griffin

Ponieważ do tego rozwiązania dotarłem również niezależnie, muszę powiedzieć, że droga do niego jest nieco wyboista ...

— Erik the Outgolfer

10

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

— Jo King
źródło

10

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

— Ponury
źródło

7

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!

— Arnauld
źródło

7

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.

— nimi
źródło

6

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!

— attinat
źródło

2

Imponujące, że jest krótszy niż wbudowany CatalanNumber!

— erfink

6

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)

— Kevin Cruijssen
źródło

1

Ciekawe, że może to rozwiązać (1200) w 40 sekund na tio, podczas gdy inne podejścia rekurencyjne przekroczą limit czasu dla liczb n niż 100 ...

— Stewie Griffin

1

Stworzyłem również (ale nie opublikowałem) wersję rekurencyjną. To 13 bajtów dla pierwszych n terminów lub 11 bajtów dla nieskończonej listy . Specjalna obudowa a (n-1) kosztuje dużo bajtów i nie jest potrzebna (patrz na przykład wzór xnor ).

— Grimmy,

@Grimy Czy masz coś przeciwko, jeśli dodam twoje rekurencyjne rozwiązania do mojej odpowiedzi (oczywiście dziękuję)? Zostawię również moją oryginalną odpowiedź. Ale miło jest widzieć różnice między oryginalną formułą a formułą oszczędzania bajtów xnor. :)

— Kevin Cruijssen

1

Jasne, w porządku!

— Grimmy,

@StewieGriffin Tak, byłem pod wrażeniem szybkości tych rekurencyjnych funkcji nieskończoności. Może jedna z mocnych stron Eliksiru, a na pewno ze względu na wbudowane leniwe ładowanie. Oblicza się n=100w 0,65 sekundy , ale kiedy wyłączę leniwe ładowanie, upłynie limit czasu po 60 sekundach, nawet przezn=25 .

— Kevin Cruijssen

5

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!

— ovs
źródło

3

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

— Nick Kennedy
źródło

2

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!

— wada
źródło

2

APL (Dyalog Extended) , 34 bajty ^SBCS

-2 dzięki dzaima.

Anonimowy przedrostek lambda.

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

Wypróbuj online!

— Adám
źródło

@dzaima Dzięki. TFW ktoś zna mój język lepiej niż ja :-)

— Adám

2

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

— Kudłaty
źródło

1

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.

— Jo King
źródło

1

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

— reffu
źródło

1

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.

— Neil
źródło

1

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.

— ar4093
źródło

1

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)

— GB
źródło

1

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 .

— Sanchises
źródło

Nie widzę żadnych oczywistych sposobów skrócenia podejścia do pętli ... Wygląda całkiem dobrze golfowo! Poza tym nieczęsto widzę indeksowanie od zera w Octave :)

— Stewie Griffin,

@StewieGriffin Ponieważ rekurencja ma pewne przesunięcia, tak naprawdę nie ma znaczenia, czy wybierzesz zero lub jedno indeksowanie. Myślę, że mógłbym ogolić kilka bajtów, gdybym zrobił 2-indeksowanie, ale to wydawało się oszustwem. W każdym razie twoja intuicja była słuszna - jakoś tak naprawdę była krótsza w anonimowy sposób rekurencyjny. Myślę, że główną zaletą jest to, że bardzo dobrze radzi sobie z tworzeniem czterech wartości początkowych, ponieważ zwraca po prostu 1 dla n<4.

— Sanchises

1

@StewieGriffin Oczywiście, stare dobre mnożenie macierzy. Dobra robota!

— Sanchises

0

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!

— Xcali
źródło

0

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!

— polfosol ఠ_ఠ
źródło

Może a(n-1-k)być a(n+~k)?

— Jonathan Frech

@JonathanFrech może nawet a(++k)*a(n-k)zadziałać i zrzuca kolejne 2 bajty for. Ale wyczuwam niezdefiniowane zachowanie.

— polfosol ఠ_ఠ

To wydaje się być problemem związanym z sekwencjonowaniem; zdecydowanie UB.

— Jonathan Frech

1, 2, 4, 8, 16,… 33?

Wyzwanie

Python , 51 bajtów

Perl 6 , 44 bajtów

Wyjaśnienie:

05AB1E , 14 13 11 bajtów

JavaScript (ES6), 42 bajty

JavaScript (ES6), 83 75 bajtów

Haskell, 49 43 39 bajtów

Wolfram Language (Mathematica) , 36 bajtów

05AB1E , 17 13 bajtów

Python 3 , 59 bajtów

Galaretka , 17 bajtów

Haskell , 76 bajtów

APL (Dyalog Extended) , 34 bajty SBCS

Japt , 19 17 16 bajtów

Haskell , 65 bajtów

Dalej (gforth) , 99 81 bajtów

Objaśnienie kodu

Węgiel drzewny , 26 bajtów

Pyth , 30 bajtów

Rubin , 42 41 bajtów

Oktawa , 73 bajty

Oktawa , 75 bajtów

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

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

APL (Dyalog Extended) , 34 bajty ^SBCS

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