Herausforderung

Schreiben Sie eine Funktion / ein Programm, das entweder das n'te Element oder die ersten nElemente in der bekannten Zahlenfolge ausgibt :

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

Oh, warte ... Ich habe die ersten Zahlen vergessen:

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

Heck, ich werde ein paar mehr für gutes Maß hinzufügen:

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

Die Zahlen sind verallgemeinerte katalanische Zahlen, die durch die (mit Nullen versehene) Formel angegeben werden:

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

woher

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

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

Dies ist OEIS A004149 .

Sie können wählen, ob die Sequenz null- oder einsindiziert werden soll. Die Reihenfolge muss natürlich identisch sein, daher müssen Sie die Formel neu schreiben, wenn Sie sie einmal indiziert haben.

code-golf number sequence recursion Stewie Griffin
quelle

Korrigieren Sie mich , wenn ich hier falsch bin, aber die Modifikation für eine indizierte Formel zu ändern , a(n-1-k)zu a(n-k)korrigieren?

Sumner,

9

Dies erinnert mich an das starke Gesetz der kleinen Zahlen

Luis Mendo

22

Python , 51 Bytes

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

Probieren Sie es online!

Vereinfacht die Formel etwas:

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

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

ein (- 1) = ein (0) = ein (1) = ein (2) = 1

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

xnor
quelle

8

Herzlichen Glückwunsch zum 100k !!

Stewie Griffin

Da ich auch eigenständig zu dieser Lösung gekommen bin, muss ich sagen, dass der Weg dahin etwas holprig ist ...

Erik the Outgolfer

10

Perl 6 , 44 Bytes

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

Probieren Sie es online!

Anonymer Codeblock, der eine langsame unendliche Folge von Werten zurückgibt. Dies implementiert die beschriebene Sequenz so ziemlich, mit der Abkürzung, dass alle Elemente nach dem zweiten Element mit der Umkehrung der Liste multipliziert werden, beginnend mit dem vierten Element und dem Hinzufügen eines Extra 1am Ende.

Erläuterung:

{                                          }  # 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

Scherzen
quelle

10

05AB1E , 14 13 11 Bytes

$ƒˆ¯Âø¨¨¨PO

Probieren Sie es online!

Gibt das n-te Element mit dem Index 0 aus.

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

Grimmig
quelle

7

JavaScript (ES6), 42 Byte

Eine Portierung von xnors Lösung .

0-indiziert.

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

Probieren Sie es online!

JavaScript (ES6), 83 bis 75 Byte

Eine schnellere, weniger rekursive, aber deutlich längere Lösung.

0-indiziert.

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

Probieren Sie es online!

Arnauld
quelle

7

Haskell, 49 43 39 Bytes

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

Probieren Sie es online!

Für n<3das sumist 0, also max ... 1wirft es auf 1.

Edit: -6 Bytes dank @Jo King.

nimi
quelle

6

Wolfram Language (Mathematica) , 36 Byte

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

Probieren Sie es online!

1-indiziert.

Die 2-indizierte Sequenz ist 4 Byte kürzer: Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&. Probieren Sie es online!

attinat
quelle

2

Beeindruckend, dass dieser kürzer ist als der eingebaute CatalanNumber!

Erfink

6

05AB1E , 17 13 Bytes

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

Nicht kürzer als die bisherige 05AB1E-Antwort , aber ich wollte die rekursive Funktionalität der neuen 05AB1E-Version als Übung für mich ausprobieren. ~~Könnte vielleicht von ein paar Bytes golfen werden.~~ EDIT: Und es kann in der Tat die rekursive Version von @Grimys 05AB1E Antwort sehen, die 13 Bytes ist .

$n$

$n$ £è
£

Erläuterung:

$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- Byte- Version von @Grimy (stellen Sie sicher, dass Sie seine Antwort positiv bewerten , falls Sie dies noch nicht getan haben!):

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

$n$

1λèλ1šÂ¨¨¨øPO
λλ1šÂ¨¨¨øPO $a(0)=1$

Erläuterung:

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

1

Interessant, dass dies eine (1200) in 40 Sekunden auf tio lösen kann, während andere rekursive Ansätze eine Zeitüberschreitung für Zahlen n als 100 ...

Stewie Griffin,

1

