C/C++语言 多项式加法和乘法

多项式的加法

题目描述

输入输出

样例

步骤

总体思想是用链表来做
① 我们发现输入样例中，系数和指数是分开输入的。也就是说，输入系数的时候，我们并不知道他对应的指数是多少。因此，我们先定义一个两个数组，一个放系数，一个放指数，然后转换为结点（用结构体，存放每一项的系数和指数），放进链表。

②输入第二个多项式的时候，要在合适的地方插入链表

• 如果遍历到指数相同的节点，则指数相加，不建立新的节点
• 如果遍历到第一个指数比自己大的节点，则插入到这个节点之前
• 如果直接遍历到链表尾端了，那就插在最后

代码段

全局变量设定

typedef struct node{//存放系数和指数
    ll ind;
    ll exp;
    struct node* next;
}NODE;
NODE* head;//合并之后链表的头结点
int n,m;//多项式1和2的长度
ll ret;//记录系数非零的节点数目

注意一点，因为是多组数据输入，因此每一次都要确保全局变量ret清零

新建结点

NODE* createNode(ll i,ll e){
    NODE* newnode = (NODE*)malloc(sizeof(NODE));
    newnode->ind=i;
    newnode->exp=e;
    newnode->next=NULL;
    return newnode;
}

用于合并两个链表时使用

合并链表

合并两个有序链表是非常经典的链表算法，这里我传的参数并不是链表，但是也是用到了合并链表的思想

