F#递归添加多项式 [英] F# adding polynomials recursively

问题描述

我正在尝试用F#编写一个函数，该函数以递归方式添加多项式.我的多项式可以表示为元组列表.

I'm trying to write a function in F# that adds polynomials recursively. My polynomials can be represented as a list of tuples.

例如2x ^ 4 + 3x ^ 2 + x + 5等于[(2.0,4);(3.0,2);(1.0,1);(5.0,0)]

For example, 2x^4 + 3x^2 + x + 5 is equal to [(2.0,4);(3.0,2);(1.0,1);(5.0,0)]

所有多项式的结构都正确(没有重复项具有相同的度数，没有具有零系数的项，除非它是零多项式，这些项通过递减指数排序，没有空的输入列表).

All polynomials are properly structured (no repeated terms with the same degree, no terms with zero coefficients unless it is the zero polynomial, terms sorted by decreasing exponent no empty input list).

我在执行此操作时遇到了麻烦.这是我的代码

I'm having trouble doing this. Here is my code

type term = float * int
type poly = term list

let rec atp(t:term,p:poly):poly =
  match p with
  | [] -> []
  | (a, b) :: tail -> if snd t = b then (fst t + a, b) :: [] elif snd t > b then t :: [] else ([]) :: atp(t, tail)
(* val atp : t:term * p:poly -> poly *)

let rec addpolys(p1:poly,p2:poly):poly =
  match p1 with
  | [] -> []
  | (a,b) :: tail -> atp((a,b), p2) @ addpolys(tail, p2)

我有两个多项式

val p2 : poly = [(4.5, 7); (3.0, 4); (10.5, 3); (2.25, 2)]
val p1 : poly = [(3.0, 5); (2.0, 2); (7.0, 1); (1.5, 0)]

当我调用该函数时，我的结果是

and when I call the function, my result is

val p4 : poly =
  [(4.5, 7); (3.0, 5); (3.0, 4); (3.0, 5); (10.5, 3); (3.0, 5); (4.25, 2)]

正确答案是

  [(4.5, 7); (3.0, 5); (3.0, 4); (10.5, 3); (4.25, 2); (7.0, 1); (1.5, 0)]

推荐答案

很遗憾，您的代码无法编译，因此我很难理解您的意图.但是对于您的问题，我有自己的实现.也许会对您有帮助:

Unfortunately your code does not compile therefore it is difficult for me to understand your intentions. But I've got an own implementation for your problem. Maybe it will help you:

// addpoly:  (float * 'a) list -> (float * 'a) list -> (float * 'a) list
let rec addpoly p1 p2 =
    match (p1, p2) with
    | [], p2 -> p2
    | p1, [] -> p1
    | (a1, n1)::p1s, (a2, n2)::p2s -> 
        if   n1 < n2 then (a2,    n2) :: addpoly p1  p2s
        elif n1 > n2 then (a1,    n1) :: addpoly p1s p2
        else              (a1+a2, n1) :: addpoly p1s p2s

let p1 = [(3.0, 5); (2.0, 2); ( 7.0, 1);  (1.5, 0)]
let p2 = [(4.5, 7); (3.0, 4); (10.5, 3); (2.25, 2)]

let q = addpoly p1 p2
// val q : (float * int) list =
//   [(4.5, 7); (3.0, 5); (3.0, 4); (10.5, 3); (4.25, 2); (7.0, 1); (1.5, 0)]

我想做一点说明.当您更改 多项式，则可以简化函数的实现.您可以将多项式表示为其系数列表.

I would like to make a little note. When you change the representation of the polynomials a little bit then you can simplify the implementation of your function. You can express a polynomial as a list of its coefficients.

例如，当您拥有该多项式时

For example when you have this polynomial

p1 = 5.0x^5 + 2.0x^2 + 7.0x

您也可以这样写

p1 = 1.5x^0 + 7.0x^1 + 2.0x^2 + 0.0x^3 + 0.0x^4 + 5.0x^5     

因此，您可以使用以下列表定义多项式:

Therefore you are able to define the polynomial with this list:

let p1 = [1.5; 7.0; 2.0; 0.0; 0.0; 5.0]

这里有两个对表示起作用的功能. polyval计算给定值的结果，polyadd将两个多项式相加.实现很简单:

Here are two functions which operates on the representation. polyval calculates the result for a given value and polyadd adds two polynomials. There implementation are rather simple:

// p1 = 1.5x^0 + 7.0x^1 + 2.0x^2 + 0.0x^3 + 0.0x^4 + 5.0x^5
let p1 = [1.5; 7.0; 2.0; 0.0; 0.0; 5.0]

// p2 = 0.0x^0 + 0.0x^1 + 2.25x^2 + 10.5x^3 + 3.0x^4 + 0.0x^5 + 0.0x^6 + 4.5x^7
let p2 = [0.0; 0.0; 2.25; 10.5; 3.0; 0.0; 0.0; 4.5]

// polyval: float list -> float -> float
let rec polyval ps x =
    match ps with
    | []    -> 0.0
    | p::ps -> p + x * (polyval ps x)

// polyadd: float int -> float int -> float int
let rec polyadd ps qs =
    match (ps, qs) with
    | [], ys       -> ys
    | xs, []       -> xs
    | x::xs, y::ys -> (x+y)::polyadd xs ys

let v = polyval p1 2.3
// val v : float = 349.99715

let p = polyadd p1 p2
// val p : float list = [1.5; 7.0; 4.25; 10.5; 3.0; 5.0; 0.0; 4.5]

这篇关于F#递归添加多项式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！