Seidel-Dreieck

14

Das Seidel-Dreieck ist eine mathematische Konstruktion, die dem Pascal-Dreieck ähnelt und für seine Verbindung mit den Bernoulli-Zahlen bekannt ist.

Die ersten paar Zeilen sind:

      1
      1  1
   2  2  1
   2  4  5  5
16 16 14 10 5
16 32 46 56 61 61

Jede Zeile wird wie folgt generiert:

Wenn die Zeilennummer gerade ist (1-indiziert):

  • Bringen Sie das erste Element der vorherigen Zeile nach unten

  • Jeder nächste Artikel ist die Summe des vorherigen Artikels und des Artikels darüber

  • Dupliziere das letzte Element

Wenn die Zeilennummer ungerade ist:

  • Bringen Sie das letzte Element der vorherigen Zeile nach unten

  • Wenn Sie rückwärts gehen , ist jeder Artikel die Summe des vorherigen Artikels und des Artikels darüber

  • Dupliziere das, was jetzt der erste Gegenstand ist.

Grundsätzlich konstruieren wir das Dreieck in einem Zick-Zack-Muster:

    1
    v
    1 > 1
        v
2 < 2 < 1
v
2 > 4 > 5 > 5

Weitere Informationen finden Sie auf der Wikipedia-Seite zu Bernoulli-Zahlen.

Die Herausforderung:

Gegeben n, entweder als Funktionsargument oder aus STDIN, drucke oder gib entweder die dritte nZeile des Seidel-Dreiecks oder die ersten nZeilen zurück. Sie können entweder 0 oder 1 Indexierung verwenden.

Sie müssen keine negativen oder nicht ganzzahligen Eingaben (oder 0, wenn 1-indiziert) verarbeiten. Sie müssen keine Ausgaben verarbeiten, die größer als sind2147483647 = 2^31 - 1

Da dies Codegolf ist, tun Sie dies in so wenigen Bytes wie möglich.

Beispiele:

In diesen Beispielen ist der Rückgabewert die ndritte Zeile mit dem Index 0.

Input   ->  Output

0           1
1           1 1
2           2 2 1
6           272 272 256 224 178 122 61
13          22368256 44736512 66750976 88057856 108311296 127181312 144361456 159575936 172585936 183194912 191252686 196658216 199360981 199360981
Bolce Bussiere
quelle
"Sie müssen keine Ausgaben verarbeiten, die größer sind als der Standard-Int-Typ Ihrer Sprache" macht dies für Sprachen mit nur 1-Bit-Ints trivial
ASCII
Können die Zeilen immer von klein nach groß sortiert ausgegeben werden?
Angs
@ Nur ASCII Geändert, um mit C ++ 's maximalem int
übereinzustimmen
@Angs Nein, die Reihen sollten wie abgebildet bestellt werden
Bolce Bussiere
@ Nur ASCII Das ist eine Standardlücke (obwohl IMO ist es ein bisschen schlecht formuliert, da es davon abhängt, was die Leute als "vernünftig" betrachten würden)
user202729

Antworten:

7

Brain-Flak , 66 Bytes

<>(())<>{({}[()]<(()[{}]<<>{(({}<>{}))<>}>)>)}{}{{}<>{({}<>)<>}}<>

Probieren Sie es online!

Zeile ist 0-indiziert.

# Push 1 (the contents of row 0) on other stack; use implicit zero as parity of current row
<>(())<>

# Do a number of times equal to input:
{({}[()]<

  # Subtract the row parity from 1
  (()[{}]<

    # For each entry in old row:
    <>{

      # Add to previous entry in new row and push twice
      (({}<>{}))<>

    }

  >)

>)}{}

# If row parity is odd:
{{}

  # Reverse stack for output
  <>{({}<>)<>}

# Switch stacks for output
}<>
Nitrodon
quelle
4

JavaScript (SpiderMonkey) , 67 Byte

Dieser Code missbraucht die sort()Methode und funktioniert nicht bei allen Engines.

Zeilen sind 0-indiziert.

f=(n,a=[1],r)=>n--?f(n,[...a.map(n=>k+=n,k=0),k].sort(_=>n|r),!r):a

Probieren Sie es online!

Wie?

Wir kehren ein Array bedingt um, indem wir die sort()Methode mit einer Rückruffunktion verwenden, die seine Parameter ignoriert und entweder 0 oder eine positive Ganzzahl zurückgibt . Versuchen Sie das nicht zu Hause! Dies funktioniert nur mit SpiderMonkey zuverlässig.

let A = [1,2,3,4,5] and B = [1,2,3,4,5,6,7,8,9,10,11]

             | SpiderMonkey (Firefox)  | V8 (Chrome)             | Chakra (Edge)
