Sumy Kolumny Pascala

29

Prawie wszyscy tutaj znają Trójkąt Pascala. Tworzą go kolejne rzędy, w których każdy element jest sumą dwóch górnych lewych i prawych górnych sąsiadów. Oto pierwsze 5wiersze (zapożyczone z trójkąta Generuj Pascala ):

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Weźmiemy Trójkąt Pascala i dokonamy na nim pewnych sum (hah-ha). Dla danych wejściowych nwypisz sumę kolumnową pierwszych nwierszy trójkąta Pascala. Na przykład dane wejściowe 5byłyby tworzone przez

            1
          1   1
        1   2   1
      1   3   3   1
[+] 1   4   6   4   1
----------------------
    1 1 5 4 9 4 5 1 1

Więc wynik byłby [1, 1, 5, 4, 9, 4, 5, 1, 1].

Pamiętaj, że nie musisz generować trójkąta Pascala, aby obliczyć sumę - to zależy od twojej implementacji, jeśli jest to krótsze, czy nie.

Wkład

Pojedyncza dodatnia nze n >= 1 w dowolnym, wygodnym formacie .

Wydajność

Powstała tablica / lista z podsumowaniem kolumnowym pierwszych nrzędów trójkąta Pascala, jak opisano powyżej. Ponownie, w dowolnym odpowiednim formacie.

Zasady

  • Wiodące lub końcowe znaki nowej linii lub białe znaki są opcjonalne, o ile same znaki są odpowiednio ustawione w linii.
  • Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
  • Jeśli to możliwe, dołącz link do internetowego środowiska testowego, aby inni mogli wypróbować Twój kod!
  • Standardowe luki są zabronione.
  • To jest więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Przykłady

[input]
[output]

1
[1]

2
[1, 1, 1]

3
[1, 1, 3, 1, 1]

5
[1, 1, 5, 4, 9, 4, 5, 1, 1]

11
[1, 1, 11, 10, 54, 44, 155, 111, 286, 175, 351, 175, 286, 111, 155, 44, 54, 10, 11, 1, 1]
AdmBorkBork
źródło

Odpowiedzi:

7

MATL , 16 bajtów

tZv=Gq:"t5BZ+]vs

Wypróbuj online!

Wyjaśnienie

To wielokrotnie stosuje splot do generowania wierszy. Na przykład dla danych wejściowych n=5zaczynamy od pierwszego wiersza

0 0 0 0 1 0 0 0 0

Rozmowa z [1 0 1]daje

0 0 0 1 0 1 0 0 0

Powtarzanie operacji daje

0 0 1 0 2 0 1 0 0

następnie

0 1 0 3 0 3 0 1 0

itd. Połączenie tych tablic w pionie i obliczenie sumy każdej kolumny daje wynik.

t       % Input n implictly. Duplicate
Zv      % Symmetric range. Gives [1 2 3 4 5 4 3 2 1] for input 5
=       % Equal to (element-wise). Gives [0 0 0 0 1 0 0 0 0]. This is the first row
Gq:     % Push [1 2 ... n-1]
"       % For each. This executes the following code n-1 times
  t     %   Duplicate
  5B    %   Push 5 in binary, that is, [1 0 1]
  Z+    %   Convolution keeping size
]       % End
v       % Concatenate all results vertically 
s       % Sum. Display implicitly.
Luis Mendo
źródło
Śmiertelność! Nie mogę przeciąć mojej liczby bajtów na pół; czubek kapelusza, proszę pana.
Magic Octopus Urn
3
@carusocomputing Dzięki :-) Wiesz, co mówią o konwolucji ...
Luis Mendo
5

CJam , 32 25 24 bajtów

Podziękowania dla Luisa Mendo za zaoszczędzenie 1 bajtu.

