多项式的欧几里得除法
1.00/5 (1投票)
本文介绍了如何对两个多项式进行除法运算，并展示了计算该除法的源代码。此外，还提供了加法、减法和乘法运算两个多项式的代码。
引言
欢迎来到使用Python的Polynomial库进行多项式除法。在本教程中，我们将讨论多项式除法的数学概念以及如何使用Polynomial库来实现它。我们还将提供一个分步指南，介绍如何对两个多项式进行除法以及如何在您自己的项目中使用这些代码。
在我们开始之前，了解什么是多项式以及它在Python中如何表示很重要。多项式是包含变量（也称为系数）和指数的数学表达式。在Python中，使用Polynomial库，多项式表示为系数列表，例如[1, 2, 3, ...]。
多项式的欧几里得除法并不是一个简单的算法，尽管它完全受到整数除法的启发。相比之下，对两个多项式求和或相乘是更直观、更容易理解的算法。在本文中，我将提供一段代码，用于创建由数值系数列表表示的多项式，获取列表的大小，计算多项式中最大的非零次数，以及进行加法和乘法运算。
背景
为了编写这段代码，我受到了Python中声明多项式方式的启发，并且我在网上查找了许多关于如何对两个多项式进行除法的解释，包括一个解释计算过程的YouTube视频。
尽管解释得很清楚，但这仍然是一个难以实现的练习，因为在纸上进行多项式除法的方式与要执行的算法之间存在差异。
Using the Code
要测试此代码，您可以访问talenha.boribar.com。那里有一个输入窗口，允许您输入代码并进行测试。即使在测试此代码时可能会遇到困难，您也可以轻松地将其转译成您喜欢的语言。
引言
这使我们可以更轻松地对多项式进行运算，尤其是在计算多项式的导数和积分时。
在本文中，我们将学习如何使用欧几里得除法来实现一个多项式除法算法。该方法包括找到多项式除法的商和余数。它是整数除法算法的推广，可用于求解多项式方程。
我们将首先介绍理解该算法所需的数学概念，然后使用Polynomial库在Python中实现它。最后，我们将把结果与使用Python内置多项式除法函数获得的结果进行比较，并讨论我们实现的优点和局限性。
数学概念
两个多项式的除法是一种将一个多项式除以另一个多项式的结果表示为“商”多项式和“余数”多项式的方法。它基于我们在小学学到的长除法算法，但将其扩展到多项式。
多项式f(x)除以多项式g(x)可以写成如下形式：
f(x) = g(x) * q(x) + r(x)
其中q(x)是商多项式，r(x)是余数多项式。
如果您想得到除法公式，只需将等式两边同时除以g(x)即可。
f(x) / g(x) = q(x) + r(x) / g(x)
为了执行除法，我们首先将f(x)的首项系数除以g(x)的首项系数。这将得到商多项式q(x)的第一个系数。然后，我们将g(x)乘以这个系数，并将其从f(x)中减去，得到一个新的多项式，我们称之为“简化”多项式。我们重复这个过程，直到简化多项式的次数小于g(x)的次数。最终的简化多项式就是余数多项式r(x)。
例如，让我们考虑将多项式f(x) = x^3 + 2x^2 + 3x + 4除以多项式g(x) = x^2 + x + 1。我们首先将f(x)的首项系数（为1）除以g(x)的首项系数（也为1）。这将得到商多项式q(x)的第一个系数，即1。然后，我们将g(x)乘以这个系数，并将其从f(x)中减去，得到简化多项式。需要注意的是，下一次迭代是从新的函数f(x) - C * g(x)开始，而不是从f(x)开始。
除两个多项式的迭代算法
| f(x) | g(x) | C | f(x) - C * g(x) |
| x^3 | x^2 | x | x^2 + 2x + 4 |
| x^2+2x+4 | x^2 | 1 | x + 3 |
最终结果是x + 1 - (x+3) / (x^2+x+1)。
当我们展开这个等式时，我们会得到一个与f(x)完全相等的等式。
Python程序
在Python中，使用Polynomial库，多项式表示为系数列表，例如[1, 2, 3, ...]。系数的排列顺序很重要，因为它们从左到右排列，从次数n开始到次数0，相对于polynomial对象。如果您定义了一个系数列表，其中
np.poly1d([1, 2, 3])
它们从左到右排列，从次数0开始到次数n。
现在我们对多项式及其在Python中的表示有了基本的了解，让我们深入探讨多项式除法的概念以及如何在Python中实现它。
Python测试
为了在Python中进行测试，我们将使用Web应用程序replit.com。
from polynomial import poly
import numpy as np
# Print a polynomial object with the coefficients [1, 2, 3, 4]
print(poly([1, 2, 3, 4]))
# Print a polynomial object with the coefficients [1, 1, 1]
print(poly([1,1,1]))
# Divide the polynomial [ 1, 2, 3, 4 ] by the polynomial [ 1, 1, 1 ]
print(np.polydiv(poly([1,2,3,4]), poly([ 1, 1, 1 ])))
输出与之前的结果完全相同。
[1, 2, 3, 4]
[1, 1, 1]
(array([1., 1.]), array([1., 3.]))
用简单的编程语言实现的函数
在这个多项式版本中，需要注意的是，系数从左到右排列，从次数n开始到次数0。
例如，[ 1, 2, 3, 4 ]会被打印为以下表达式：
x^3 + 2x^2 + 3x + 4
可以使用以下函数
poly@create(n): 创建一个次数为n的新多项式poly@copy(p): 克隆一个已有多项式poly@size(p): 计算多项式系数列表的大小poly@degree(p): 返回最高非零系数的次数poly@trim(p): 从列表中删除所有前导0poly@isNull(p): 判断是否为null多项式poly@nth(p, i): 返回多项式第i次的系数poly@add(p1, p2): 返回一个多项式，它是p1和p2的和poly@sub(p1, p2): 返回一个多项式，它是p1减去p2的结果poly@mul(p1,p2): 返回一个多项式，它是p1和p2的乘积poly@monome(i, c): 构建一个次数为i、系数为c的单项式poly@div(p1, p2): 将多项式p1除以p2，并返回除法的商和余数poly@print(p): 以代数形式打印多项式表达式
[<<[
fun poly@create(n) {
p = [0],
while(n > 0) {
p = p 0,
n = n - 1
},
output(p)
},
fun poly@copy(p) {
copy = [],
count = 0,
while(count < p.length) {
copy = copy p(count),
count = count + 1
},
output(copy)
},
fun poly@size(p) {
output(p.length - 1)
},
fun poly@degree(p) {
select {
default {
foreach(i from p) {
if (p(i) == 0) {} else jump "break"
},
output(-1)
},
break { output(p.length - 1 - i) }
}
},
fun poly@nth(p, i) {
output(p(poly@size(p) - i))
},
fun poly@isNull(p) {
output(poly@degree(p) == -1)
},
fun poly@add(p1, p2) {
count1 = poly@size(p1),
count2 = poly@size(p2),
// init result
result = poly@create(number@max(count1, count2)),
while(count1 >= 0 && count2 >= 0) {
count = number@max(count1,count2),
result(count) = p1(count1) + p2(count2),
count1 = count1 - 1,
count2 = count2 - 1
},
while(count1 >= 0) {
result(count1) = p1(count1),
count1 = count1 - 1
},
while(count2 >= 0) {
result(count2) = p2(count2),
count2 = count2 - 1
},
output(result)
},
fun poly@sub(p1, p2) {
count1 = poly@size(p1),
count2 = poly@size(p2),
// init result
result = poly@create(number@max(count1, count2)),
while(count1 >= 0 && count2 >= 0) {
count = number@max(count1,count2),
result(count) = p1(count1) - p2(count2),
count1 = count1 - 1,
count2 = count2 - 1
},
while(count1 >= 0) {
result(count1) = p1(count1),
count1 = count1 - 1
},
while(count2 >= 0) {
result(count2) = -p2(count2),
count2 = count2 - 1
},
output(result)
},
fun poly@mul(p1, p2) {
result = poly@create(poly@size(p1) + poly@size(p2)),
count2 = poly@size(p2),
while(count2 >= 0) {
count1 = poly@size(p1),
while(count1 >= 0) {
pos = poly@size(result) - (poly@size(p1) - count1 +
poly@size(p2) - count2),
result(pos) = result(pos) + p1(count1) * p2(count2),
count1 = count1 - 1
},
count2 = count2 - 1
},
output(result)
},
fun poly@monome(degree, coefficient) {
count = degree,
o = [0],
while(count > 0) {
o = o 0,
count = count - 1
},
o(0) = coefficient,
output(o)
},
fun poly@div(p1, p2) {
if (poly@degree(p1) < poly@degree(p2)) {
output({ quotient : [0], remainder : p1})
} else {
quotient = [0],
remainder = poly@copy(p1),
select {
default {
pos = poly@size(p2),
loop = 0,
while(poly@degree(remainder) >= poly@degree(p2)) {
q = poly@monome(poly@degree(remainder) - poly@degree(p2),
remainder(poly@size(remainder) -
poly@degree(remainder)) / p2(0)),
print("polynome quotient " poly@print(q)),
quotient = poly@add(quotient, q),
remainder = poly@sub(remainder, poly@mul(p2, q)),
print("polynome reste = " poly@print(remainder)),
if (poly@degree(remainder) == -1)
jump "break",
pos = pos - 1,
if (loop > 5) jump "break",
loop = loop + 1
}
},
break {}
},
output({ quotient : quotient, remainder : remainder })
}
},
fun poly@print(p) {
if (p.length > 0) {
count = poly@size(p),
if (p(count) == 0) { o = "" } else o = p(count),
count = count - 1,
while(count >= 0) {
if (poly@size(p) - count == 1) {
degree = "x"
} else degree = "x^" (poly@size(p) - count),
if (o) { plus = " + " } else plus = "",
if (p(count) == 1)
{ o = degree plus o }
else if (p(count) == 0) {}
else
o = p(count) degree plus o,
count = count - 1
},
if (o) {} else o = 0,
output(o)
}
}
]>>]
函数poly@div(p1, p2)的说明
起始条件
首先，p1的次数必须大于p2的次数。如果p1的次数小于p2的次数，则商为0，余数为p1，函数结束。
循环条件
当余数的次数小于p2的次数时，while循环条件poly@degree(remainder) >= poly@degree(p2)为false。例如：
remainder = 2x + 1 // <-- degree 1
p2 = x^2 + 2x + 1 // <-- degree 2
poly@degree(remainder) >= poly@degree(p2) // <-- false, the while loop ends
商的计算
q = poly@monome(poly@degree(remainder) - poly@degree(p2),
remainder(poly@size(remainder) - poly@degree(remainder)) / p2(0))
函数poly@monome(n, c)接受一个数字n和一个系数c，然后创建一个次数为n、系数为c的新多项式。次数是通过当前余数的次数减去多项式p2的次数来计算的。这意味着您计算多项式商的次数，就像您在除以x时除以x^3一样。
然后，您通过将第n个余数系数除以p2的第一个系数来计算系数。系数位于列表中第一个非零系数的位置（从左到右）。请记住，p2必须在左侧进行修剪：第一个系数必须位于列表的索引0处。
加到最终商中
计算出的商是一个单项式。通过此操作将其添加到最终商中：
quotient = poly@add(quotient, q)
余数的计算
remainder = poly@sub(remainder, poly@mul(p2, q))
这正是计算新余数f(x) - C * g(x)的等式。
请注意，为了计算欧几里得除法，您必须实现两个多项式的减法和乘法。
关注点
我使用了ChatGPT来帮助我调试这里展示的源代码。尽管他多次向我解释欧几里得除法，但这仍然是一个不容易理解的算法。但是，它是完成多项式函数的一个重要算法。
历史
- 2023年4月18日：初版