Ich habe auch eine rekursive Version erstellt (aber nicht veröffentlicht). Es sind 13 Bytes für die ersten n Terme oder 11 Bytes für eine unendliche Liste . Sonderfälle a (n-1) kosten viele Bytes und werden nicht benötigt (siehe zum Beispiel xnors Formel ).

Grimmy

@Grimy Stört es Sie, wenn ich Ihre rekursiven Lösungen zu meiner Antwort hinzufüge? Ich werde auch meine ursprüngliche Antwort hinterlassen. Aber es ist schön, die Unterschiede zwischen der ursprünglichen Formel und der bytespeichernden Formel von xnor zu sehen. :)

Kevin Cruijssen

1

Klar ist das in Ordnung!

Grimmy

@StewieGriffin Ja, ich war auch beeindruckt von der Geschwindigkeit dieser rekursiven unendlichen Funktionen. Vielleicht eine der Stärken von Elixir und definitiv auf das eingebaute Lazy-Loading zurückzuführen. Es wird n=100in 0,65 Sekunden berechnet , aber wenn ich Lazy-Loading deaktiviere, läuft es stattdessen nach 60 Sekunden ab, auch fürn=25 .

Kevin Cruijssen

5

Python 3 , 59 Bytes

Wirklich ineffizient, a(13)endet nicht bei 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)

Probieren Sie es online!

ovs
quelle

3

Gelee , 17 Bytes

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

Probieren Sie es online!

$n$ $0$ $n$

Nick Kennedy
quelle

2

Haskell , 76 Bytes

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

Probieren Sie es online!

Fehler
quelle

2

APL (Dyalog Extended) , 34 Byte ^SBCS

-2 danke an dzaima.

Anonymes Präfix Lambda.

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

Probieren Sie es online!

Adam
quelle

@dzaima Danke. TFW jemand kennt meine Sprache besser als ich :-)

Adám

2

Japt , 19 17 16 Bytes

Gibt den ersten nTerm mit einem Index aus.

@Zí*Zz2)Å¤x}g4Æ1

Versuch es

@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

Zottelig
quelle

1

Haskell , 65 Bytes

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

Probieren Sie es online!

Sie können entweder fein einzelnes Element einer Sequenz abrufen oder eine Werteliste an übergeben gund alle Indizes für diese Liste abrufen.

Scherzen
quelle

1

Forth (gforth) , 99 81 Bytes

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

Probieren Sie es online!

Die Ausgabe ist das n-te Glied und die Eingabe ist 1-indiziert

Bearbeiten: 17 Bytes durch Umschalten auf die Formel von xnor gespeichert. Weitere 1 Byte mit 1-Index gespeichert

Code-Erklärung

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

1

Holzkohle , 26 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Gibt die 0-indizierte n-te Zahl aus, obwohl sie intern mit 1-Indizierung berechnet wird. Erläuterung:

Ｆ⁵⊞υ¹

Beginnen Sie mit a[0] = a[1] = a[2] = a[3] = a[4] = 1. Ja, dies ist 1-indiziert, jedoch mit einem zusätzlichen nullten Wert. Das ist Codegolf für Sie.

ＦＮ

Berechnen Sie zusätzliche nBegriffe. Dies ist übertrieben, erleichtert aber das Auffinden des gewünschten Begriffs, wenn n<5.

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

Berechnen Sie für jeden Term den nächsten Term als die Summe der bisherigen Terms, multipliziert mit der Umkehrung der bisherigen Terms, mit Ausnahme von drei Terms.

→

Dies ist ein No-Op, der verwendet wird, um Charcoal zum Parsen der 2-Argument-Form von Slicezu verleiten, da ich ansonsten weniger Golf spielen müsste, um drei Begriffe zu entfernen.

Ｉ§υ±⁴

Geben Sie das 4. letzte Semester aus.

Neil
quelle

1

Pyth , 30 Bytes

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

Probieren Sie es online!

$n$

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]

<@ $n$

ar4093
quelle

1

Ruby , 42 41 Bytes

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

Probieren Sie es online!

1-indiziert (um 1 Byte zu sparen)

GB
quelle

1

Oktave , 73 Bytes

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

Probieren Sie es online!