{(_0a*1+\{_(2$+.+}*]:.+}

Wypróbuj online!

Wyjaśnienie

(       e# Decrement input N.
_0a*1+  e# Create a list of N-1 zeros and a 1. This is the top row with
        e# the required indentation.
\{      e# Run this block N-1 times.
  _     e#   Duplicate the last row.
  (     e#   Pull off a leading zero, shifting the row left.
  2$+   e#   Copy the full row and prepend that zero, shifting the row right.
  .+    e#   Element-wise addition, which results in the next row.
}*
]       e# Wrap all rows in a list.
:.+     e# Add up the columns by reducing element-wise addition over the rows.
Martin Ender
źródło
5

JavaScript (ES6), 83 bajty

f=
n=>[...Array(n+--n)].map(g=(j=n,i,a)=>j--?g(j,i-1)+g(j,i+1)+(a?g(j,i,a):0):i-n?0:1)
<input type=number min=1 oninput=o.textContent=f(+this.value)><pre id=o>

Indeksowanie 1 kosztowało mnie bajt. Objaśnienie: g(j-1,i-1)+g(j-1,i+1)rekurencyjnie oblicza trójkąt Pascala, aż osiągnie pierwszy rząd, który jest przypadkiem podstawowym. Aby uzyskać sumy kolumn, wykorzystuję fakt, że mapfaktycznie przekazuje trzeci parametr, więc jest dodatkowy krok rekurencyjny, gdy tak jest.

Neil
źródło
5

JavaScript (ES6), 90 87 86 84 82 bajtów

Zaoszczędzono 3 bajty dzięki produktom ETH

f=(n,a=[1],b=a)=>n--?f(n,[...(F=x=>a.map((n,i)=>n+~~x[i-d]))(a,d=2),0,d=1],F(b)):b

Przypadki testowe

Arnauld
źródło
5

Mathematica, 59 57 bajtów

Podziękowania dla Martina Endera za znalezienie dwubajtowych oszczędności!

Binomial[i,(j+i)/2]~Sum~{i,Abs@j,b,2}~Table~{j,-b,b=#-1}&

Czysta funkcja pobierająca dodatnie liczby całkowite i zwracająca listę liczb całkowitych. Dosłownie tworzy wszystkie odpowiednie wpisy trójkąta Pascala i odpowiednio je sumuje.

Poprzednie zgłoszenie (które jest nieco łatwiejsze do odczytania):

Table[Sum[Binomial[i,(j+i)/2],{i,Abs@j,b,2}],{j,-b,b=#-1}]&
Greg Martin
źródło
4

Oktawa , 84 67 45 bajtów

22 bajty zapisane dzięki Neilowi !

@(n)sum(spdiags(flip(tril(flip(pascal(n))))))

Wypróbuj online!

Wyjaśnienie

pascalFunkcja daje matrycę, która zawiera wartości w trójkąt Pascala:

>> pascal(5)
ans =
     1     1     1     1     1
     1     2     3     4     5
     1     3     6    10    15
     1     4    10    20    35
     1     5    15    35    70

Aby wyodrębnić pożądane wartości, odwracamy w pionie ( flip), zachowujemy dolną trójkątną część ( tril) i ponownie odwracamy. To daje

ans =
   1   1   1   1   1
   1   2   3   4   0
   1   3   6   0   0
   1   4   0   0   0
   1   0   0   0   0

spdiags następnie wyodrębnia przekątne jako kolumny

ans =
   1   1   1   1   1   0   0   0   0
   0   0   4   3   2   1   0   0   0
   0   0   0   0   6   3   1   0   0
   0   0   0   0   0   0   4   1   0
   0   0   0   0   0   0   0   0   1

i sumoblicza sumę każdej kolumny, co daje wynik.

Luis Mendo
źródło
Nie możesz tego uprościć @(n)sum(spdiags(flip(tril(flip(pascal(n))))))?
Neil
@Neil Tak! Dziękuję Ci!!
Luis Mendo,
4

05AB1E , 34 32 28 25 24 bajtów

-4 dzięki Emignie.

FN©ƒ®Ne0})¹®-Å0.ø˜¨ˆ}¯øO

Wypróbuj online!


FN©ƒ®Ne0})               # Generate, iteratively, the current pascal row, interspersed with 0's.
          ¹®-Å0          # Calculate the number of zeros to middle pad it.
               .ø˜¨ˆ}¯øO # Surround with the zeros, transpose and sum.

