Jumlah Kolom Pascal

29

Kebanyakan orang di sini mengenal Segitiga Pascal. Itu dibentuk oleh baris berturut-turut, di mana setiap elemen adalah jumlah dari dua tetangga kiri atas dan kanannya. Ini adalah 5baris pertama (dipinjam dari segitiga Generate Pascal ):

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

Kita akan mengambil Pascal's Triangle dan melakukan beberapa penjumlahan di atasnya (hah-ha). Untuk input yang diberikan n, hasilkan jumlah kolom dari nbaris pertama Segitiga Pascal. Misalnya, untuk input 5, output akan dibentuk oleh

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

Jadi hasilnya akan [1, 1, 5, 4, 9, 4, 5, 1, 1].

Perhatikan bahwa Anda tidak perlu membuat Segitiga Pascal untuk menghitung penjumlahan - itu terserah implementasi Anda jika lebih pendek untuk melakukannya atau tidak.

Memasukkan

Integer positif tunggal ndengan n >= 1 format apa pun yang nyaman .

Keluaran

Array / daftar hasil penjumlahan kolom dari nbaris pertama segitiga Pascal, seperti diuraikan di atas. Sekali lagi, dalam format apa pun yang sesuai.

Aturan

  • Leading atau trailing newlines atau whitespace semuanya opsional, asalkan karakter itu sendiri berbaris dengan benar.
  • Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
  • Jika memungkinkan, harap sertakan tautan ke lingkungan pengujian online agar orang lain dapat mencoba kode Anda!
  • Celah standar dilarang.
  • Ini adalah sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.

Contohnya

[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
sumber

Jawaban:

7

MATL , 16 byte

tZv=Gq:"t5BZ+]vs

Cobalah online!

Penjelasan

Ini berulang kali menerapkan konvolusi untuk menghasilkan baris. Sebagai contoh, untuk input n=5kita mulai dengan baris pertama

0 0 0 0 1 0 0 0 0

Bergaul dengan [1 0 1]memberi

0 0 0 1 0 1 0 0 0

Mengulangi operasi memberi

0 0 1 0 2 0 1 0 0

kemudian

0 1 0 3 0 3 0 1 0

dll. Menggabungkan array-array ini secara vertikal dan menghitung jumlah setiap kolom memberikan hasilnya.

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
sumber
Kematian! Saya tidak dapat memotong byte-count saya menjadi setengah; ujung topi untuk Anda pak.
Magic Octopus Urn
3
@carusocomputing Terima kasih :-) Anda tahu apa yang mereka katakan tentang konvolusi ...
Luis Mendo
5

CJam , 32 25 24 byte

Terima kasih kepada Luis Mendo karena telah menghemat 1 byte.

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

Cobalah online!

Penjelasan

(       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
sumber
5

JavaScript (ES6), 83 byte

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>

Pengindeksan 1 biaya satu byte. Penjelasan: g(j-1,i-1)+g(j-1,i+1)secara rekursif menghitung segitiga Pascal sampai mencapai baris pertama, yang merupakan kasus dasar. Untuk mendapatkan jumlah kolom, saya menggunakan fakta yang mapbenar - benar melewati parameter ketiga, jadi ada langkah rekursif tambahan saat ini.

Neil
sumber
5

JavaScript (ES6), 90 87 86 84 82 byte

Disimpan 3 byte berkat produk 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

Uji kasus

Arnauld
sumber
5

Mathematica, 59 57 byte

Terima kasih kepada Martin Ender karena menemukan penghematan dua byte!

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

Fungsi murni mengambil input bilangan bulat positif dan mengembalikan daftar bilangan bulat. Secara harfiah menghasilkan semua entri yang relevan dari segitiga Pascal dan menjumlahkannya dengan tepat.

Kiriman sebelumnya (yang sedikit lebih mudah dibaca):

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

Oktaf , 84 67 45 byte

22 byte disimpan berkat Neil !

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

Cobalah online!

Penjelasan

The pascalFungsi memberikan matriks yang berisi nilai-nilai dalam segitiga Pascal:

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

Untuk mengekstrak nilai yang diinginkan, kami membalik secara vertikal ( flip), menjaga bagian segitiga bawah ( tril), dan membalik lagi. Ini memberi

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 lalu ekstrak diagonal sebagai kolom

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

dan summenghitung jumlah setiap kolom, yang memberikan hasilnya.

Luis Mendo
sumber
Tidak bisakah Anda menyederhanakan hal itu @(n)sum(spdiags(flip(tril(flip(pascal(n))))))?
Neil
@Neil Ya! Terima kasih!!
Luis Mendo
4

05AB1E , 34 32 28 25 24 byte

-4 Terima kasih kepada Emigna.

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

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

Pada dasarnya yang dilakukan adalah menghasilkan ini:

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

Ubah itu:

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

Kemudian jumlah setiap baris:

0
1
1
5
4
9
4
5
1
1
0

Jika 0 yang memimpin dan mengikuti tidak dapat diterima, ®>-Åbukan ®-Åperbaikan untuk penalti +1 byte.


Hasil untuk 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]
Guci Gurita Ajaib
sumber
1
-Å0alih-alih >-Ý0*harus bekerja dan tidak diperlukan pada akhirnya.
Emigna
1
Dan >Fbisa jadi ƒ.
Emigna
Tangkapan bagus, aku selalu lupa Å, pintar! Saya menyimpan "ctrl + f" untuk "daftar identitas" atau sesuatu seperti itu di info.txtheh ...
Magic Octopus Mm
Saya baru saja mulai mengingat bahwa mereka ada :)
Emigna
1
Mengapa transpose mengubahnya dari 13 x 5menjadi 5 x 11? Ke mana dua kolom / baris lainnya pergi?
AdmBorkBork
4

