高数不胜寒
2021-12-05 11:08
采纳率: 100%
浏览 113

链表实现一元多项式相乘

【问题描述】
编写一个程序实现两个一元多项式相乘。
【输入形式】
首先输入第一个多项式中系数不为0的项的系数和指数,以一个空格分隔。且该多项式中各项的系数均为0或正整数,系数和最高幂次不会超过int类型的表示范围。对于多项式 anxn +a n-1 x n-1 + … + a1x1 + a0x0 的输入方法如下:
an n a n-1 n-1 … a1 1 a0 0
即相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为0的项。最后一项的指数后没有空格,只有一个回车换行符。
按照上述方式再输入第二个多项式。
【输出形式】
将运算结果输出到屏幕。将系数不为0的项按指数从高到低的顺序输出,每次输出其系数和指数,均以一个空格分隔,最后一项的指数后也可以有一个空格。
【样例输入】
10 80000 2 6000 7 300 5 10 18 0
3 6000 5 20 8 10 6 0
【样例输出】
30 86000 50 80020 80 80010 60 80000 6 12000 21 6300 10 6020 31 6010 66 6000 35 320 56 310 42 300 25 30 130 20 174 10 108 0
【样例说明】
输入的两行分别代表如下表达式:
10x80000 + 2x6000 + 7x300 + 5x10 + 18
3x6000 + 5x20 + 8x10 + 6
相乘结果为:
30x86000 + 50x80020 + 80x80010 + 60x80000 + 6x12000 + 21x6300 + 10x6020 + 31x6010 + 66x6000 + 35x320 + 56x310 + 42x300 + 25x30 + 130x20 + 174x10 + 108
提示:利用链表存储多项式的系数和指数。
【评分标准】
该题要求输出相乘后多项式中系数不为0的系数和指数,共有5个测试点。
【编程语言】
C/C++

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

  • 大榕树51 2021-12-05 11:52
    最佳回答
    
    yright © 1999-2020, CSDN.NET, All Rights Reserved
    
    
    
    Matlab精品一篇就够
      
    1
    
    暗中观察|.・`)
    关注
    BUAA(2021春)多项式相乘 原创
    2021-04-29 17:24:14
     2点赞
    
    暗中观察|.・`)  
    
    码龄1年
    
    关注
    BUAA数据结构第三次编程题——多项式相乘
    看前须知
    第三次上机题汇总
    题目内容
    问题描述
    输入形式
    输出形式
    样例
    样例说明
    题解
    易错点和难点
    参考代码
    补充测试的数据
    看前须知
    要点介绍和简要声明.
    
    第三次上机题汇总
    连续线段——结构体多级排序.
    
    猴子选大王(约瑟夫问题)+3种解决约瑟夫问题的方法.
    
    多项式相乘.
    
    文件加密(环)——要求循环链表熟练的删除操作.
    
    词频统计(数组或链表实现).
    
    题目内容
    问题描述
    编写一个程序实现两个一元多项式相乘。
    
    输入形式
    首先输入第一个多项式中系数不为0的项的系数和指数,以一个空格分隔。且该多项式中各项的指数均为0或正整数,系数和最高幂次不会超过int类型的表示范围。对于多项式 anxn +a n-1 x n-1+…+ a1x1+ a0x0 的输入方法如下:
    an n a n-1 n-1 … a1 1 a0 0
    即相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为0的项。最后一项的指数后没有空格,只有一个回车换行符。
    按照上述方式再输入第二个多项式。
    
    输出形式
    将运算结果输出到屏幕。将系数不为0的项按指数从高到低的顺序输出,每次输出其系数和指数,均以一个空格分隔,最后一项的指数后也可以有一个空格。
    
    样例
    【样例输入】
    
    10 80000 2 6000 7 300 5 10 18 0
    3 6000 5 20 8 10 6 0
    1
    2
    1
    2
    【样例输出】
    
    30 86000 50 80020 80 80010 60 80000 6 12000 21 6300 10 6020 31 6010 66 6000 35 320 56 310 42 300 25 30 130 20 174 10 108 0
    1
    1
    样例说明
    输入的两行分别代表如下表达式:
    10x80000+ 2x6000 + 7x300 + 5x10 + 18
    3x6000 + 5x20 + 8x10 + 6
    相乘结果为:
    30x86000 + 50x80020 + 80x80010 + 60x80000 + 6x12000 + 21x6300 + 10x6020 + 31x6010 + 66x6000+ 35x320 + 56x310 + 42x300 + 25x30 + 130x20 + 174x10 + 108
    
    题解
    易错点和难点
    本题不难,主要一个是读入,一个是计算。
    
    对于读入,我们需要用do while来进行读入,在读入的过程中,顺便记录多项式的项数。
    
    对于计算,有一个需要注意的一点,就是可能会出现很多的指数相同的项,所以我们计算(系数相乘,指数相加)完后,我们需要进行去重操作。但是此处有技巧,如果有指数相同的项,我们只需要保留第一项即可,如果不是,可能会造成不必要的麻烦。
    
    参考代码
    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<stdlib.h>
    #include<ctype.h>
    struct expression{            //多项式结构体 
        int coe;                //系数 
        int pow;                //指数 
    };
    typedef struct expression ex;
    ex a[2000],b[2000],c[2000];//a是第一个多项式,b是第二个多项式 ,c是最后相乘的多项式 
    int cmp(const void*p1,const void*p2);
    int main()
    {    
        int i,j,k=0;
        int n=0,nn=0;//n是第一个多项式的项数 ,nn是第二个多项式的项数  
        char ch;
        do   //读入第一个多项式 
        {
            scanf("%d%d%c",&a[n].coe,&a[n].pow,&ch);
            n++;
        }while(ch!='\n');
        do    //读入第二个多项式
        {
            scanf("%d%d%c",&b[nn].coe,&b[nn].pow,&ch);
            nn++;
        }while(ch!='\n');
        qsort(a,n,sizeof(ex),cmp); //按指数排序 
        qsort(b,nn,sizeof(ex),cmp);    //按指数排序 
        for(i=0;i<n;i++)
        {
            for(j=0;j<nn;j++)
            {
                c[k].coe=a[i].coe*b[j].coe;//系数相乘 
                c[k].pow=a[i].pow+b[j].pow;//指数相加 
                k++;
            }
        }
        qsort(c,k,sizeof(ex),cmp);//根据指数排序 
        for(i=0;i<k;i++)
        {
            if(c[i].pow == c[i+1].pow && c[i].pow!=0)//指数一样的进行去重操作 
            {
                c[i+1].coe+=c[i].coe;//指数一样的进行去重操作 
                c[i].coe=0;//去重项系数设为零 
            }
        }
        qsort(c,k,sizeof(ex),cmp);//根据指数排序 
        for(i=0;i<k;i++)
        {
            if(c[i].coe==0)//去重项不输出 
            {
                continue;
            }
            else
            {
                printf("%d %d ",c[i].coe,c[i].pow);//输出 
            }
        }
        return 0;
    }
    int cmp(const void*p1,const void*p2)
    {
        struct expression *a=(struct expression*)p1;
        struct expression *b=(struct expression*)p2;
        return b->pow-a->pow;
    }
    
    评论
    解决 1 无用
    打赏 举报 编辑记录

相关推荐 更多相似问题