Zasadniczo wszystko, co robi, to generuje to:

0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 1 0 2 0 1 0 0 0 0
0 0 0 1 0 3 0 3 0 1 0 0 0
0 0 1 0 4 0 6 0 4 0 1 0 0

Transponuj to:

0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 4
0 1 0 3 0
1 0 2 0 6
0 1 0 3 0
0 0 1 0 4
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0

Następnie sumuje każdy wiersz:

0
1
1
5
4
9
4
5
1
1
0

Jeśli wiodące i końcowe 0 są niedopuszczalne, ®>-Åoznacza ®-Åto naprawienie kary +1 bajta.


Wynik dla 50:

[0, 1, 1, 50, 49, 1224, 1175, 19551, 18376, 229125, 210749, 2100384, 1889635, 15679951, 13790316, 97994765, 84204449, 523088334, 438883885, 2421229251, 1982345366, 9833394285, 7851048919, 35371393434, 27520344515, 113548602181, 86028257666, 327340174085, 241311916419, 851817398634, 610505482215, 2009517658701, 1399012176486, 4313184213360, 2914172036874, 8448367214664, 5534195177790, 15139356846901, 9605161669111, 24871748205410, 15266586536299, 37524050574849, 22257464038550, 52060859526501, 29803395487951, 66492351226050, 36688955738099, 78239857877649, 41550902139550, 84859704298201, 43308802158651, 84859704298201, 41550902139550, 78239857877649, 36688955738099, 66492351226050, 29803395487951, 52060859526501, 22257464038550, 37524050574849, 15266586536299, 24871748205410, 9605161669111, 15139356846901, 5534195177790, 8448367214664, 2914172036874, 4313184213360, 1399012176486, 2009517658701, 610505482215, 851817398634, 241311916419, 327340174085, 86028257666, 113548602181, 27520344515, 35371393434, 7851048919, 9833394285, 1982345366, 2421229251, 438883885, 523088334, 84204449, 97994765, 13790316, 15679951, 1889635, 2100384, 210749, 229125, 18376, 19551, 1175, 1224, 49, 50, 1, 1, 0]
Urna Magicznej Ośmiornicy
źródło
1
-Å0zamiast >-Ý0*powinien działać i nie jest potrzebny na końcu.
Emigna
1
I >Fmoże być ƒ.
Emigna
Ładne połowy, o których zawsze zapominam Å, sprytne! Trzymałem „ctrl + f” dla „listy tożsamości” lub coś w tym stylu na info.txtheh ...
Magic Octopus Urn
Dopiero niedawno zacząłem pamiętać, że istnieją :)
Emigna
1
Dlaczego transpozycja zmienia to z 13 x 5na 5 x 11? Gdzie poszły pozostałe dwie kolumny / rzędy?
AdmBorkBork
4

PHP , 119 bajtów

numery kolumn od 1-wejściowego do wejściowego -1

for(;$r<$argn;$l=$t[+$r++])for($c=-$r;$c<=$r;$c+=2)$s[$c]+=$t[+$r][$c]=$r|$c?$l[$c+1]+$l[$c-1]:1;ksort($s);print_r($s);

Wypróbuj online!

Jörg Hülsermann
źródło
@LuisMendo Dziękuję Znalazłem błąd i zapisuje 3 bajty. Teraz działa z wersjami PHP większymi 5.5. array_columnto nowa funkcja w tej wersji
Jörg Hülsermann
Fajnie, gdy korekta okazuje się krótsza :-)
Luis Mendo
Oto kolejne 24 do 30 bajtów : Zapisz 13 bajtów, zamieniając liczbę wierszy i kolumn i upuszczając je array_column(). $x=2*$j++-$ioszczędza 7 bajtów. Zapętlenie $ j w dół zamiast w górę może zaoszczędzić 1 ( for($j=$i+1;$j--;)). I jeszcze 3 bajty mogą być golfowane z wyjścia.
Tytus
@Titus też było tak przyjemnie użyćarray_column
Jörg Hülsermann
Pewnego dnia zaoszczędzi bajty.
Tytus
3

