F＃遞歸添加多項式

Question

我想在F＃中編寫一個遞歸添加多項式的函數。我的多項式可以表示爲元組列表。

例如，2×^ 4 + 3×^ 2 + X + 5等於[（2.0,4）;（3.0,2）;（1.0,1）;（5.0,0）]

所有多項式的結構都是合理的（沒有相同度的重複項，沒有零係數的項，除非它是零多項式，按降序指數排序的項沒有空輸入表）。

我在做這件事時遇到了麻煩。這裏是我的代碼

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)] 

，當我打電話的功能，我的結果是

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)] 

Answer 1

不幸的是，你的代碼並沒有com因此，我很難理解你的意圖。但是我已經爲您的問題自行實施。也許它會幫助你：

// 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)] 

我想做一個小記錄。如果稍微改變 多項式的表示形式，則可以簡化函數的實現。您可以將多項式表示爲其係數列表。

例如，當你有這樣的多項式

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  

因此，你能與此列表定義多項式：

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

這裏有兩個功能在表示上進行操作。 polyval計算給定值的結果，polyadd添加兩個多項式。有執行相當簡單：

// 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] 

Answer 2

這是完全通用，尾遞歸實現：

let inline addPolys xs ys = 
    let rec imp acc = function 
     | (coeffx, degx)::xt, (coeffy, degy)::yt when degx = degy -> 
      imp ((coeffx + coeffy, degx)::acc) (xt, yt) 
     | (coeffx, degx)::xt, (coeffy, degy)::yt when degx > degy -> 
      imp ((coeffx, degx)::acc) (xt, (coeffy, degy)::yt) 
     | xs, yh::yt -> imp (yh::acc) (xs, yt) 
     | xh::xt, [] -> imp (xh::acc) (xt, []) 
     | [], yh::yt -> imp (yh::acc) ([], yt) 
     | [], [] -> acc 
    imp [] (xs, ys) |> List.rev 

它具有類型：

xs:(^a * 'b) list -> ys:(^a * 'b) list -> (^a * 'b) list 
    when ^a : (static member (+) : ^a * ^a -> ^a) and 'b : comparison 

由於float具有構件+，和int支持比較，類型float * int匹配這些通用約束：

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