帕斯卡尔三角形在哈斯克尔 [英] Pascal Triangle in Haskell
问题描述
我是Haskell的新手，我真的需要一些帮助！
我必须编写一个包含递归函数的程序，以产生一个二项式系数列表使用帕斯卡三角技术的功率n = 12。
我在脑海中有一些想法，但是因为我刚刚开始，我不知道如何实现这一点haskell？！
有人能帮我解决吗？
第一行：（a + b）^ 0 = 1第二行：（a + b）^ 1 = 1a + 1b
第三行：（a + b）^ 2 = 1a ^ 2 + 2ab + 1b ^ 2
等等...这是我的主要想法。但我甚至不能尝试这一点，因为我不知道我是如何把它放在Haskell中的。所有的时间都是错误的
解决方案首先为三角形中的每个元素分配索引： 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
在这里，我只是将三角形放在一边，以便我们可以对它们进行编号。所以这里我要说（6，4）的元素是 15 ，而（4，6）不存在。现在着眼于编写一个函数
pascal :: Integer - >整数 - >整数
pascal x y = ???
这样就可以生成这个版本的三角形。你可以从写作
pascal x y
| x == 0 = 1
| x == y = 1
| x < y =错误不是帕斯卡三角形的有效坐标。
|否则= pascal？ ？ +帕斯卡？ ？
请注意，在这里，不要确定哪些元素应该通过对角线添加在一起，您可以做到这一点通过直角坐标。在这里，你会注意到 y 是你所在三角形的哪一行， x 是该行中的元素。所有你需要做的就是弄清楚？ s。
一旦你得到那个工作，我对这个三角形有一个单行线，效率更高，可以一次生成整个三角形，同时仍然使用递归：
import Data.List（scanl1）
pascals :: [[Integer]]
pascals = repeat 1：map（scanl1（+））pascals
不要试着将这个解决方案转给你的教授，这不是他们想要的，它会让它变得非常明显如果你只有一个星期在做Haskell，有人给了你这个解决方案。但是，它确实显示了Haskell对于这类问题有多强大。我将展示如何索引 pascals 以获得给定的（n，k）值，但这样做也会给你提供了太多解决幼稚递归的提示。
由于存在一些混淆，我给出这个解决方案的原因是在它和经常显示的懒惰之间画一个平行线实现Fibonacci序列：
fibs = 1：1：zipWith（+）fibs（尾纤）
与
相比 fib 0 = 1
fib 1 = 1
fib n = fib（n - 1）+ fib（n - 2）
这个定义生成了所有斐波纳契数的无限列表，并且非常高效（从CPU的角度来看，RAM是一个不同的故事）。它在前2个元素中编码基本情况，然后是递归表达式，可以计算剩余的情况。对于斐波那契数列，你需要2个数值来开始你，但对于帕斯卡三角形来说，你只需要一个数值，那个数值恰好是一个无限列表。在上面发布的网格中有一个很容易看到的模式， scanl1（+）函数只是利用了这种模式，并且允许我们生成它很容易，但这是产生三角形的对角线而不是行。为了获得行，你可以为这个列表建立索引，或者你可以用 take ， drop 来做一些奇特的技巧，其他此类功能，但这是另一天的练习。
I'm new to Haskell and I really need some help!
I have to write a program that includes a recursive function to produce a list of binomial coefficients for the power n=12 using the Pascal's triangle technique.
I have some ideas in my head but because I'm just getting started I have no idea how to implement this to haskell?!
Could someone please help me out??
first row: (a+b)^0 = 1
second row: (a+b)^1 = 1a+1b
third row: (a+b)^2 = 1a^2+2ab+1b^2
and so on...this is my main idea. But I cant even try this out because I have no idea how I put this in Haskell..getting errors all the time
Start by assigning an index to each element in the triangle:
| 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
Here I've simply put the triangle on its side so that we can number them. So here I'd say that the element at (6, 4) is 15, whereas (4, 6) doesn't exist. Now focus on writing a function
pascal :: Integer -> Integer -> Integer
pascal x y = ???
Such that you can generate this version of the triangle. You can start by writing
pascal x y
| x == 0 = 1
| x == y = 1
| x < y = error "Not a valid coordinate for Pascal's triangle."
| otherwise = pascal ? ? + pascal ? ?
Note that here, instead of figuring out which elements should be added together by diagonals, you can do it via rectangular coordinates. Here, you'll note that y is which row in the triangle you're on and x is the position of the element in that row. All you need to do is figure out what goes in place of the ?s.
Once you get that working, I've got a one-liner for this triangle that is more efficient and can generate the entire triangle all at once while still using recursion:
import Data.List (scanl1)
pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals
Don't try turning this solution in to your professor, it's not what they're looking for and it would make it pretty obvious someone gave you this solution if you've only been doing Haskell for a week. However, it really shows how powerful Haskell can be for this sort of problem. I would show how to index pascals to get a given (n, k) value, but doing so would also give you too many hints for solving the naive recursion.
Since there's been some confusion, the reason why I gave this solution is to draw a parallel between it and the often shown lazy implementation for the Fibonacci sequence:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Compared to
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
This definition generates an infinite list of all the Fibonacci numbers, and does so quite efficiently (from the point of view of the CPU, RAM is a different story). It encodes in its first 2 elements the base case, then a recursive expression that can calculate the rest. For the Fibonaccis, you need 2 values to start you off, but for Pascal's triangle, you only need one value, that value just happens to be an infinite list. There is an easy to see pattern going across the columns in the grid I posted above, the scanl1 (+) function just takes advantage of this pattern and allows us to generate it very easily, but this is generating the diagonals of the triangle rather than the rows. To get the rows, you can index this list, or you can do some fancy tricks with take, drop, and other such functions, but that's an exercise for another day.
这篇关于帕斯卡尔三角形在哈斯克尔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
