V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Tiande
V2EX  ›  Python

这段 杨辉三角 的算法,真漂亮...

  •  
  •   Tiande ·
    Tiande · 2015-06-17 14:42:56 +08:00 · 10174 次点击
    这是一个创建于 3208 天前的主题,其中的信息可能已经有所发展或是发生改变。

    来源 (代码在评论中)

    代码:

    def triangles():
    ....a = [1];
    ....while True:
    ........yield a
    ........a = [sum(i) for i in zip([0] + a, a + [0])]

    部分结果:

    $ python python/pytest.py
    [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]
    

    真是爆za了 ;)

    45 条回复    2015-06-26 17:12:38 +08:00
    ColorfulNight
        1
    ColorfulNight  
       2015-06-17 14:46:48 +08:00
    我用C的队列写过,但是不知道为什么当行数一大就会出错
    sinux
        2
    sinux  
       2015-06-17 14:52:33 +08:00
    nice job
    elvis_w
        3
    elvis_w  
       2015-06-17 15:09:37 +08:00
    Python的生成器函数,不错
    zerh925
        4
    zerh925  
       2015-06-17 15:46:21 +08:00   ❤️ 1
    之前看到使用yield生成fab数,从最简单的方法,到使用list存储,再到定义一个类的next()方法,最后再来一记yield,真是惊艳到了。
    66beta
        5
    66beta  
       2015-06-17 15:49:16 +08:00   ❤️ 1
    哼,格式不对,没对齐
    est
        6
    est  
       2015-06-17 15:51:31 +08:00   ❤️ 1
    pascal = map ([1,1]^) [0..]
    take 5 pascal -- [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]

    还是有更加高级的语言的描述能力能秒杀python的。
    est
        7
    est  
       2015-06-17 15:54:32 +08:00   ❤️ 2
    定义一个函数 fib 用来输入任意位的Fibonacci 数列

    fib 0 = 0
    fib 1 = 1
    fib n = fib (n-1) + fib (n-2)
    TimLang
        8
    TimLang  
       2015-06-17 16:03:47 +08:00
    看了下python的yield和ruby的yield完全不是一个意思啊。下面是Ruby代码,ruby不需要生成器。

    ```ruby
    def pascal(n)
    ar = [1]
    while n > 1
    ar.unshift(0).push(0) # tack a zero on both ends
    yield ar = ar.each_cons(2).map{|a, b| a + b }
    n=n-1
    end
    end
    puts pascal(5){|row| p row}
    ···
    codercai
        9
    codercai  
       2015-06-17 16:28:56 +08:00
    graceful job!
    Vlux
        10
    Vlux  
       2015-06-17 16:38:15 +08:00
    人生苦短。pythonic
    some0ne
        11
    some0ne  
       2015-06-17 16:41:47 +08:00   ❤️ 1
    ```ruby

    triangles = Enumerator.new do |yielder|
    a = [1]
    loop do
    yielder << a
    a = ([0] + a).zip(a + [0]).map {|i| i.reduce(:+) }
    end
    end

    triangles.take(10).each {|row| p row }

    ```

    相同功能的ruby版
    Tiande
        12
    Tiande  
    OP
       2015-06-17 16:48:02 +08:00
    @some0ne 连函数名都一样 hhh
    Tiande
        13
    Tiande  
    OP
       2015-06-17 16:49:06 +08:00
    @est 这是啥语言
    (已匍匐在石榴裙下)
    some0ne
        14
    some0ne  
       2015-06-17 16:58:18 +08:00   ❤️ 1
    @dtdnqsb 变量名随便起,一样只不过是为了跟LZ的代码对应。你要是不喜欢,我改成 `杨辉三角.take(10)` 怎么样?
    jsyangwenjie
        15
    jsyangwenjie  
       2015-06-17 17:00:49 +08:00   ❤️ 1
    这。。
    你随便学一门函数式语言就写得出来的。。
    est
        16
    est  
       2015-06-17 17:00:56 +08:00   ❤️ 1
    @dtdnqsb 当然是我大Haskell 。
    luciankaltz
        17
    luciankaltz  
       2015-06-17 17:21:32 +08:00
    Python弱鸡被惊艳到了。。。
    Tiande
        18
    Tiande  
    OP
       2015-06-17 17:58:18 +08:00
    @some0ne 我是说 zip() 不是变量名 hhh
    Tiande
        19
    Tiande  
    OP
       2015-06-17 17:59:31 +08:00
    @jsyangwenjie 你就随便拿顺手的语言写个如此简洁的,让大家活儿好好乐乐?
    没有嘲讽的意思 -。-
    Tiande
        20
    Tiande  
    OP
       2015-06-17 17:59:58 +08:00
    @est 好好好,立马去跪舔
    pubby
        21
    pubby  
       2015-06-17 18:26:49 +08:00 via Android
    坐等PHP版
    ob
        22
    ob  
       2015-06-17 18:41:07 +08:00
    zip里面是啥?
    zonghua
        23
    zonghua  
       2015-06-17 18:41:49 +08:00 via iPhone
    人生苦短,为了排个杨辉三角,耗费了多少脑力。
    jsyangwenjie
        24
    jsyangwenjie  
       2015-06-17 19:08:54 +08:00   ❤️ 1
    @dtdnqsb
    yang::Int -> [Int]
    yang n
    | n == 0 = [1]
    | otherwise = map (\x-> fst x + snd x) $ zip ([0] ++ yang (n-1)) (yang (n-1) ++ [0])
    这是人家玩烂了的。。
    lilydjwg
        25
    lilydjwg  
       2015-06-17 19:14:59 +08:00
    @est ^ 是什么操作?我这里报错了。

    PS: 斐波那契数列不是 fibs = scanl (+) 0 (1:fibs) 么 ;-)
    lilydjwg
        26
    lilydjwg  
       2015-06-17 19:15:25 +08:00   ❤️ 1
    @est 好像这个更流行: fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
    staticor
        27
    staticor  
       2015-06-17 20:53:54 +08:00
    xuyl
        28
    xuyl  
       2015-06-17 21:10:36 +08:00
    @dtdnqsb 那么这个函数怎么迭代运行呢?求教。都不带参数来着
    horx
        29
    horx  
       2015-06-17 21:11:00 +08:00
    Fibonacci 数列 Elixir 版:
    def fib(n) when n < 1, do: n
    def fib(n), do: fib(n -1) + fib(n - 2)
    horx
        30
    horx  
       2015-06-17 21:12:39 +08:00   ❤️ 1
    上门第一行写错了, 是 def fib(n) when n <= 1, do:n
    zerh925
        31
    zerh925  
       2015-06-17 22:21:47 +08:00
    @staticor 对 就是这篇
    karloku
        32
    karloku  
       2015-06-17 23:04:31 +08:00   ❤️ 1
    pascal = lambda do |n|
    | n.times.reduce([[1]]) do |rows|
    | rows << ([0] + rows.last).zip(rows.last + [0]).map {|i| i.reduce(&:+)}
    | end
    end
    Tiande
        33
    Tiande  
    OP
       2015-06-17 23:12:55 +08:00
    @xuyl
    # 函数写好后,实例化
    result = triangles()

    i = 1
    for a in result:
    ....i = i + 1
    ....print(a)
    ....if i > 10: # 限定循环次数
    ........break
    Tiande
        34
    Tiande  
    OP
       2015-06-17 23:21:59 +08:00
    @jsyangwenjie
    谢谢,然而并不懂你说的函数式编程...
    msg7086
        35
    msg7086  
       2015-06-18 07:32:12 +08:00   ❤️ 1
    4 kyu Pascal's Triangle
    Ruby:

    def pascalsTriangle(n)
    result = p = [1]
    (n-1).times do
    p = (p+[0]).zip([0]+p).map{|v|v.reduce(&:+)}
    result += p
    end
    result
    end
    4 days ago

    前几天刚写过。
    lds56
        36
    lds56  
       2015-06-18 10:26:30 +08:00   ❤️ 1
    Scala 版本

    def tri(row:Int):List[Int] = { row match {
    case 1 => List(1)
    case n:Int => List(1) ::: ((tri(n-1) zip tri(n-1).tail) map {case (a,b) => a+b}) ::: List(1)
    }
    }

    def prettytri(n:Int) = (1 to n) foreach {i=>print(" "*(n-i)); tri(i) map (c=>print(c+" ")); println}
    prettytri(5)

    出自 http://rosettacode.org/wiki/Pascal's_triangle
    lds56
        37
    lds56  
       2015-06-18 10:29:00 +08:00
    感觉 python 的生成器还是不够优雅
    xiaoxianyu
        38
    xiaoxianyu  
       2015-06-18 11:26:35 +08:00   ❤️ 1
    很美丽~zip原来有这么赞的用法~~~
    dsdshcym
        39
    dsdshcym  
       2015-06-18 14:38:39 +08:00
    @lds56
    yuankui
        40
    yuankui  
       2015-06-18 14:56:32 +08:00
    性能堪忧啊...
    yuankui
        41
    yuankui  
       2015-06-18 14:56:56 +08:00
    好多列表的concat
    wizardoz
        42
    wizardoz  
       2015-06-18 14:57:30 +08:00
    @xuyl
    for i,l in zip(range(10),triangles()):
    ....print(l)
    forrestchang
        43
    forrestchang  
       2015-06-18 15:16:59 +08:00   ❤️ 1
    刚学Swift, 用Swift写了一个,基本的方法
    func pascalsTriangle(rows: Int) {
    if rows < 0 {
    return
    }

    var last = [Int]()
    last.append(1)
    println(last)

    for i in 1..<rows {
    var thisRow = [Int]()
    thisRow.append(last.first!)
    for j in 1..<i {
    thisRow.append(last[j - 1] + last[j])
    }
    thisRow.append(last.first!)
    last = thisRow
    println(thisRow)
    }

    }
    shizukoto
        44
    shizukoto  
       2015-06-18 23:20:02 +08:00   ❤️ 2
    JavaScript (ES6) 实现:

    ```js
    const {zip, sum, map, head} = require('aureooms-js-itertools');

    function *triangles() {
    let a = [1];
    while (true) {
    yield a;
    a = Array.from(map(sum, zip([[0].concat(a), a.concat([0])])));
    }
    }

    for (let row of head(triangles(), 5)) console.log(row.join(' '));

    ```
    Hchan
        45
    Hchan  
       2015-06-26 17:12:38 +08:00   ❤️ 1
    lazy val tri: Stream[List[Int]] = List(1) #:: tri map {s => (0 :: (s :+ 0)).sliding(2).toList.map(_.sum)}
    @lds56
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2843 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 14:34 · PVG 22:34 · LAX 07:34 · JFK 10:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.