如何存储多项式？

Question

整数可用于存储单个数字,但不能用于存储数学表达式.例如,假设我有以下表达式:

6x ^ 2 + 5x + 3

我如何存储多项式？我可以创建自己的对象,但我不知道如何通过成员数据表示多项式.我不想创建一个函数来评估传入的参数,因为我不仅需要对它进行求值,还需要操作表达式.

矢量是我唯一的选择还是有更合适的解决方案？

Answer 1

一种简单而低效的方法是将其存储为系数列表.例如,问题中的多项式将如下所示:

[6, 5, 3]

如果缺少某个术语,请将其置于原位.例如,多项式2x^3 - 4x + 7将表示如下:

[2, 0, -4, 7]

多项式的次数由列表的长度减去1给出.这种表示有一个严重的缺点:对于稀疏多项式,列表将包含许多零.

稀疏多项式的术语列表的更合理表示是非零项的列表,其中每个项是包含该项的顺序和该顺序的系数的列表; 多项式的次数由第一项的顺序给出.例如,多项式x^100+2x^2+1将由此列表表示:

[[100, 1], [2, 2], [0, 1]]

作为该表示有用的示例,本书SICP使用上述多项式的第二表示来构建简单但非常有效的符号代数系统.