根据符号和指数对多项式排序

Question

我正在用 lisp 编写多项式算术，目前正在研究加法。我需要帮助按指数和符号对多项式进行排序。我的多项式表示如下：

((3 ((1 x)(1 y))) (1 ((3 y)))) ; == 3xy + 1y^3

我需要指导的功能被赋予了一个术语

((5 ((3 x))) (3 ((3 y))) (4 ((2 z)))) ((6 ((3 x))) (1 ((3 y))) (9 ((2 z)))))

我想要：

((4 ((2 Z))) (9 ((2 Z))) (5 ((3 X))) (6 ((3 X))) (3 ((3 Y))) (1 ((3 Y))))

返回，所以所有的z^2和z^2都在一起[=13=]

Answer 1

您的初始示例显示了具有两个变量的项（例如 3xy），但您稍后的示例没有。该解决方案不会处理多变量项的情况（而且您还没有说在这种情况下您希望如何分组），但它会处理您的示例。

首先，为使用多项式项定义一些抽象概念，因为目前它们相当不方便。这里有三个函数可以更容易地从每个项中提取系数、次数和变量：

(defun polynomial-term-coefficient (term)
  (destructuring-bind (coefficient ((degree variable))) term
    (declare (ignore degree variable))
    coefficient))

(defun polynomial-term-degree (term)
  (destructuring-bind (coefficient ((degree variable))) term
    (declare (ignore coefficient variable))
    degree))

(defun polynomial-term-variable (term)
  (destructuring-bind (coefficient ((degree variable))) term
    (declare (ignore coefficient degree))
    variable))

那么，据我了解你的问题，你实际上是从两个多项式 5x³ + 3y³ + 4z² 和 6x³ + y³ + 9z²。您可以先 将它们添加 在一起，只需附加它们的术语列表即可。然后你可以 sort 谓词 string> （需要 string designators，所以符号是可以的), 关键函数为多项式项变量。也就是说，您使用 key 函数来提取您实际想要排序的值。

(let ((p1 '((5 ((3 x))) (3 ((3 y))) (4 ((2 z)))))
      (p2 '((6 ((3 x))) (1 ((3 y))) (9 ((2 z))))))
  (let ((unsimplified-sum (append p1 p2)))
    (sort (copy-list unsimplified-sum) 'string> :key 'polynomial-term-variable)))
;=> ((4 ((2 Z))) (9 ((2 Z))) (3 ((3 Y))) (1 ((3 Y))) (5 ((3 X))) (6 ((3 X))))

Answer 2

您可能想要搜索 "Horner's method"，这是一种在 O(n) 时间内计算多项式值的旧数值方法，n 是项数。它从一开始看起来就接近你想要做的事情，或者至少在表现上相似。

根据符号和指数对多项式排序

Sort Polynomial based on Symbol and Exponent

lisp

clisp

common-lisp

polynomial-math