Horner关于双变量多项式的规则 [英] Horner's rule for two-variable polynomial
问题描述
我很容易将使用SML的方法应用于一个变量多项式，表示为一个int列表：
<$ p $ （fn（a，b）=> a + b * x）（0.0）coeffList
这很好。然后我们可以使用它：
- val test = horner [1.0，2.0，3.0] 2.0;
> val test = 17.0：real
其中 [1.0，2.0，3.0] 是表示多项式系数的列表， 2.0 是变量x的值， 17.0 是评估多项式的结果。
我的问题是这样的：我们有一个两个变量多项式， ）。高级列表中的第n项将表示包含y ^ n的所有多项式项，并且低级列表中的第m项将表示包含x ^ m的所有多项式项。
例如： [[2]，[3,0,0,3]，[1,2]] 是多项式
lockquote
（2（x ^ 0）（y ^ 0））+ -
（3（x ^ 0）（y ^ 1） ）+ 0（x ^ 1）（y ^ 1）+ 0（x ^ 2）（y ^ 1）+3（x ^ 3）（y ^ 1））+ -
（1（x ^ b
该函数需要返回
我尝试过使用mlton编译器的各种方法。
<首先我尝试了一个嵌套的foldr函数：
fun evalXY（z :: zs）xy =
foldr
（fn（s，li：list）=>
s +（（foldr（fn（a，b）=> a + b * x）0 li）* y）
）
0
z：zs
你可以看到我试图使用s作为累加器，就像在单个变量示例中使用a一样。由于foldr处理的每个元素都需要折叠，所以我在描述外部折叠器的函数中再次调用foldr。我知道这个内部折叠器工作正常，我在上面证明了它。 *我的问题似乎是我无法访问外部折叠器所在列表中的元素，以将该列表传递给内部折叠器。 >看看我在哪里使用锂在内部折叠器，这是我的问题。 * b
$ b
-
然后我尝试应用我的单变量函数来映射。我遇到同样的问题：
fun evalXY（z :: zs）xy =
map
（foldr（fn（a，b）=> a + b * x）0）
z：zs
*通过这种尝试，我知道即时通讯获取整数列表。我把一个int列表列表中，其中内部列表被处理并作为int整数返回到外部列表。在此之后，我再次折叠以将y值应用于多项式。
这里的函数应该看起来像:: fn evalXY：（int list list）* int * int） - > ... - > int list *
我是SML的新手，所以也许我在这里错过了一些基本的东西。我知道这是一种函数式编程语言，所以我试图积累值而不是改变不同的变量， 非常接近。我们首先将问题正式化。给定系数C作为你指定的嵌套列表，你需要评估
请注意，您可以将 s从内在的和，得到
仔细观察内在的总和。这只是变量x上的一个多项式，其系数由给出。在SML中，我们可以将 horner 函数的内部金额写为
fun sumi Ci = horner Ci x
让我们更进一步并定义
在SML中， val D = map sumj C 。我们现在可以按照D来写出原始多项式：
应该清楚，这只是 horner 的另一个实例，因为我们有一个多项式，其系数。在SML中，这个多项式的值是
horner D y
...我们完成了！
这是最后的代码：
fun horner2 C xy =
let
fun sumj Ci = horner Ci x
val D =地图sumj C
in
horner D y
end
这不是很好吗？我们需要的是Horner方法的多个应用程序， map 。
Horner's rule is used to simplify the process of evaluating a polynomial at specific variable values. https://rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#Standard_ML
I've easily applied the method using SML, to a one variable polynomial, represented as an int list:
fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList
This works fine. We can then call it using:
- val test = horner [1.0, 2.0, 3.0] 2.0;
> val test = 17.0 : real
Where [1.0, 2.0, 3.0] is the list representing the polynomial coefficients, 2.0 is the value of the variable x, and 17.0 is the result of evaluating the polynomial.
My problem is as such: We have a two variable polynomial represented by an (int list list). The nth item in a high-level list will represent all the polynomial terms containing y^n, and the mth item in a low-level list will represent all the polynomial terms containing x^m.
For example: [[2],[3,0,0,3],[1,2]] is the polynomial
( 2(x^0)(y^0) ) +
( 3(x^0)(y^1) + 0(x^1)(y^1) + 0(x^2)(y^1) + 3(x^3)(y^1) ) +
( 1(x^0)(y^2) + 2(x^1)(y^2) )
The function needs to return the value of the polynomial at the specified x and y.
I've tried various methods using the mlton compiler.
First I tried a nested foldr function:
fun evalXY (z::zs) x y = foldr (fn (s, li:list) => s + ((foldr (fn(a, b) => a + b*x) 0 li)*y) ) 0 z:zs
You can see that I'm trying to use "s" as an accumulator, like "a" was used in the single variable example. Since each element being processed by foldr needs to be "foldr'ed" itself, i call foldr again in the function describing the outer foldr. I know hat this inner foldr works fine, I proved it above. *My problem seems to be that I cant access the element of the list that the outer foldr is on to pass that list into the inner foldr. >See where I use li in the inner foldr, thats my issue. *
Then i tried applying my single variable function to map. I came across the same issue:
fun evalXY (z::zs) x y = map (foldr (fn(a, b) => a + b*x) 0 ???) z:zs*With this attempt, i know that im getting back a list of ints. I put in an int list list, in which the inner lists were processed and returned to the outer list as ints by foldr. After this i would foldr again to apply the y value to the polynomial. The function here should look like :: fn evalXY : (int list list) * int * int) -> ... -> int list *
I am new to SML, so maybe i'm missing something fundamental here. I know this is a functional programming language, so I'm trying to accumulate values instead of altering different variables,
You're very close. Let's begin by formalizing the problem. Given coefficients C as a nested list like you indicated, you want to evaluate
Notice that you can pull out the s from the inner sum, to get
Look closely at the inner sum. This is just a polynomial on variable x with coefficients given by . In SML, we can write the inner sum in terms of your horner function as
fun sumj Ci = horner Ci x
Let's go a step further and define
In SML, this is val D = map sumj C. We can now write the original polynomial in terms of D:
It should be clear that this is just another instance of horner, since we have a polynomial with coefficients . In SML, the value of this polynomial is
horner D y
...and we're done!
Here's the final code:
fun horner2 C x y =
let
fun sumj Ci = horner Ci x
val D = map sumj C
in
horner D y
end
Isn't that nice? All we need is multiple applications of Horner's method, and map.
这篇关于Horner关于双变量多项式的规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