PHP , 119 byte

nomor kolom dari 1-input ke input -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);

Cobalah online!

Jörg Hülsermann
sumber
@LuisMendo Terima kasih, saya telah menemukan kesalahan dan menghemat 3 Bytes. Sekarang ini berfungsi dengan Versi PHP lebih besar 5.5. array_columnadalah fungsi baru dalam versi ini
Jörg Hülsermann
Sangat menyenangkan ketika koreksi ternyata lebih pendek :-)
Luis Mendo
Berikut ini adalah 24 hingga 30 byte lainnya : Hemat 13 byte dengan menukar jumlah baris dan kolom dan menjatuhkannya array_column(). $x=2*$j++-$imenghemat 7 byte. Looping $ j ke bawah alih-alih bisa menghemat 1 ( for($j=$i+1;$j--;)). Dan 3 byte lagi dapat di-golf dari output.
Titus
@Itus itu sangat bagus juga digunakanarray_column
Jörg Hülsermann
Suatu hari nanti akan menghemat byte.
Titus
3

Jelly , 12 byte

Ḷµc€j€0Ṛṙ"NS

Cobalah online!

Bagaimana itu bekerja

Ḷµ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
sumber
2

Python 3, 201 184 byte

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
sumber
2

Python 2 , 140 137 byte

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]

Cobalah online! atau Coba online!

Untukn=3
Mulai dengan daftar dengan nangka nol mengelilingi angka satu - [[0, 0, 0, 1, 0, 0, 0]]
Hasilkan piramida lengkap

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

Putar 90º dan jumlah setiap baris, buang yang pertama dan yang terakhir (hanya nol)

[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 0],
 [1, 0, 2],
 [0, 1, 0],
 [0, 0, 1],
 [0, 0, 0]]
tongkat
sumber
2

Haskell, 118 112 104 byte

6 14 byte disimpan berkat @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
sumber
Anda dapat mempersingkat fungsi bantalan #ke r#n|d<-0<$[1..n]=d++r++d.
nimi
Oh, sekarang Anda bisa sebaris #, karena tidak rekursif lagi: tentukan fsebagai f n=foldl1 z[d++p x++d|x<-[1..n],d<-[0<$[1..n-x]]]dan buang #.
nimi
1

Python 3, 124 karakter

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

Ini menggunakan fakta bahwa Segitiga Pascal dapat didefinisikan dengan koefisien binomial. Saya mencoba menghapus abs(x)dan range(-n+1,n)dengan membuatnya range(n)dan kemudian menggunakan lambda l:l[-1:0:-1]+ltetapi lebih lama.

Juga ini kali pertama saya bermain golf, jadi saya harap Anda memaafkan kecerobohan.

Binomial bukan milikku dan diambil dari sini .

Tilman
sumber