如何乘以2多项式使用链表与输出功率变量？

我的老师让我用链表做一个多项式样，因为这代码如何乘以2多项式使用链表与输出功率变量？

class Node { 
    public: 
     int data; // only data, has no power 
     Node* next; 
}; 
class PolyList { 
    private: 
     Node* pHead; 
    public: 
     PolyList(); 
     ~PolyList(); 
     ............ 
}

列表由文件input.txt中读出。例如：2 4 0 3 ---> Polynomial =（2x^3 + 4x^2 + 3）

如何实现方法在list1和list2之间乘以2多项式。 我搜索谷歌和这个网站，但只有在创建发现多项式数据包括系数变量和电源变量。我的多项式只有系数，我不能改变这个结构。我需要大家的帮助。非常感谢。

来源

2011-10-11 Cong Binh

如果要乘以M和N阶的两个多项式，则生成的多项式的阶数将为M + N。因此，您需要创建一个输出链表，其长度为两个输入列表的长度之和。然后，您只需遍历两个输入列表，然后将这些项相乘并相加到输出列表中。

提示：你可能想尝试先用手这样做，即用铅笔和纸，让你了解的过程，你尝试编写它之前。

来源

2011-10-11 21:33:40

你想要做什么系数convolution。如果你有机会到Matlab的（或八度），你可以试一下：

% Note this is Matlab, just for demonstration 
p1 = [1 1]; % x + 1 
p2 = [1 0]; % x 
p3 = conv(p1, p2) %x*(x + 1) => x^2 + x 

% gives p3 = [1 1 0], i.e., x^2 + x

编辑：我没有给有关实现此的任何细节 - 您可以通过谷歌搜索它使用链表可能发现卷积的例子。

来源

2011-10-11 21:33:45 dantswain

一种方法做它可以是以下几点：

list<int> multiply(list<int> l1, list<int> l2) { 
    int m[l1.size() + l2.size() - 1]; // Only positive powers of l1 "augments" the powers of l2! 

    for (unsigned int i = 0; i < l1.size(); i++) { 
    for (unsigned int j = 0; j < l2.size(); i++) { 
     m[i + j] += l1.get() * l2.get(); 
     l2.next(); 
    } 
    l2.reset(); 
    l1.next(); 
    } 
    list<int> to_ret; 
    for (unsigned int i = 0; i < m.length; i++) 
    to_ret.push_back(m[i]); 
    return to_ret; 
}

你把所产生的多项式的i次幂的系数m[i]。为了填补m，它足以为[0，l1.size）×[0，l2.size）的每对夫妇（I，J）迭代，并把在m[i + j]你得到乘以i次方系数系数的第一个多项式与第二个的j次幂。

来源

2011-10-11 21:40:22 akappa

可能是因为将作业的回答作为逐字回答 – sehe

并不是非常有建设性的，但是您应该认识到对这类问题的有意义的回答与伪代码包含并不遥远，就像我一样。 – akappa

@akappa似乎只用2列表具有相同的长度？ –

你可以用两个嵌套for循环的两个列表乘在一起，同时节省他们在另一个列表：（伪）

define list3 as a new PolyList of length x + y 

for each element A at index x in list1 
    for each element B at index y in list2 
     save list3 element at index x + y as (A * B + (element at index x + y))

因此，例如，以x^3 - 2 + 1 * *^2 + 4 = [1,0，-2,1] * [0,0,1,4] = [0,0,0,1,0,2,1，-8,4]。

* 注：你的结果列表可以高达两次两个阵列的原始长度的大小，因为对于实施例X^3 * X^3 = X^6，这将被记录在第六个索引，从右边开始*

另请注意：两个数组的长度必须相同才能正常工作！如果这不是你正在创建的函数所承担的，你将不得不处理这种情况。

弄清楚怎么样，这是想象正是你会做些什么来解决问题的步骤，写那些下来程序有问题，然后再翻译成您所使用的语言的好方法。

来源

2011-10-11 21:44:29 therin

谢谢但是与2列表的经理很难有不一样的长度。你能给我这个案子的小费吗？ –

如果一个多项式的阶数小于另一个多项式的阶数，则用零填充较小阶的多项式直到它们具有相同的长度。例如：x^3 + 1 * x^2 + x = [1,0,0,1] * [2,1,0] = [1,0,0,1] * [0,2,1， 0]（注意你必须填充列表的左端而不是右端）。 – therin

如何乘以2多项式使用链表与输出功率变量？

回答

相关问题