Решение задачи "Умножение многочленов" с Меньшиков

Без пояснения   Просмотров: 9


Ввести в символьной форме два многочлена от x с целыми коэффициентами и вывести их произведение в порядке убывания степеней - также в символьной форме. Степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 104.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
 
using namespace std;
const int MAX_POW = 10 * 2 + 5;
 
typedef long long i64;
typedef vector<i64> polynom;
 
void SkipSeps(char* &pos) {
    while (*pos == ' ')
        pos++;
}
bool isEnd(char* &pos) {
    SkipSeps(pos);
    return pos == 0;
}
bool isPlusOrMinus(const char* pos) {
    return *pos == '+' || *pos =='-';
}
bool isDigit(char p) {
    return '0' <= p && p <='9';
}
void ReadNumber(char * &pos, int &num) {
    if (isEnd(pos)) return;
    while (!isEnd(pos) && isDigit(*pos)) {
        num = num*10 + *pos - '0';
        pos++;
    }
}
void ReadPower(char* &pos, int &pow) {
    // <Степень> ::= "^"<Число>
    if (isEnd(pos)) return;
    if (*pos!='^') {
        pow = 1;
        return;
    }else {
        pos++;
        pow = 0;
        ReadNumber(pos, pow);
    }
}
void ReadKoef(char* &pos, int &k) {
    // <Коэффициент> ::= ("+" | "-")<Число>
    if (isEnd(pos)) return;
 
    bool isNeg = false;
    if (isPlusOrMinus(pos)){
        isNeg = *pos == '-';
        pos++;
    }
    if (isDigit(*pos)) {
        k = 0;
        ReadNumber(pos, k);
    }
    else
        k = 1;
    k *= isNeg ? -1 : 1;
}
void ReadMonomial(char* &pos, int &k, int &pow) {
    if (isEnd(pos)) return;
    // <Одночлен> ::= {<Коэффициент>}x{<Степень>}
    ReadKoef(pos,k);
    if (*pos == 'x') {
        pos++; // x;
        ReadPower(pos,pow);
    }
    else
        pow = 0;
}
void ReadPolynom(char* &pos, polynom &p) {
 // <Многочлен> ::= <Одночлен> {("+"|"-") <Одночлен>}
    do
    {
        int k, pow;
        ReadMonomial(pos, k, pow);
        p[pow] += k;
 
    } while (!isEnd(pos) && isPlusOrMinus(pos));
 
}
void input(polynom &a, polynom &b) {
    string str;
    cin>>str;
    char *buf = (char*)str.c_str();
    ReadPolynom(buf,a);
   
    cin>>str;
    buf = (char*)str.c_str();
    ReadPolynom(buf,b);
 
}
void mul(const polynom &a, const polynom &b, polynom &res) {
    for (int i=0; i < MAX_POW; i++) {
        for (int j=0; j<MAX_POW; j++) {
            if (i+j < MAX_POW)
                res[i+j] += a[i] * b[j];
        }
    }
}
void output (const polynom &p) {
    bool isEmpty = true;
    for (int i=0;i<p.size();i++) isEmpty &= !p[i];
    if (isEmpty) {
        cout<<0;
        return;
    }
    bool isFirst = true;
    for (int i=MAX_POW-1;i>=0;i--) {
        if (p[i]) {
            if (!isFirst && p[i] > 0) cout<<"+";
 
            if (i == 0) {
                cout<<p[i];
            }else {
                if (p[i] == -1)
                    cout<<"-";
                else if (p[i] != 1)
                    cout<<p[i];
            }
 
            if (i != 0)
                cout<<"x";
            if (i > 1)
                cout<<"^"<<i;
 
            if (isFirst) isFirst = !isFirst;
        }
    }
}
int main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    polynom a(MAX_POW), b(MAX_POW), res(MAX_POW);
    input(a,b);
    mul(a,b,res);
    output(res);
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться