编码高尔夫：生成帕斯卡三角形

Question

编码高尔夫：生成帕斯卡三角形

algorithmcode-golfcombinatoricsdiscrete-mathematicspascals-triangle

37

用尽可能少的代码生成大小为N的 Pascal三角形的列表（或者打印，我不介意！）

这是我用Python 2.6和一个技巧尝试的结果（只需118个字符）：

c,z,k=locals,[0],'_[1]'
p=lambda n:[len(c()[k])and map(sum,zip(z+c()[k][-1],c()[k][-1]+z))or[1]for _ in range(n)]

解释：

当长度为0时，列表推导式的第一个元素是[1]
下一个元素是通过以下方式获得的：
取前一个列表并创建两个新列表，一个在开头填充0，另一个在末尾填充0。
- 例如，对于第二步，我们取[1]并创建[0,1]和[1,0]
逐个元素将两个新列表相加
- 例如，我们创建一个新列表[(0,1),(1,0)]并使用sum映射。
重复n次，完成。

用法（带漂亮打印，实际上是出自Code Golf）：

result = p(10)
lines = [" ".join(map(str, x)) for x in result]
for i in lines:
    print i.center(max(map(len, lines)))

输出：

             1             
            1 1            
           1 2 1           
          1 3 3 1          
         1 4 6 4 1         
       1 5 10 10 5 1       
      1 6 15 20 15 6 1     
    1 7 21 35 35 21 7 1    
   1 8 28 56 70 56 28 8 1  
1 9 36 84 126 126 84 36 9 1

- fortran

3

如果这个被关闭了，我会投票支持重新开放。我喜欢代码高尔夫，但我不明白为什么有人对它看不惯。请注意，翻译过程中保留原义，使语言更通俗易懂。 - Kenan Banks

2

也许只是我个人的看法，但是如果你的编程语言无法解析XML文件，我就不会点赞。 - Kenan Banks

3

@fortran，我对两者都很熟悉。我的意思是，专门用于代码高尔夫的语言，例如K和J，在代码高尔夫问题中获得最多的赞，但你永远不会在其他情况下使用它们。比起20个字符的J解决方案，我更加钦佩一个50个字符的C解决方案。 - Kenan Banks

2

@Triptych：K和J不是专门用于代码高尔夫的语言。此外，J似乎有用于XML的模块，例如http://www.jsoftware.com/jwiki/Addons/xml/sax。 - Jimmy

2

@Triptych：那么金融行业一定在进行很多代码高尔夫比赛了：http://kx.com/Customers/end-user-customers.php - earl

显示剩余4条评论

23个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DJ. · Answer 1

VBA/VB6 (392 chars w/ formatting)

Public Function PascalsTriangle(ByVal pRows As Integer)

Dim iRow As Integer
Dim iCol As Integer
Dim lValue As Long
Dim sLine As String

  For iRow = 1 To pRows
    sLine = ""
    For iCol = 1 To iRow
      If iCol = 1 Then
        lValue = 1
      Else
        lValue = lValue * (iRow - iCol + 1) / (iCol - 1)
      End If
      sLine = sLine & " " & lValue
    Next
    Debug.Print sLine
  Next

End Function

- Nietzche-jou · Answer 2

Scheme - 100个字符的压缩版本

(define (P h)(define (l i r)(if (> i h) '() (cons r (l (1+ i) (map + (cons 0 r) (append r '(0))))))(l 1 '(1)))

这是更易读的形式（269个字符）：

(define (pascal height)
  (define (next-row row)
    (map +
         (cons 0 row)
         (append row '(0))))
(define (iter i row)
    (if (> i height)
        '()
        (cons row
              (iter (1+ i)
                    (next-row row)))))
(iter 1 '(1)))

- fortran · Answer 3

另一次尝试，在Prolog（我在练习xD），不太短，正好164个字符：

s([],[],[]).
s([H|T],[J|U],[K|V]):-s(T,U,V),K is H+J.
l([1],0).
l(P,N):-M is N-1,l(A,M),append(A,[0],B),s(B,[0|A],P).
p([],-1).
p([H|T],N):-M is N-1,l(H,N),p(T,M).

说明：

s = 逐个元素相加的列表
l = 第N行三角形
p = 大小为N的整个三角形

- fortran · Answer 4

另一个Python解决方案，如果内置函数名称更短，可能会更短...106个字符。

from itertools import*
r=range
p=lambda n:[[len(list(combinations(r(i),j)))for j in r(i+1)]for i in r(n)]

- Andrew Y · Answer 5

Ruby，83c：

def p(n);n>0?(m=p(n-1);k=m.last;m+[([0]+k).zip(k+[0]).map{|x|x[0]+x[1]}]):[[1]];end

测试：

irb(main):001:0> def p(n);n>0?(m=p(n-1);k=m.last;m+[([0]+k).zip(k+[0]).map{|x|x[0]+x[1]}]):[[1]];end
=> nil
irb(main):002:0> p(5)
=> [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
irb(main):003:0>

- Skizz · Answer 6

我几年前写了这个C++版本：

#include <iostream>
int main(int,char**a){for(int b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0;b<atoi(a[1]);(d|f|h)>1?e*=d>1?--d:1,g*=f>1?--f:1,i*=h>1?--h:1:((std::cout<<(i*g?e/(i*g):1)<<" "?d=b+=c++==b?c=0,std::cout<<std::endl?1:0:0,h=d-(f=c):0),e=d,g=f,i=h));}

- user306970 · Answer 7

VBA，122个字符：

Sub p(n)
For r = 1 To n
l = "1"
v = 1
For c = 1 To r - 1
v = v / c * (r - c)
l = l & " " & v
Next
Debug.Print l
Next
End Sub

- Michael Puckett · Answer 8

虽然这是一个旧帖子，但我今天在另一个论坛上回应了一个挑战，写下了以下内容：

def pascals_triangle(n):
    x=[[1]]
    for i in range(n-1):
        x.append([sum(i) for i in zip([0]+x[-1],x[-1]+[0])])
    return x

for x in pascals_triangle(5):
    print('{0:^16}'.format(x))

      [1]       
     [1, 1]     
   [1, 2, 1]    
  [1, 3, 3, 1]  
[1, 4, 6, 4, 1]

- pavium · Answer 9

一个Perl版本（不带shebang的139个字符）

@p = (1,1);
while ($#p < 20) {
    @q =();
    $z = 0;
    push @p, 0;
    foreach (@p) {
        push @q, $_+$z;
        $z = $_
    }
    @p = @q;
    print "@p\n";
}

输出从 1 2 1 开始

- Hugh Bothwell · Answer 10

PHP，115个字符

$t[][]=1;
for($i=1;$i<$n;++$i){
$t[$i][0]=1;
for($j=1;$j<$i;++$j)$t[$i][$j]=$t[$i-1][$j-1]+$t[$i-1][$j];
$t[$i][$i]=1;}

如果您不关心print_r()是否按正确顺序显示输出数组，您可以将其缩短到113个字符，如下所示：

$t[][]=1;
for($i=1;$i<$n;++$i){
$t[$i][0]=$t[$i][$i]=1;
for($j=1;$j<$i;++$j)$t[$i][$j]=$t[$i-1][$j-1]+$t[$i-1][$j];}