Galaretka , 12 bajtów

Ḷµc€j€0Ṛṙ"NS

Wypróbuj online!

Jak to działa

Ḷµc€j€0Ṛṙ"NS  Main link. Argument: k

Ḷ             Unlength; yield A := [0, ..., k-1].
 µ            New chain. Argument: A
  c€          Combinations each; compute nCr for each n and r in A, grouping by n.
    j€0       Join each resulting array [nC0, ..., nC(k-1)], separating by zeroes,
              yielding, [nC0, 0, ..., 0, nC(k-1)].
              Note that nCr = 0 whenever r > n.
       Ṛ      Reverse the resulting 2D array.
          N   Negate A, yielding [0, ..., -(k-1)].
        ṙ"    Zipwith rotate; for each array in the result to the left and the
              corresponding integer non-positive integer to the right, rotate
              the array that many units to the left.
           S  Take the columnwise sum.
Dennis
źródło
2

Python 3, 201 184 bajtów

def f(n):x,z,m=[1],[0],n-1;l=[z*m+x+z*m];exec("x=[*map(sum,zip(z+x,x+z))];l.append(z*(n-len(x))+[b for a in zip(x,z*len(x))for b in a][:-1]+z*(n-len(x)));"*m);return[*map(sum,zip(*l))]
Uriel
źródło
2

Python 2 , 140 137 bajtów

n=input()
x=[]
a=[0]*n+[1]+n*[0]
z=n%2
exec'x+=[a];a=[(i%2^z)*sum(a[i-1:i+2])for i in range(2*n+1)];z^=1;'*n
print map(sum,zip(*x))[1:-1]

Wypróbuj online! lub Wypróbuj online!

Nan=3
początek z listą z nzerami otaczającymi jeden - [[0, 0, 0, 1, 0, 0, 0]]
Wygeneruj pełną piramidę

[[0, 0, 0, 1, 0, 0, 0],
 [0, 0, 1, 0, 1, 0, 0],
 [0, 1, 0, 2, 0, 1, 0]]

Obróć o 90º i zsumuj każdy wiersz, odrzucając pierwszy i ostatni (tylko zera)

[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 0],
 [1, 0, 2],
 [0, 1, 0],
 [0, 0, 1],
 [0, 0, 0]]
Pręt
źródło
2

Haskell, 118 112 104 bajtów

6 14 bajtów zapisanych dzięki @nimi

z=zipWith(+)
p n|n<2=[1]|m<-p(n-1)=z(0:0:m)(m++[0,0])            -- Generate the nth triangle row.
f n=foldl1 z[d++p x++d|x<-[1..n],d<-[0<$[1..n-x]]]  -- Pad each row with 0s and then sum all the rows.
Nick Hansen
źródło
Możesz skrócić funkcję wypełniania #do r#n|d<-0<$[1..n]=d++r++d.
nimi
Och, teraz możesz wstawić #, ponieważ nie jest już rekurencyjny: zdefiniuj fjako f n=foldl1 z[d++p x++d|x<-[1..n],d<-[0<$[1..n-x]]]i zrzuć #.
nimi
1

Python 3, 124 znaki

f=lambda n:[sum(map(lambda n,k:k<1or (2*k+n)*f(2*k+n-1,k-1)/k,[abs(x)]*n,range(n))[:(n+1-abs(x))/2]) for x in range(-n+1,n)]

Wykorzystuje to fakt, że Trójkąt Pascala można zdefiniować za pomocą współczynników dwumianowych. Próbowałem usunąć abs(x)i range(-n+1,n), robiąc to, range(n)a następnie używając, lambda l:l[-1:0:-1]+lale było dłużej.

To także mój pierwszy raz w golfa, więc mam nadzieję, że wybaczysz faux-pas.

Dwumian nie jest mój i został zabrany stąd .

Tilman
źródło