L2-018 多项式A除以B (25分)

(最近重刷PTA天梯赛的题目碰到这个题,还是无从下手,所以写篇博客记录一下)

//输入是以指数递减的形式依次输入每一项
4 4 1 2 -3 1 -1 0 -1
3 2 3 1 -2 0 1

//输出和输入格式一样,依次输出商和余数
3 2 0.3 1 0.2 0 -1.0
1 1 -3.1

样例图解

多项式相除

题目代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define lowbit(x) ((x) & (-x))
const int inf = 0x3f3f3f3f;
const int N = 1010;

double c1[N], c2[N], ans[N];     //ans数组保存商,c1数组最终的值就是余数
int max1, max2;

void input(double *arr, int cnt, int &m) {
    int e;
    double val;
    while (cnt--) {
        cin >> e >> val;
        arr[e] = val;
        m = max(m, e);
    }
}

void output(double *arr, int e) {
    int cnt = 0;
    for (int i = 0; i <= e; i++) 
        if (abs(arr[i]) >= 0.05)     //四舍五入后为0.0的项不会输出
            cnt++;
    if (cnt == 0) cout << "0 0 0.0";
    else {
        cout << cnt;
        for (int i = e; i >= 0; i--) {
            if (abs(arr[i]) >= 0.05) 
                printf(" %d %.1f", i, arr[i]);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif      
    int n;
    cin >> n, input(c1, n, max1);
    cin >> n, input(c2, n, max2);
    int d = max1 - max2;            //保存商的最高项
    while (max1 >= max2) {
        double k = c1[max1] / c2[max2];    
        ans[max1 - max2] = k;
        for (int i = max1, j = max2; i >= 0 && j >= 0; i--, j--) 
            c1[i] -= c2[j] * k;
        max1--;
    }
    output(ans, d);
    cout << endl;
    output(c1, max1);
    
    return 0;
}
最后修改:2020 年 11 月 30 日 11 : 08 PM