我目前正在编写一个方法，将两个多项式(由2个文本文件给出)加在一起。例如:
4.0x^5 + -2.0x^3 + 2.0x + 3.0
和
8.0x^4 + 4.0x^3 + -3.0x + 9.0
将得到:4.0x^5 + 8.0x^4 + 2.0x^3 - 1.0x + 12
目前，我的方法创建了一个新的多项式对象，但只添加了有程度匹配的项。所以我的输出看起来像这样:
2.0x^3 - 1.0x + 12
缺少前两项，因为度不匹配。下面是我的代码(重要的是:多项式最初是由Node poly = null构造的;——所以变量poly是指向多项式链表前面的节点):
public Polynomial add(Polynomial p) {
Polynomial answer = new Polynomial();
for (Node firstPoly = poly; firstPoly != null; firstPoly = firstPoly.next){
for (Node secondPoly = p.poly; secondPoly != null; secondPoly = secondPoly.next){
if (firstPoly.term.degree == secondPoly.term.degree){
answer = addToRear(answer, (firstPoly.term.coeff + secondPoly.term.coeff), firstPoly.term.degree, null);
if (answer.poly.term.coeff == 0){
answer.poly = null;
}
}
}
}
return answer;
}
我不是要求任何人为我解决这个问题，但是有人知道我下一步要做什么来确保不匹配的度被添加吗?我一直想把它写在纸上，但由于各种原因，什么都没有成功。这里是addToRear方法，以防它对你们有用。
private Polynomial addToRear(Polynomial p, float coeff, int degree, Node next){
if (p.poly == null){
p.poly = new Node(coeff, degree, null);
return p;
}
for (Node temp = p.poly; temp != null; temp = temp.next){
if (temp.next == null){
temp.next = new Node(coeff, degree, null);
return p;
}
}
return p;
}
谢谢。
可能更容易确保多项式数据结构包含所有幂，包括那些没有乘数的幂。换句话说，多项式2.0x3 - 1.0x + 12将被表示为集合:
pwr 0 1 2 3
---- ---- ---- ----
{ 12.0, 1.0, 0.0, 2.0 }
除非你讨论的是大量的多项式和大量的高端项幂，否则这个解的非稀疏性应该是无关紧要的。
正如你所看到的，我也改变了的顺序，这样x0(常数)项在列表中是第一个，因为假设你的多项式没有负幂，这也会减轻添加的工作量。这是因为匹配能力将在集合中具有匹配索引。
那么，将两个多项式相加:
4.0x5 - 2.0x3 + 2.0x + 3.0
8.0x4 + 4.0x3 - 3.0x + 9.0
类似于:
pwr 0 1 2 3 4 5
---- ---- ---- ---- ---- ----
{ 3.0, 2.0, 0.0, -2.0, 0.0, 4.0 }
+ { 9.0, -3.0, 0.0, 4.0, 8.0 }
----------------------------------------
= { 12.0, -1.0, 0.0, 2.0, 8.0, 4.0 }
根据需要给出(输出时忽略零乘法器)
4.0x5 + 8.0x4 + 2.0x3 - 1.0x + 12.0
如果，出于某种原因，必须处理稀疏链表，那么它取决于项是否基于幂进行排序。
如果它们不是，您通常必须使用这样的算法:
set poly3 to empty
# Process all in poly1, including those in poly2.
foreach term1 in poly1:
find term2 in poly2 with matching power
if none:
add (term1.coeff, term1.power) to poly3
else:
add (term1.coeff + term2.coeff, term1.power) to poly3
# Process all in poly2, but NOT in poly1.
foreach term2 in poly2:
find term1 in poly1 with matching power
if none:
add (term2.coeff, term2.power) to poly3
这将首先将第一个多项式的所有幂相加，包括那些在第二个多项式中有项的幂。
然后，它将在第二个数组中添加那些在第一个数组中没有对应项的数组。这样，所有的术语都被正确添加。
如果项是排序的，您可以通过并行处理列表(类似于合并算法)使其更高效，在每个阶段从列表中获得最高未处理能力的项，例如:
set poly3 to empty
set term1 to poly1.head
set term2 to poly2.head
# Process both until at least one runs out.
while term1 != null and term2 != null:
if term1.power == term2.power:
add (term1.coeff + term2.coeff, term1.power) to poly3
term1 = term1.next
term2 = term2.next
elif term1.power > term2.power:
add (term1.coeff, term1.power) to poly3
term1 = term1.next
else:
add (term2.coeff, term2.power) to poly3
term2 = term2.next
# Process remaining single list, if any.
while term1 != null:
add (term1.coeff, term1.power) to poly3
term1 = term1.next
while term2 != null:
add (term2.coeff, term2.power) to poly3
term2 = term2.next
作为概念证明，这里有一些Python代码执行排序变体。代码的大部分是将字符串转换为"列表"(实际上是幂稀疏数组)并打印出结果多项式。解决方案的核心在主线中，从poly3 = []:
poly1 = '4.0x^5 - 2.0x^3 + 2.0x + 3.0'
poly2 = '8.0x^4 + 4.0x^3 + -3.0x + 9.0'
# Makes component extraction from array easier.
coeff = 0
power = 1
def baseline(s):
# Remove spaces, normalise to all '+'.
check = s + ' '
result = s
while result != check:
check = result
result = result.replace(' ','');
result = result.replace('-','+-')
result = result.replace('++','+')
# Create array of terms.
result = result.split('+')
# Make each term a coefficient/power pair.
for i in range(len(result)):
result[i] = result[i].split('^')
if len(result[i]) == 1 and result[i][coeff].endswith('x'):
result[i].append('1')
if len(result[i]) == 1 and not result[i][coeff].endswith('x'):
result[i].append('0')
if result[i][coeff].endswith('x'):
result[i][coeff] = result[i][coeff][:-1]
result[i][coeff] = float(result[i][coeff])
result[i][power] = int(result[i][power])
return result
def polyprint(s,p):
print()
print(s, p, end=':n ')
if len(p) > 0:
print(p[0][coeff],end='')
if p[0][power] == 1:
print('x',end='')
elif p[0][power] > 1:
print('x^%d' % (p[0][power]),end='')
for i in range(1,len(p)):
if p[i][coeff] < 0:
print(' -',-p[i][coeff],end='')
else:
print(' +',p[i][coeff],end='')
if p[i][power] == 1:
print('x',end='')
elif p[i][power] > 1:
print('x^%d' % (p[i][power]),end='')
print()
# Turn polynomials into sparse (based on powers) array.
poly1 = baseline(poly1)
poly2 = baseline(poly2)
polyprint('poly1',poly1)
polyprint('poly2',poly2)
# Add them as per sorted algorithm.
poly3 = []
idx1 = 0
idx2 = 0
while idx1 < len(poly1) and idx2 < len(poly2):
if poly1[idx1][power] == poly2[idx2][power]:
if poly1[idx1][coeff] != poly2[idx2][coeff]:
poly3.append([poly1[idx1][coeff] + poly2[idx2][coeff], poly1[idx1][power]])
idx1 += 1
idx2 += 1
continue
if poly1[idx1][power] > poly2[idx2][power]:
poly3.append([poly1[idx1][coeff], poly1[idx1][power]])
idx1 += 1
continue
poly3.append([poly2[idx2][coeff], poly2[idx2][power]])
idx2 += 1
while idx1 < len(poly1):
poly3.append([poly1[idx1][coeff], poly1[idx1][power]])
idx1 += 1
while idx2 < len(poly2):
poly3.append([poly2[idx2][coeff], poly2[idx2][power]])
idx2 += 1
polyprint('poly3',poly3)
取任意多项式的最大次，并将所有缺失项设为零。即x^2 = 0x^3 + 1x^2 + 0x^1 + 0x^0。(作为旁注，数值计算的实际实现将以嵌套形式表示多项式，以最大限度地减少在乘法后添加的精度损失。)