整数可用于存储单个数字，但不能用于存储数学表达式。例如，假设我有以下表达式：
6x^2 + 5x + 3
我将如何存储多项式？我可以创建自己的对象，但我不知道如何通过成员数据来表示多项式。我不想创建一个函数来评估传入的参数，因为我不仅需要评估它，还需要操作表达式。
矢量是我唯一的选择还是有更合适的解决方案？
问问题
6632 次
8 回答
8
一种简单但低效的方法是将其存储为系数列表。例如，问题中的多项式如下所示：
[6, 5, 3]
如果缺少一个术语，请在其位置放置一个零。例如，多项式2x^3 - 4x + 7将表示如下：
[2, 0, -4, 7]
多项式的次数由列表的长度减一给出。这种表示有一个严重的缺点：对于稀疏多项式，列表将包含很多零。
稀疏多项式的项列表更合理的表示是非零项的列表，其中每个项是包含项的阶和该阶的系数的列表；多项式的次数由第一项的阶数给出。例如，多项式x^100+2x^2+1将由以下列表表示：
[[100, 1], [2, 2], [0, 1]]
于 2012-05-22T00:50:26.503 回答
2
列表不是唯一的选择。
您可以使用映射（字典）将指数映射到相应的系数。
使用地图，您的示例将是
{2: 6, 1: 5, 0: 3}
（系数，指数）对的列表是非常标准的。如果你知道你的多项式是密集的，也就是说，所有的指数位置都是 0 到某个小的最大指数范围内的小整数，你可以使用数组，正如我看到的 Óscar Lopez 刚刚发布的那样。:)
于 2012-05-22T00:50:24.243 回答
2
您可以将表达式表示为表达式树。参见例如.NET 表达式树。
这允许比简单多项式更复杂的表达式，并且这些表达式也可以使用多个变量。
在 .NET 中，您可以将表达式树作为树来操作，并且可以将其作为函数进行评估。
Expression<Func<double,double>> polynomial = x => (x * x + 2 * x - 1);
double result = polynomial.Compile()(23.0);
于 2012-05-22T00:55:43.380 回答
1
面向对象的方法会说多项式是单项式的集合，而单项式将系数和指数封装在一起。
当您有这样的多项式时，此方法有效：
y(x) = x^1000 + 1
对于这种病态情况，将数据结构与多项式阶数联系起来的方法将是非常浪费的。
于 2012-05-22T02:27:32.323 回答
0
向量/数组是显而易见的选择。根据表达式的类型，您可能会考虑某种稀疏向量类型（自定义，即基于字典甚至链表，如果您的表达式有 2-3 个非零系数 5x^100+x ）。
在任何一种情况下，通过自定义类/接口公开都是有益的，因为您可以稍后替换实现。如果您计划编写大量表达式操作代码，您可能希望提供标准操作（+、-、*、等于）。
于 2012-05-22T00:50:45.130 回答
0
您需要存储两件事：
- 多项式的次数（例如“3”）
- 包含每个系数的列表（例如“{3, 0, 2}”）
在标准 C++ 中，“std::vector<>”和“std::list<>”两者都可以。
于 2012-05-22T00:52:13.757 回答
0
只需将系数存储在数组或向量中。例如，在 C++ 中，如果您只使用整数系数，您可以使用std::vector<int>, 或对于实数，std::vector<double>. 然后你只需按顺序推动系数并通过可变指数数访问它们。
例如（再次在 C++ 中），要存储 5*x^3 + 9*x - 2 你可以这样做：
std::vector<int> poly;
poly.push_back(-2); // x^0, acceesed with poly[0]
poly.push_back(9); // x^1, accessed with poly[1]
poly.push_back(0); // x^2, etc
poly.push_back(5); // x^3, etc
如果您有大型、稀疏的多项式，那么您可能想要使用地图而不是向量。如果您有固定大小的长度，那么您可能会使用固定长度的数组而不是向量。
我以 C++ 为例，但同样的方案可以用在任何语言中。
于 2012-05-22T00:57:56.227 回答
0
您还可以将其转换为反向波兰表示法：
6x^2 + 5x + 3 -> x 2 ^ 6 * x 5 * + 3 +
wherex和 numbers 被“推送”到堆栈中，操作 (^,*,+) 从堆栈中获取两个最顶层的值并将它们替换为操作的结果。最后你得到堆栈上的结果值。
在这种形式下，很容易计算任意复杂的表达式。
这种表示也接近于表达式的树表示，其中非叶树节点表示操作和函数，叶节点用于常量和变量。
树的好处是您还可以轻松地评估表达式，还可以对它们进行符号微分之类的操作。两者都具有递归性质。
于 2012-05-22T01:06:46.107 回答