3. Polynomial

点击查看考点

类的基础语法, C 风格数组或 std::map

Implement a class called Polynomial, which holds a polynomial (eg. \(ax^2 + bx^1\)), and satisfies the following invariants,

• No similar term.

  • Users shouldn't observe similar terms in the polynomial. That is, \(3 + 3x^2 + 5 + 2x^2\) should be observed as \(8 + 5x^2\).

• Sorted by ascending power order.

  • Users should observe an ascendingly sorted polynomial. That is, \(2x^2 + 3 + x\) should be observed as \(3 + x + 2x^2\).

• For terms with 0 as coefficient, the observable state shows as if the term dosen't exsit. That is, \(0x^2 + x^3\) should be observed as \(x^3\).

You should implement the following functions for it,

• auto operator+=(Polynomial const& other) -> Polynomial&

  • Add *this and other, store the result in *this.

• friend auto operator+(Polynomial const& lhs, Polynomial const& rhs) -> Polynomial

  • Add lhs and rhs, store the result in a new Polynomial.

• friend auto operator<<(std::ostream& ostream, Polynomial const& polynomial) -> std::ostream&

  • Output the polynomial with the format 3 + 5x^2 + 1x^3 + 1x^5.

After that, write a main function to test all your public functions.

翻译

实现一个类 Polynomial, 它包含一个多项式 (如 \(ax^2 + bx^1\)), 并且满足一下不变式.

• 无同类项.

  • 用户不应该在该多项式中观察到同类项. 即, \(3 + 3x^2 + 5 + 2x^2\) 应该被观察为 \(8 + 5x^2\).

• 按次幂升序排序.

  • 用户应该观察到一个升序的有序多项式. 即, \(2x^2 + 3 + x\) 应该被观察为 \(3 + x + 2x^2\).

• 对于系数是 0 的项, 观察结果就好像该项不存在一样. 即, \(0x^2 + x^3\) 应该被观察为 \(x^3\).

你应该为它实现以下函数.

• auto operator+=(Polynomial const& other) -> Polynomial&

  • *this 和 other 求和, 结果存储在 *this 中.

• friend auto operator+(Polynomial const& lhs, Polynomial const& rhs) -> Polynomial

  • lhs 和 rhs 求和, 结果存储在新的 Polynomial 中.

• friend auto operator<<(std::ostream& ostream, Polynomial const& polynomial) -> std::ostream&

  • 按 3 + 5x^2 + 1x^3 + 1x^5 的格式输出多项式.

在那之后, 编写一个 main 函数来测试你所有的公用函数.

点击查看解答参考

警告

此卷的所有解答参考都是笔者考试时实际写的代码的回忆版, 所以 相比于其他卷的解答参考可能更为超纲难懂.

主要是在展示以 "C++98 + Lambdas + range-based for + auto + STL" 为学习内容能如何秒杀转专业题目.

[在线代码 q1Pvcf4eo]

使用 std::map<Key, Value> 作为关联数组很简单即可完成, 其中 Key 作为次幂, Value 作为次幂对应的系数.

则类型为 std::map<int, int>, 其内元素为 std::pair<int const, int>, 这相当于:

struct Pair {
 public:
  int const first;
  int second;
};