void merge(ll* ind1,ll*exp1,ll*ind2,ll*exp2){
    NODE* tail = head;
    int i1 =0;
    int i2=0;//i1和i2分别记录两个多项式的当前最后一位
    while(i1!=n&&i2!=m){
        if(exp1[i1]>exp2[i2]){
            NODE* new = createNode(ind2[i2],exp2[i2]);
            tail->next = new;
            i2++;
        }else if(exp1[i1]<exp2[i2]){
            NODE* new = createNode(ind1[i1],exp1[i1]);
            tail->next = new;
            i1++;
        }else{
            NODE* new = createNode(ind1[i1]+ind2[i2],exp1[i1]);
            tail->next = new;
            i1++;
            i2++;
        }
        tail=tail->next;
        ret++;
    }
    while(i1!=n){
        NODE* new = createNode(ind1[i1],exp1[i1]);
        tail->next = new;
        i1++;ret++;
        tail=tail->next;
    }
    while(i2!=m){
        NODE* new = createNode(ind2[i2],exp2[i2]);
        tail->next = new;
        i2++;ret++;
        tail=tail->next;
    }
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
#include<limits.h>
typedef long long ll;
#define MAX_N 100005
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
typedef struct node{//存放系数和指数
    ll ind;
    ll exp;
    struct node* next;
}NODE;
NODE* head;
int n,m;
ll ret;//记录系数非零的节点数目
NODE* createNode(ll i,ll e){
    NODE* newnode = (NODE*)malloc(sizeof(NODE));
    newnode->ind=i;
    newnode->exp=e;
    newnode->next=NULL;
    return newnode;
}
void merge(ll* ind1,ll*exp1,ll*ind2,ll*exp2){
    NODE* tail = head;
    int i1 =0;
    int i2=0;//i1和i2分别记录两个多项式的当前最后一位
    while(i1!=n&&i2!=m){
        if(exp1[i1]>exp2[i2]){
            NODE* new = createNode(ind2[i2],exp2[i2]);
            tail->next = new;
            i2++;
        }else if(exp1[i1]<exp2[i2]){
            NODE* new = createNode(ind1[i1],exp1[i1]);
            tail->next = new;
            i1++;
        }else{
            NODE* new = createNode(ind1[i1]+ind2[i2],exp1[i1]);
            tail->next = new;
            i1++;
            i2++;
        }
        tail=tail->next;
        ret++;
    }
    while(i1!=n){
        NODE* new = createNode(ind1[i1],exp1[i1]);
        tail->next = new;
        i1++;ret++;
        tail=tail->next;
    }
    while(i2!=m){
        NODE* new = createNode(ind2[i2],exp2[i2]);
        tail->next = new;
        i2++;ret++;
        tail=tail->next;
    }
}
int main(){
    //初始化链表头结点,作为哑结点
    head  =(NODE*)malloc(sizeof(NODE));
    head->ind=head->exp=-1;
    head->next=NULL;
    
    int t;
    scanf("%d",&t);
    while(t--){
        ret=0;
        scanf("%d",&n);
        ll arr1_ind[n];//存放第一个多项式的系数
        for(int i=0;i<n;i++){
            scanf("%lld",&arr1_ind[i]);
        }

        ll arr1_exp[n];//存放第一个多项式的指数
        for(int i=0;i<n;i++){
            scanf("%lld",&arr1_exp[i]);
        }

    
        scanf("%d",&m);
        ll arr2_ind[m];//存放第二个多项式的系数
        for(int i=0;i<m;i++){
            scanf("%lld",&arr2_ind[i]);
        }

        ll arr2_exp[m];//存放第二个多项式的指数
        for(int i=0;i<m;i++){
            scanf("%lld",&arr2_exp[i]);
        }
        
        //合并两个多项式
        merge(arr1_ind,arr1_exp,arr2_ind,arr2_exp);

        
        //输出最后合并的结果
        printf("%lld\n",ret);

        NODE* cur = head->next;
        while(cur!=NULL){
            printf("%lld ",cur->ind);
            cur = cur->next;
        }
        printf("\n");
        cur = head->next;
        while(cur!=NULL){
            printf("%lld ",cur->exp);
            cur = cur->next;
        }
        printf("\n");
    }
    return 0;
}

多项式乘法

题目描述

输入输出

样例

代码段

计算两多项式结果

ll cal(ll base1,ll base2,ll* a,ll* b){
    ll ret1 = 0;
    ll x=1;
    for(int i=0;i<=n;i++){
        ret1=(ret1%MOD+x*a[i]%MOD)%MOD;
        x=(x*base1)%MOD;
    }

    ll ret2 = 0;
    x=1;
    for(int i=0;i<=m;i++){
        ret2=(ret2%MOD+x*b[i]%MOD)%MOD;
        x=(x*base2)%MOD;
    }
    return (ret1*ret2)%MOD;
}

注意取模的规则

输入

cin>>n;
    ll a[n+1];//注意要多开辟一个空间
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }

    cin>>m;
    ll b[m+1];
    for(int i=0;i<=m;i++){
        cin>>b[i];
    }

两个系数数组都要记得多开辟一个空间，因为n和m代表最高次数，1-n次再加上一个0次，一共需要n+1个空间

完整代码

#include <iostream>
using namespace std;
#define MOD 10007
typedef long long ll;
int n,m,q;
ll cal(ll base1,ll base2,ll* a,ll* b){
    ll ret1 = 0;
    ll x=1;
    for(int i=0;i<=n;i++){
        ret1=(ret1%MOD+x*a[i]%MOD)%MOD;
        x=(x*base1)%MOD;
    }

    ll ret2 = 0;
    x=1;
    for(int i=0;i<=m;i++){
        ret2=(ret2%MOD+x*b[i]%MOD)%MOD;
        x=(x*base2)%MOD;
    }
    return (ret1*ret2)%MOD;
}
int main(){
    cin>>n;
    ll a[n+1];
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }

    cin>>m;
    ll b[m+1];
    for(int i=0;i<=m;i++){
        cin>>b[i];
    }

    cin>>q;
    for(int i=0;i<q;i++){
        ll base1,base2;
        cin>>base1>>base2;
        cout<<cal(base1,base2,a,b)<<endl;
    }
}

原文地址：https://blog.csdn.net/zxy13149285776/article/details/143724527

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！