-------------+-------------------------+-------------------------+------------------------
A.sort(_=>0) | 1,2,3,4,5               | 1,2,3,4,5               | 1,2,3,4,5
A.sort(_=>1) | 5,4,3,2,1               | 5,4,3,2,1               | 1,2,3,4,5
B.sort(_=>0) | 1,2,3,4,5,6,7,8,9,10,11 | 6,1,3,4,5,2,7,8,9,10,11 | 1,2,3,4,5,6,7,8,9,10,11
B.sort(_=>1) | 11,10,9,8,7,6,5,4,3,2,1 | 6,11,1,10,9,8,7,2,5,4,3 | 1,2,3,4,5,6,7,8,9,10,11

Beachten Sie, dass V8 abhängig von der Länge des Arrays (weniger oder mehr als 10 Elemente) wahrscheinlich unterschiedliche Sortieralgorithmen verwendet.

Kommentiert

f = (                     // f = recursive function taking:
  n,                      //   n   = row counter
  a = [1],                //   a[] = current row, initialized to [1]
  r                       //   r   = 'reverse' flag, initially undefined
) =>                      //
  n-- ?                   // decrement n; if it was not equal to zero:
    f(                    //   do a recursive call with:
      n,                  //     - the updated value of n
      [ ...a.map(n =>     //     - a new array:
          k += n, k = 0   //       - made of the cumulative sum of a[]
        ), k              //         with the last value appended twice
      ].sort(_ => n | r), //       - reversed if n is not equal to 0 or r is set
      !r                  //     - the updated flag r
    )                     //   end of recursive call
  :                       // else:
    a                     //   stop recursion and return a[]
Arnauld
quelle
Welche spinnenaffen-spezifische Funktion wird verwendet?
Downgoat
@Downgoat Es nutzt die spezifische Implementierung sort()dieser Engine. Ich habe eine Erklärung hinzugefügt.
Arnauld
3

Haskell , 89 87 82 Bytes

(cycle[r,id]!!)<*>s
r=reverse
s 0=[1]
s n=let a=zipWith(+)(0:a)$(r.s$n-1)++[0]in a

Druckt einfach sdie Zeilen in der Zick-Zack-Reihenfolge, kehrt die anonyme Funktion in der ersten Zeile die Hälfte der Zeilen um.

Vielen Dank an @nimi für das Speichern von 5 Bytes!

Probieren Sie es online!

Angs
quelle
2

Python 3 , 98 91 Bytes

from itertools import*
f=lambda n:n and[*accumulate(f(n-1)[::n&1or-1]+[0])][::n&1or-1]or[1]

Probieren Sie es online!

Das Umschalten auf 0-basierte Zeilennummerierung sparte 7 Bytes.

RootTwo
quelle
2

Julia 0,6 , 85 Bytes

r(l,n=cumsum(l))=[n...,n[end]]
w=reverse
f(n)=n<2?[1]:n%2<1?r(f(n-1)):w(r(w(f(n-1))))

Probieren Sie es online!

Dies ist eine rekursive Lösung in Julia. Beachten Sie, dass es 1-basierte Indizierung hat. Daher die Tests.

Ungolfed Version, um die Logik zu verstehen:

function new_row(last_row)
    new_row = cumsum(last_row)
    push!(new_row, new_row[end])
    return new_row
end


function triangle(n)
    if n == 1
        return [1]
    elseif mod(n,2) == 0
        return new_row(triangle(n-1))
    else
        return reverse(new_row(reverse(triangle(n-1))))
    end
end

Als Bonus gibt es hier eine nicht-rekursive Version, aber das ist länger:

w=reverse;c=cumsum
r(l,i)=i%2<1?c([l...,0]):w(c(w([0,l...])))
f(n,l=[1])=(for i=2:n l=r(l,i)end;l)
niczky12
quelle
1

Python 2 , 103 97 Bytes

f=lambda n,r=[1],k=2:n and f(n-1,[sum(r[-2::-1][:i],r[-1])for i in range(k)],k+1)or r[::-(-1)**k]

Probieren Sie es online!

Nicht-rekursive Version (leichter zu lesen):

Python 2 , 106 Bytes

def f(n,r=[1],j=1):
 while n:
	a=r[-2::-1];r=r[-1:];n-=1;j=-j
	for x in a+[0]:r+=[r[-1]+x]
 return r[::-j]

Probieren Sie es online!

Besser geht es doch!

Chas Brown
quelle
1

Python 3 , 91 Bytes

from numpy import *
s=lambda n:n and cumsum(s(n-1)[::n%2*2-1]+[0]).tolist()[::n%2*2-1]or[1]

Probieren Sie es online!

Guoyang Qin
quelle
Sie können das Leerzeichen zwischen importund entfernen*
12Me21