5

我是 Haskell 的新手，我真的需要一些帮助！

我必须编写一个包含递归函数的程序，以使用帕斯卡三角技术生成幂 n=12 的二项式系数列表。

我脑子里有一些想法，但是因为我才刚刚开始，所以我不知道如何将它实施到haskell？！

有人可以帮我吗？

first row: (a+b)^0 = 1
second row: (a+b)^1 = 1a+1b
third row: (a+b)^2 = 1a^2+2ab+1b^2

等等......这是我的主要想法。但我什至不能尝试这个，因为我不知道我是如何把它放在 Haskell 中的......一直出错

4

4 回答 4

9

首先为三角形中的每个元素分配一个索引：

  | 0 1 2 3 4 5 6
--+--------------
0 | 1
1 | 1 1
2 | 1 2 1
3 | 1 3 3 1
4 | 1 4 6 4 1
5 | 1 5 10 10 5 1
6 | 1 6 15 20 15 6 1

在这里，我只是将三角形放在一边，以便我们对它们进行编号。所以在这里我会说元素 at (6, 4)is 15, while(4, 6)不存在。现在专注于写一个函数

pascal :: Integer -> Integer -> Integer
pascal x y = ???

这样您就可以生成此版本的三角形。你可以从写作开始

pascal x y
    | x == 0 = 1
    | x == y = 1
    | x <  y = error "Not a valid coordinate for Pascal's triangle."
    | otherwise = pascal ? ? + pascal ? ?

请注意，在这里，您可以通过直角坐标来确定哪些元素应该通过对角线添加在一起，而不是确定。在这里，您会注意到您y所在的三角形中的哪一行，以及该行中x元素的位置。您需要做的就是找出代替?s 的内容。

一旦你开始工作，我就为这个三角形提供了一个更有效的单线，并且可以在仍然使用递归的同时一次生成整个三角形：

import Data.List (scanl1)

pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals

不要试图把这个解决方案交给你的教授，这不是他们想要的，如果你只用了一周的 Haskell，就会很明显有人给了你这个解决方案。但是，它确实显示了 Haskell 对此类问题的强大功能。我将展示如何通过索引pascals来获得给定的(n, k)值，但这样做也会为您提供太多解决朴素递归的提示。

由于存在一些混淆，我给出这个解决方案的原因是为了在它和斐波那契序列的经常显示的惰性实现之间画一个平行线：

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

相比

fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

这个定义生成了所有斐波那契数的无限列表，并且这样做非常有效（从 CPU 的角度来看，RAM 是另一回事）。它在其前两个元素中编码基本情况，然后是可以计算其余部分的递归表达式。对于斐波那契，您需要 2 个值才能开始，但对于帕斯卡三角形，您只需要一个值，该值恰好是一个无限列表。我在上面发布的网格中的列之间有一个很容易看到的模式，该scanl1 (+)函数只是利用了这种模式并允许我们非常容易地生成它，但这是生成三角形的对角线而不是行。要获取行，你可以索引这个列表，或者你可以做一些花哨的技巧take，drop和其他类似功能，但这是另一天的练习。

于 2014-12-01T17:33:56.850 回答
7

从三角形本身开始：

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

您应该注意到，要写下下一行，您必须应用此规则：将前一行的相邻元素相加，使用 a0表示孤独的边缘元素。视觉上：

    0   1   0
     \+/ \+/
  0   1   1   0
   \+/ \+/ \+/
0   1   2   1   0
 \+/ \+/ \+/ \+/
  1   3   3   1
       ...

在操作上，它看起来像这样：

For row 0:
[1]  (it's a given; i.e. base case)

For row 1:
[0, 1]   <- row 0 with a zero prepended ([0] ++ row 0)
 +  +
[1, 0]   <- row 0 with a zero appended  (row 0 ++ [0])
 =  =
[1, 1]   <- element-wise addition

For row 2:
[0, 1, 1]
 +  +  +
[1, 1, 0]
 =  =  =
[1, 2, 1]

Generally, for row N:

element-wise addition of:
  [0] ++ row(N-1)
  row(N-1) ++ [0]

请记住，在 Haskell 中按元素添加列表是zipWith (+).

因此，我们得出以下 Haskell 定义：

pascal 0 = [1]
pascal n = zipWith (+) ([0] ++ pascal (n-1)) (pascal (n-1) ++ [0])

或者以类似于著名的“懒惰谎言”的方式：

pascals = [1] : map (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) pascals
于 2017-07-09T17:32:42.460 回答
2

另一种可能的解决方案（我认为更适合初学者）：

pascal :: Integer -> [Integer]
pascal 0 = [1]
pascal 1 = [1, 1]
pascal n = let p = pascal (n - 1)
    in [1] ++ pascalStep p ++ [1]

pascalStep :: [Integer] -> [Integer]
pascalStep [] = []
pascalStep [_] = []
pascalStep (x:y:xs) = x + y : pascalStep (y : xs)

使用let以避免更多的空间使用。 pascal递归调用以查找所有先前的行，使用它们来获取下一行，直到到达所需的行。

输出：

*Main> pascal 3
[1,3,3,1]
*Main> pascal 4
[1,4,6,4,1]
*Main> pascal 5
[1,5,10,10,5,1]
于 2018-04-12T08:48:08.113 回答
0

从基本情况开始。

pascal 0 0 = 1

然后处理边缘情况

pascal n 0 = 1
pascal n r | n == r = 1

现在用递归步骤展开

pascal n r = pascal (n - 1) (r - 1) + pascal (n - 1) r

如果您想要特定行的列表，请编写一个包装器

binom n = map (pascal n) [0..n]

弄清楚类型应该不难

pascal :: Integral a => a -> a -> a
binom :: Integral a => a -> [a]
于 2014-12-01T16:58:04.090 回答