haskell - 如何在haskell中正确解决帕斯卡三角形？

Question

我在 Haskell 中实现 Pascal Triangle，但代码工作不正确。该代码又提供了 1 行。我也试图像一棵树一样打印结果，但这对我来说很困难和困惑，所以我没有添加打印代码。

这些是我得到的结果：

*Main> pascal 1
[[1],[1,1]]
*Main> pascal 2
[[1],[1,1],[1,2,1]]

预期输出：

*Main> pascal 2
    [[1],[1,1]]

理想输出：

*Main> pascal 3
           
         1  
        1 1 
       1 2 1

这是代码：

choose n 0 = 1
choose 0 k = 0
choose n k = choose (n-1) (k-1)* n `div` k

pascal :: Integer -> [[Integer]]
pascal 0 = [[1]]
pascal m = pascal (m - 1) ++ [[choose m k | k <- [0,1..m]]]

标签： haskellrecursionpascals-triangle

Answer 1

首先让我注意到你的方法有点倒退。帕斯卡三角形的全部要点在于它提供了一种有效的方法来将choose函数制成表格，而无需单独计算每个值。这并不意味着你的做法是错误的，但它肯定不是很好。请尝试在没有该choose功能的情况下解决问题！你知道，

                 1
                ╱ ╲
               1   1
              ╱ ╲+╱ ╲
             1   2   1
            ╱ ╲+╱ ╲+╱ ╲
           1   3   3   1
          ╱ ╲+╱ ╲+╱ ╲+╱ ╲
         1   4   6   4   1
        ...     ...     ...

提示：不要从编写一个计算整个三角形或单个元素的函数开始，而是先编写一个计算三角形的一行并为您提供下一行的函数。然后剩下要做的就是执行iterate该功能。

至于如何在您当前的方法中修复它 - 好吧，显然如果您想pascal 1屈服，[[1]]那么pascal 0 = [[1]]就不是一个非常明智的基本案例。而是从_

pascal 1 = [[1]]

或者

pascal 0 = []

（这更好一点，因为函数不会为零定义……但仍然是负数——我们希望避免这种情况，或者至少在这种情况下给出明确的错误消息。）

然后，对于第mth 行，您应该只计算choose (m-1) k系列。易于修复。记住还要选择正确的范围k。

至于如何以漂亮的等腰形状漂亮地打印输出：编写一个辅助函数

centerAlign :: [String] -> [String]

它在每一行的前面添加了空白，与-length相比，它对应于它所缺少的一半。maximumlength

然后你可以简单地putStrLn . unlines . centerAlign . map show在帕斯卡三角形上做。