-2 Bytes dank Stewie Griffin. Der imperative Ansatz setzt sich erneut gegen den funktionalen rekursiven Ansatz durch. Das ist unten gezeigt.

Oktave , 75 Bytes

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

Probieren Sie es online!

Captcha wollte überprüfen, ob ich ein Mensch bin, als ich das gepostet habe. Um ehrlich zu sein, bin ich mir nicht so sicher .

Sanchises
quelle

Ich sehe keine offensichtlichen Möglichkeiten, um den Loop-Ansatz zu verkürzen ... Es sieht ziemlich gut aus, Golf zu spielen! Außerdem sehe ich in Octave nicht oft eine auf Null basierende Indizierung :)

Stewie Griffin,

Da die Rekursion @StewieGriffin hat einige Versetzungen es nicht der Fall ist wirklich egal , ob Sie null- oder eine Indizierung holen. Ich denke, ich könnte vielleicht ein paar Bytes rasieren, wenn ich 2-indiziere, aber das schien zu schummeln. Wie auch immer, Ihre Intuition war richtig - irgendwie war dies auf anonyme, rekursive Weise tatsächlich kürzer. Ich denke, der Hauptvorteil ist, dass es die Erstellung der vier Anfangswerte sehr gut handhabt, da es nur 1 für zurückgibt n<4.

Sanchises,

1

@StewieGriffin Natürlich gute alte Matrixmultiplikation. Gut gemacht!

Sanchises

0

Perl 5 `-MList::Util=sum` , 61 Bytes

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

Probieren Sie es online!

Xcali
quelle

0

C / C ++ , 70 69 67 Bytes

-1 Bytes dank Jonathan.

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

Probieren Sie es online!

Polfosol ఠ_ఠ
quelle

Kann a(n-1-k)sein a(n+~k)?

Jonathan Frech,

@ JonathanFrech ist sogar a(++k)*a(n-k)wahrscheinlich zu arbeiten, und es fällt weitere 2 Bytes ab for. Aber ich rieche undefiniertes Verhalten.

Polfosol ఠ_ఠ

Das scheint ein Sequenzierungsproblem zu sein. auf jeden Fall UB.

Jonathan Frech

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

Herausforderung

Antworten:

Python , 51 Bytes

Perl 6 , 44 Bytes

Erläuterung:

05AB1E , 14 13 11 Bytes

JavaScript (ES6), 42 Byte

JavaScript (ES6), 83 bis 75 Byte

Haskell, 49 43 39 Bytes

Wolfram Language (Mathematica) , 36 Byte

05AB1E , 17 13 Bytes

Python 3 , 59 Bytes

Gelee , 17 Bytes

Haskell , 76 Bytes

APL (Dyalog Extended) , 34 Byte ^SBCS

Japt , 19 17 16 Bytes

Haskell , 65 Bytes

Forth (gforth) , 99 81 Bytes

Code-Erklärung

Holzkohle , 26 Bytes

Pyth , 30 Bytes

Ruby , 42 41 Bytes

Oktave , 73 Bytes

Oktave , 75 Bytes

Perl 5 `-MList::Util=sum` , 61 Bytes

C / C ++ , 70 69 67 Bytes

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

Herausforderung

Antworten:

Python , 51 Bytes

Perl 6 , 44 Bytes

Erläuterung:

05AB1E , 14 13 11 Bytes

JavaScript (ES6), 42 Byte

JavaScript (ES6), 83 bis 75 Byte

Haskell, 49 43 39 Bytes

Wolfram Language (Mathematica) , 36 Byte

05AB1E , 17 13 Bytes

Python 3 , 59 Bytes

Gelee , 17 Bytes

Haskell , 76 Bytes

APL (Dyalog Extended) , 34 Byte SBCS

Japt , 19 17 16 Bytes

Haskell , 65 Bytes

Forth (gforth) , 99 81 Bytes

Code-Erklärung

Holzkohle , 26 Bytes

Pyth , 30 Bytes

Ruby , 42 41 Bytes

Oktave , 73 Bytes

Oktave , 75 Bytes

Perl 5 -MList::Util=sum , 61 Bytes

C / C ++ , 70 69 67 Bytes

APL (Dyalog Extended) , 34 Byte ^SBCS

Perl 5 `-MList::Util=sum` , 61 Bytes