Suma de polinomis P70952


Statement
 

pdf   zip

thehtml

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

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−15x2+4x3 es correspon al vector

||
   0   1   2   3
||
||
  12 ‍: ‍0  2 ‍: ‍1−15 ‍: ‍2  4 ‍: ‍3
||

i el polinomi 666xx79+12x191 es correspon al vector

||
   0   1   2
||
||
  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++