Suma de polinomis P70952

Statement

thehtml

En aquest exercici considerem sumes de polinomis amb coeficients enters. Per exemple, la suma de 12+2x−15x²+4x³ amb −1−3x+15x²−2x⁴ és 11−x+4x³−2x⁴.

Representem els polinomis amb vectors de parells, cadascun amb el coeficient i l’exponent d’un monomi, sempre que el coeficient no sigui zero. El vector es troba ordenat segons els exponents, de petit a gran.

Per exemple, el polinomi 12+2x−15x²+4x³ es correspon al vector

||
||

12 ‍: ‍0

2 ‍: ‍1

−15 ‍: ‍2

4 ‍: ‍3

i el polinomi 666x−x⁷⁹+12x¹⁹¹ es correspon al vector

||
||

666 ‍: ‍1

−1 ‍: ‍79

12 ‍: ‍191

Les declaracions següents permeten definir polinomis tal com s’ha descrit:

struct Parell { int coef; // coeficient int expo; // exponent }; typedef vector<Parell> Polinomi; // ordenat per exponent

Utilitzant aquestes definicions, implementeu la funció

Polinomi suma(const Polinomi& p, const Polinomi& q);

que retorna la suma de dos polinomis p i q donats.

Observació

El programa principal ja se us dóna implementat; no el canvieu. Aquest llegeix primer un natural t. Després llegeix t parelles de polinomis, les suma i n’escriu el resultat.

#include <iostream> #include <vector> using namespace std; struct Parell { int coef; int expo; }; typedef vector<Parell> Polinomi; Polinomi suma(const Polinomi& p, const Polinomi& q) { } void llegeix(Polinomi& p) { int n; cin >> n; p = Polinomi(n); char c; for (int i = 0; i < n; ++i) cin >> p[i].coef >> c >> p[i].expo; } void escriu(const Polinomi& p) { int n = p.size(); cout << n; for (int i = 0; i < n; ++i) cout << " " << p[i].coef << ":" << p[i].expo; cout << endl; } int main() { int t; cin >> t; for (int i = 0; i < t; ++i) { Polinomi p, q; llegeix(p); llegeix(q); Polinomi r = suma(p, q); escriu(r); } }

Public test cases

Input

10

4 12:0 2:1 -15:2 4:3
4 -1:0 -3:1 15:2 -2:4

4 3:1 8:4 -3:7 5:8
4 3:1 8:4 -3:7 5:8

3 4:0 8:5 6:6
2 3:0 -6:6

2 3:0 -6:6
3 4:0 8:5 6:6

3 2:3 3:18 5:21
3 2:3 -3:18 -5:21

1 1:1000000000
1 1000000000:1

0
0

1 999:666
0

0
1 999:666

1 -999:666
1 999:666

Output

4 11:0 -1:1 4:3 -2:4
4 6:1 16:4 -6:7 10:8
2 7:0 8:5
2 7:0 8:5
1 4:3
2 1000000000:1 1:1000000000
0
1 999:666
1 999:666
0

Information

Author: Professors de P1
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++