精华内容
下载资源
问答
  • 题目 背景:编程实现如下功能:对输入的一元多项式,进行同类合并,并按指数降序排序,输出处理后的一元多项式。 说明:多项式由若干个单项式组成,单项式之间为加、减(+,-)关系。...格式说明一元多

    题目
    背景:

    编程实现如下功能:对输入的一元多项式,进行同类项合并,并按指数降序排序,输出处理后的一元多项式。
    说明:

    多项式由若干个单项式组成,单项式之间为加、减(+,-)关系。
    单项式指数字与字母幂的乘积构成的代数式。对一元多项式,字母只有一种。
    同类项合并指将多项式中指数相同的单项式,系数经过加减求和,合并为一个单项式。按指数降序指多项式中,单项式按指数从大到小顺序相连。
    格式说明

    一元多项式输入输出时以字符串形式表示,格式如下

    单项式之间用单个加减运算符相连,运算符:+,-
    单项式由系数、字母、指数标识符、指数依次直接相连组成,各部分均不能省略。
    系数:只由若干0到9数字字符组成(系数不等于0,且不以0开头)
    字母:X
    指数标识符:^
    指数:只由若干0到9数字字符组成(指数可等于0,不等于0时不以0开头)
    其他约定
    输入不为空串,输出若为0则以空串表示
    字符串中除以上字符,不包含空格等其他字符,字符串尾部以’\0’结束
    多项式中第一个单项式前加运算时省略+符号,减运算时有-符号
    注意:输入多项式符合上述格式,无需检查;输出多项式格式由考生程序保证

    规格

    输入多项式满足如下规格,考生程序无需检查:
    –0<单项式系数<=1000<>
    –0<=单项式指数<=3000<>
    –单项式个数不限制,但同类项合并处理后,单项式的系数小于65535。
    示例

    例一
    输入:
    “7X^4-5X^6+3X^3”
    输出:
    “-5X^6+7X^4+3X^3”
    例二
    输入:
    “-7X^4+5X^6-3X^3+3X^3+1X^0”
    输出:
    “5X^6-7X^4+1X^0”

    解析
    该题目有几个难点
    1、输入的字符串如何进行分解得到单项表达式,怎么从单项表达式里面提取系数和指数?
    2、每个单项表达式怎么表示?
    3、具体算法怎么完成?要求单项式按指数从大到小顺序相连怎么实现?
    整体思路
    首先说一下我的思路:我是利用单链表的思想解决这个问题,每个单项表达式存为一个节点,先利用正则表达式将该字符串进行分解,得到一个以单项表达式为节点的链表,然后一次遍历链表里面的节点进行计算,新建一个有序的存放计算结果的链表,将计算得到的结果有序的插入,最后利用Stringbuffer将链表里面的信息转换为字符串

    具体实现
    1、单项表达式节点的表示

    /**
     * 单项表达式节点
     *
     */
    class Expression {
        char calc;//每个单项表达式前面的符号,可以是+,-
        int index;// 指数
        int ratio;// 系数
        boolean counted = false;// 该项是否已经计算过,默认情况下是没有计算过
        Expression next;//链接链表的指针
    }

    counted用来表示该单项表达式是否已经计算过,如果已经计算过遍历到的时候也直接跳过,不再进行计算。

    2、将字符串转换为链表
    代码注释的很详细,如果正则表达式看不懂的自己百度一下

    private static Expression GetExpression(String s){
            Expression tail = new Expression();     //  表达式链表的尾指针
            Expression head = new Expression(); //表达式链表的头指针
            head=tail;
            Pattern p=Pattern.compile("[\\+\\-]{0,1}([\\d]){1,4}(X\\^)([\\d]){1,4}");
            Matcher m=p.matcher(s);
            Pattern p1=Pattern.compile("([\\d]){1,4}");
            Matcher m1;
    //      在while大循环里面  ,s1分别为7X^4,+5X^6,+3X^3
            while(m.find()){
                Expression tmp = new Expression();
    //          得到某一个单项表达式  比如 : +5X^6
                String s1=m.group();
                //将运算符号存入单项表达式节点 比如 :+
                if(s1.startsWith("+")||s1.startsWith("-"))
                    tmp.calc=s1.charAt(0);
                else
    //              如果某个单项式千前面没有计算符号,那就是“+”
                    tmp.calc='+';
                //利用正则表达式找出单项表达式的系数和指数  该正则表达式为([\\d]){1,4} 
                m1=p1.matcher(s1);
    //          查看是否有匹配的项目 ,即单项表达式里面是否有一串数字,其中第一串是系数,第二串是指数
                if(m1.find()){
    //              将系数写入单项式节点 比如:5
                    tmp.ratio=Integer.parseInt(tmp.calc+m1.group());
    //              去查找第二串数字
                     m1.find();
    //             将第二串数字写入单项式节点  比如:6
                    tmp.index=Integer.parseInt(m1.group());
                }
    //          将这个单项式节点放入整个链表
                tail.next=tmp;
                tail=tmp;
            }
            return head;
       }

    3、相同指数的单项表达式的合并

    private static String calculate(Expression es) {
    //      异常输入判断
            if (es == null && es.next != null)
                return null;
            es = es.next;
            Expression ResultHead = new Expression();//新链表的头指针
    //      遍历查看尚未被计算过的单项表达式节点
            while (es != null && es.counted == false) {
                Expression resultTmp = new Expression();
                int index = es.index;
                int ratio = es.ratio;
                es.counted = true;
    //          子循环里面使用一个新的指针,避免两个指针的干扰
                Expression es1 = es.next;
                while (es1 != null) {
    //              如果找到一个指数相同而且又没有计算过的节点,则进行计算,并将该节点的标记设置为已经计算过
                    if (es1.index == index && es1.counted == false) {
                        ratio += es1.ratio;
                        es1.counted = true;
                    }
                    es1 = es1.next;
    
                }
                resultTmp.index=index;
                resultTmp.ratio=ratio;
    //          某个指数的单项表达式均计算完成后,加入到结果链表中
                InsertList(ResultHead, resultTmp);
                es=es.next;
            }
    
            return GetString(ResultHead);
        }

    4、将计算出的结果插入到有序的链表中去
    这段代码逻辑有点乱,还可以优化一下,因为要求指数最后输出要从大到小,这里必须得弄成有序的来链表。

    /**
         * 计算后放结果的链表是有序的,按照的指数从大到小进行排放,所以一个新节点也需要有序的插入该链表
         */
        private static Expression InsertList(Expression resultHead,Expression tmp){
    //      如果链表中现在还没有节点,直接放在后面
            Expression r1=resultHead;
             if(resultHead.next==null)
                 resultHead.next=tmp;
             Expression resultTail=resultHead.next;
    //          如果链表中现在只有一个节点
             if(resultTail.next==null)
             {
                 if(tmp.index<resultTail.index)
                 {
                     resultHead.next=tmp;
    
                 }
                 else if(tmp.index>resultTail.index){
                     resultHead.next=tmp;
                     tmp.next=resultTail;
                 }       
             }
    //       链表中已经有多个节点了
    //       新的节点比第一个节点大
             else if(tmp.index>resultTail.index)
             { 
                 resultHead.next=tmp;
                 tmp.next=resultTail;
             }
    //       新的节点比第一个节点小,则需要两个指针在链表里面搜寻合适的位置
             else{
             boolean done=false;
             while(!done){
                resultHead=resultHead.next;
                resultTail=resultTail.next;
                if(resultTail!=null){
    //              如果找到插入元素的值在链表中的两个节点的值之间,则把该元素插入在这两个值之间
                 if(tmp.index<resultHead.index&&tmp.index>resultTail.index){
                     resultHead.next=tmp;
                     tmp.next=resultTail;
                     done=true;
                 }
                }
    //          如果查询到链表的尾节点的元素依然比要插入的元素大,则把该元素放在尾节点的后面
                else{
    
                    resultHead.next=tmp;
                    done=true;
                }
             }
             }
            return r1;
        }

    5、利用Stringbuffer将链表信息转换为字符串

        /**
         * 根据链表得到字符串
         */
        private static String GetString(Expression ResultHead){
    //      利用Stringbuffer存放字符串表达式
            StringBuffer resultString=new StringBuffer();
            ResultHead=ResultHead.next;
    //      依次将系数,X^,指数放进StringBuffer中
            while(ResultHead!=null){
    //          如果表达式的系数大于0而且又不是第一个单项表达式,则需要在其前面添加一个“+”
                if(ResultHead.ratio>=0&&resultString.length()!=0)
                resultString.append("+");
                resultString.append(ResultHead.ratio);
                resultString.append("X^");
                resultString.append(ResultHead.index);
                ResultHead=ResultHead.next;
            }
            return resultString+"";
        }

    6、最后主函数

    public static void main(String[] args) {
            String s = "7X^4+5X^6+3X^3";
            System.out.println(calculate(GetExpression(s)));
        }

    如有错误或者需要改正的地方,欢迎各位指正。

    展开全文
  • 一元多项式相加的算法和C++实现

    万次阅读 多人点赞 2015-08-13 15:53:08
    利用顺序表的链式存储实现一元多项式的加法

    利用顺序表的链式存储实现一元多项式的加法

    一、数据结构

    <span style="font-size:18px;">struct PolyNode
    {
    	float coef;  //多项式的系数
    	int expn;    //多项式的指数
    	PolyNode *next;   //指向下一个结点的指针
    };</span>
    <span style="font-size:18px;">void InitList(PolyNode *&L)     //初始化多项式单链表</span>
    <span style="font-size:18px;">void InsertNode(PolyNode *&L, float c, int e, int i)  //在多项式链表的第i个位置插入结点</span>
    <span style="font-size:18px;">void print(PolyNode *L)   //打印多项式</span>
    <span style="font-size:18px;">void SortList(PolyNode *&L)     //按指数非递减给多项式排序</span>
    <span style="font-size:18px;">void CreateList(PolyNode *&L, float C[], int E[], int n)    //创建多项式单链表</span>
    <span style="font-size:18px;">PolyNode *AddPoly(PolyNode *L1, PolyNode *L2)       //一元多项式相加</span>


    二、核心算法描述

    1.创建一个空的链表,用作存储两个多项和的链表

    2.调用SortList函数,给两个多项式按指数非递减的顺序给多项式排序

    3.比较两个多项式链表的第一项的指数,如果链表a>b,则将较小指数的b的系数和指数复制到新建空结点s,再讲s链接到链表c的末尾;否则,换成a。如果a=b,则又分为两种情况:如果a的结点和b的结点的系数之和不为0,就将a和b的系数之和复制给s,将a或b任意一个的指数复制给s,再将s链接到c的末尾;如果为0,就跳过a和b的这两个结点,继续后面的比较。重复上述过程,知道任意一个链表为空为止。

    4.如果a为空,就将b的后面部分复制给s,然后依次链接到c的末尾;如果b为空,就将a的后面部分复制给s,然后依次链接到c的末尾。


    三、完整程序代码

    #include "stdafx.h"
    
    #include <iostream>
    using namespace std;
    
    /*实现一元多项式的加法*/
    
    struct PolyNode
    {
    	float coef;  //多项式的系数
    	int expn;    //多项式的指数
    	PolyNode *next;   //指向下一个结点的指针
    };
    
    void InitList(PolyNode *&L)     //初始化多项式单链表
    {
    	L = new PolyNode;       //生成一个头结点
    	L->next = NULL;
    }
    
    void InsertNode(PolyNode *&L, float c, int e, int i)  //在多项式链表的第i个位置插入结点
    {
    	PolyNode *p, *q;
    	q = new PolyNode;
    	q->coef = c;
    	q->expn = e;
    	q->next = NULL;
    	p = L;
    	int j = 1;
    	while (j < i)     //找到第i-1个结点,在它的后面插入结点
    	{
    		p = p->next;
    		++j;
    	}
    	q->next = p->next;
    	p->next = q;
    }
    
    void print(PolyNode *L)   //打印多项式
    {
    	PolyNode *p;
    	p = L->next;
    	while (p != NULL)
    	{
    		cout << "(" << p->coef <<","<<p->expn<< ") ";
    		p = p->next;
    	}
    	cout << endl;
    }
    
    void SortList(PolyNode *&L)     //按指数非递减给多项式排序
    { 
    	PolyNode *p, *q, *pre;
    	p = L->next;
    	L->next = NULL;
    	while (p != NULL)
    	{
    		if (L->next == NULL)       //处理第一个结点
    		{
    			L->next = p;
    			p = p->next;
    			L->next->next = NULL;
    		}
    		else         //处理剩余其他结点
    		{
    			pre = L;
    			q = pre->next;
    			while (q && q->expn < p->expn)
    			{
    				pre = q;
    				q = q->next;
    			}
    			q = p->next;
    			p->next = pre->next;
    			pre->next = p;
    			p = q;
    		}
    	}
    }
    
    void CreateList(PolyNode *&L, float C[], int E[], int n)    //创建多项式单链表
    {
    	int i;
    	InitList(L);
    	for (i = 0; i < n; i++)
    	{
    		InsertNode(L, C[i], E[i], i+1);
    	}
    }
    
    PolyNode *AddPoly(PolyNode *L1, PolyNode *L2)       //一元多项式相加
    {
    	PolyNode *pa, *pb, *s, *pc,*p; 
    	PolyNode *tc;    //创建尾节点
    	pc = new PolyNode;
    	pc->next = NULL;    /*pc为新建单链表的头结点*/
    	tc = pc;   /*tc始终指向新建单链表的最后结点*/
    	pa = L1->next;
    	pb = L2->next;   //获得多项式单链表的第一个结点
    	while (pa!=NULL && pb!=NULL)    //pa,pb都不为空,就进行比较,否则,跳出while
    	{
    		if (pa->expn < pb->expn)         //将*pa结点复制到*s并链到pc尾
    		{
    			s = new PolyNode;
    			s->coef = pa->coef;
    			s->expn = pa->expn;
    			s->next = NULL;
    			tc->next = s;
    			tc = s;
    			pa = pa->next;
    		}
    		else if (pa->expn > pb->expn)      //将*pb结点复制到*s并链到pc尾
    		{
    			s = new PolyNode;
    			s->coef = pb->coef;
    			s->expn = pb->expn;
    			s->next = NULL;
    			tc->next = s;
    			tc = s;
    			pb = pb->next;
    		}
    		else         //pa->expn=pa->expn时的情况
    		{
    			if (pa->coef+pb->coef!=0)     //如果相加系数之和不为0,则将新结点插在tc后面
    			{
    				s= new PolyNode;
    				s->coef = pa->coef + pb->coef;
    				s->expn = pa->expn;
    				s->next = NULL;
    				tc->next = s; 
    				tc = s;
    			}
    			pa = pa->next;   //跳过当前的结点,继续后面的结点的比较
    			pb = pb->next;
    		}
    	}
    	//将尚未扫描完的余下结点复制并链接到pc单链表之后
    	if (pa != NULL)        //pb为空   
    		p = pa;
    	else                  //pa为空
    		p = pb;
    	while (p != NULL)   
    	{
    		s = new PolyNode;
    		s->coef = p->coef;
    		s->expn = p->expn;
    		s->next = NULL;
    		tc->next = s;
    		tc = s;
    		p = p->next;
    	}
    	return pc;
    }
    
    int main()
    {
    	PolyNode *La, *Lb, *Lc;
    	float C1[] = { 3, 7, 9, 5 }, C2[] = { 8, 22, -9 };
    	int E1[] = { 1, 0, 8, 17 }, E2[] = { 1, 7, 8 };
    	InitList(La);
    	InitList(Lb);
    	InitList(Lc);
    	CreateList(La, C1, E1, 4);
    	CreateList(Lb, C2, E2, 3);
    	cout << "原多项式为:" << endl;
    	print(La);
    	print(Lb);
    	SortList(La);
    	SortList(Lb);
    	cout << "按指数非递减排序后的多项式:" << endl;
    	print(La);
    	print(Lb);
    	cout << "多项式相加的结果为:" << endl;
    	Lc = AddPoly(La,Lb);
    	print(Lc);
    	return 0;
    }

    四、实验截图


    五、总结

    暑假比较闲,所以自己就想这把大二学的数据结构的一些算法全部实现一遍,分享到网上,供大家交流学习。经过差不多半天的时间吧,自己先是好好研究了单链表的各种操作特性,然后分析了怎样用单链表存储多项式,怎样实现多项式的加法的各种细节,先在草稿纸上写了大概的伪代码,然后再敲代码实现,边敲代码,边思考每行每部分的功能联系,这样既能节约时间,也能尽量减少过程的代码产生。总之,这半天的时间没白费,自己收获很多,只有亲自动手实践,才能真正懂得一个知识点的内涵。所以,我也希望看到这篇文章的同学们也多多动手,亲自去实现自己的算法,这样自己才会慢慢收获一些东西,慢慢成长。




    展开全文
  • 一元多项方程式的实现主要在于加减法。其主要有系数和指数,如果用顺序表来表示,最大指数如果很大比如1000,但是中间又有很多指数没有,所以会浪费很多空间,所以用链表来实现虽然麻烦但是节约空间,下面来看算法的...

    一元多项方程式的实现主要在于加减法。其主要有系数和指数,如果用顺序表来表示,最大指数如果很大比如1000,但是中间又有很多指数没有,所以会浪费很多空间,所以用链表来实现虽然麻烦但是节约空间,下面来看算法的实现

    一:这是节点的结构体

    #include<iostream>
    using namespace std;
    struct Item
    {
     double coef;
     int expn;
     Item *next;
     Item();
    };


    Item::Item()
    {
    coef=0;
    next=NULL;
    }

    二:list_cometrue.h为实现方法的类

    #include"link_list.h"


    class List
    {
    protected:
    Item *head;
    public:
    void Init();
    List();
    ~List();
    void create(double co[],int ex[],int p);//创建链表
    void out();
    int length();//求链表p的长度
    void getelem(int position,Item *p);//返回指定位置的结构为*p;
    List operator+(const List &p1);


    };


     void List::Init()
    {
    head=new Item;
    }


     List::List()
     {
     Init();
     }


     List::~List()
     {
     }


     void List::create(double co[],int ex[],int p)//创建链表
    {
    Item *ptr,*p2;
    ptr=head;
      for(int i(0);i<p;i++)
      {
    p2=new Item; 
        p2->coef=co[i];
        p2->expn=ex[i];
        ptr->next=p2;
    ptr=p2;   
      }
      
     
     }


     void List::out()//输出链表
     {//Item *ptr=p.head;
        for(Item *ptr=head->next;ptr!=NULL;ptr=ptr->next)
    {
    cout<<ptr->coef<<"^"<<ptr->expn<<"+";


    }
    cout<<endl;
     }


     int List::length()
     {
     int count(0);
     for(Item *ptr=head->next;ptr!=NULL;ptr=ptr->next)
     count++;
     return count;
     }


     void List::getelem(int position,Item *p)//取指定位置的节点复制给p
     {Item *ptr=head->next;
       if(position<0||position>length())
       {
       cout<<"不存在这个元素"<<endl;
       }else{
       //Item *ptr=head->next;
       for(int i(0);i!=position;ptr=ptr->next,i++)
       {
       p->coef=ptr->coef;
       p->expn=ptr->expn;
       } 
       }
     }
     


    List List::operator+(const List &p1)//运算符重载实现加法,
    {    
    Item *la=head->next;
         Item *lb=p1.head->next;
     List List_link;
     Item *lc=List_link.head;
     cout<<"shifoujinru"<<endl;

        while(la!=NULL&&lb!=NULL)
    {
     if(la->expn>lb->expn)
     {
     lc->next=lb;
     lb=lb->next;
     lc=lc->next;
     }else if(la->expn<lb->expn){
     lc->next=la;
     la=la->next;
          lc=lc->next;
     }else{
     la->coef=la->coef+lb->coef;
     lc->next=la;
     la=la->next;
     lb=lb->next;
     lc=lc->next;
     }
    }
    if(la==NULL)
    {
    for(;lb!=NULL;lb=lb->next)
    {
    lc->next=lb;
    lc=lc->next;
    }
    }else
    {
    for(;la!=NULL;la=la->next)
    {
    lc->next=la;
    lc=lc->next;
    }
    }



       return List_link;
     }这个难点在于最后一个一元多项式加法的实现,这里用了运算符的重载,

    其中实现时应注意判断条件最后按照指数的从大到小的顺序来输出

    三:main函数

    #include"list_cometrue.h"


    void main()
    {
       List p,p1,p2;//p2为加厚的类
       double co[5]={5,4,3,2,1};
       int ex[5]={1,2,3,4,5};
       int num=sizeof(co)/sizeof(co[1]);
       p.create(co,ex,num);
       p.out();
       double co1[]={1,2,4,3,6,3,5};
       int ex1[]={1,3,3,4,5,6,7};
       int num1=sizeof(co1)/sizeof(co1[1]);
       p1.create(co1,ex1,num1);/创建函数
       p1.out();输出函数
       p2=p+p1;  //重载运算符 书实现链表想加
       p2.out();
     
       }
       

    }



        同理减法也是这样实现,只是要注意判断条件

    展开全文
  • 一元多项式乘法算法

    2010-06-19 12:08:36
    一元多项式乘法算法    一般的,一元多项式相乘有两种算法: 令A(i)(0&lt;=i&lt;n)、B(j)(0&lt;=j&lt;m)表示多项式A、B所对应的第i、j元素,C(i,j)表示A(i)*B(j)的结果。则有:...

    一元多项式乘法算法

     

           一般的,一元多项式相乘有两种算法:

    Ai)(0<=i<n)、Bj(0<=j<m)表示多项式AB所对应的第ij项元素,Cij)表示A(i)*B(j)的结果。则有:

     

    算法一:结果用链表存储

    此算法用Ai)去乘Bj(0<=j<m),逐项把每个结果插入结果链表ResultNode中。此算法下,每次相乘所得结果即Cij)要正确的插入ResultNode中,则要遍历链表以便合并同类项或生成新节点(若ResultNode有序,遍历量会相对减少)。

           算法二:结果用大型数组存储

    此算法会预先开辟一个很大的空间,如float result10000】,数组长度会根据实际情况进行调整。操作时同样用多项式A中的每一项去乘多项式B中的每一项,每次相乘得到的结果Cij)都将加入下标与Cij)指数相同的数组元素。

     

    算法一和算法二充分体现了时间与空间的矛盾:前者空间开销较小而时间开销较大,后者则恰恰相反。当然也有基于以上两种算法的变种算法,但其实质相同,并无较大改进。

     

    下面,我们尝试一种空间与时间均较优的算法。

    算法二造成空间浪费的主要原因在于无法预知最终多项式的项数,倘若可以预知结果多项式的项数,我们可以开辟较优的空间:若结果多项式的项数为num,我们可开辟空间

    index1num】和index2num】,在index1中按序存放相乘中先出现的多项式指数,而与index2中相同下标数组元素则存放该指数相对应的系数,每计算出一个新结果时只需遍历数组index1即可,该法较上两法优,而在实现上,要确定最终多项式的项数,则必须先进行一次两个多项式相乘,随后再重复一次多项式相乘操作。显然,两次多项式相乘操作会使效率大打折扣。那可以仅进行一次多项式相乘便可以得到结果吗?可以!完全可以!

     

           注意到多项式相乘时,关键因素是多项式指数确定问题,故为了简便明了,这里我们暂不考虑系数因素。而多项式相乘时,对结果指数而言,等效于将AB多项式的任意两个指数相加,故我们可建立等效该数学模型:已知两集合AhBh,定义集合Ah+Bh=Ch,这里

    +”操作是AhBh两多项式的任意两元素相加所得到的集合。

    为了更好的理解该算法原理,令Ah={125}Bh={125},求Ch

                                          编号: 0      1       2

                                                                          Bh 1          2            5

                                            Ah 1          2            5

    如右图所示:

    1)  因为Ah0+Bh(0) = 1 + 1 = 2 < Ah(1)+Bh(0)=2 + 1 = 32是尚未计算和结果中最小的一个。

    2)  因为Ah0+Bh(1) = 1 + 2 = 3 ==Ah(1)+Bh(0)=2 + 1 = 3Ah2+Bh(0) = 5+1= 6

    所以3是尚未计算和结果中最小的一个。

    3)  Ah0+Bh(3) = 1 + 5 = 6 < Ah(1)+Bh(2)=2 + 5 = 7, Ah2+Bh(0) = 5+1= 6

    所以6是尚未计算和结果中最小的一个。

    4)  Ah(1)+Bh(2)=2 + 5 = 7 ==  Ah2+Bh(1) = 5+2= 7

    所以7是尚未计算和结果中最小的一个。

    5) Ah2+Bh(2) = 5+5= 10

    所以10是尚未计算和结果中最小的一个。

     

    以上实例,并未模拟完全遍历AhBh集合,但成功的求出了Ch。基于引例,我们可以得到其计算原则:

    1)集合AB均为升序,这是该算法的前提。

    2)设立变量i=0,数组dataAhLength】用存放Ah中每个元素所对应的Bh中尚未进行计    算且计算结果不为最小和的元素的下标。

    3)计算data1=Ahi+Bhdatai】】,寻找满足Ahj+Bhdataj】】<= data1j>ij是否存在,若不存在,则data1尚未计算和结果中最小的一个。否则,把j看做变量i,继续该操作,直到找到最大的j使其和最小。

    4)若当前i多对应的datai<BhLength-1,datai++,否则i++

       data[AhLength-1] =BhLength,则所有加法和已找到,否则继续操作2

     

    其算法描述如下:

    Int main(){

       int anum,bnum;                               //定义Ah,Bh多项式项数
       int i =0,j =0,k=0,tp = 0;
       int data1 = 0,data2=0,temp = 0;                    //
    存放所得指数和的变量
       
      input
    anum;                                //输入Ah多项式项数

    input(aanum);                             //输入Ah多项式

    initdataanum;                          //初始化data【】数组

    inputbnum;                               //输入Bh多项式项数

    inputbbnum】);                            //输入Bh多项式

     

    //Ah,Bh按升序排列,如果有必要

    sorta;

    sortb;

    //依次得到最小的指数和
       while(data[anum-1]<bnum){
          data1 =  a[i]+b[data[i]];
          j = data[i] -1 ;
          k = i + 1;
          temp = data1;
          while(j>=0&&k<anum){
               data2=a[k] + b[data[k]];
               if(data2>temp){
                     if((k+1)==anum||data2<a[k+1]+b[data[k+1]])
                           break;
                     else{
                           data2 = a[k+1]+b[data[k+1]];
                           k ++;
                           j--;
                     }      
             }
           if(data2==temp){
                data[k]++;
                k++;
           }
          else{
                temp = data2;
                tp = k;
                k++;
                j--;
          }

    }//内层while
       if(temp>=data1)
            data[i]++;
        else{
            data1 = temp;
            data[tp]++;
         }

     if(data[i]>bnum-1)
           i++;

    //处理结果最小指数和data1,可以保存亦可直接输出,这里省略。

    }

    }

     

    指数问题一旦解决了,那么计算系数时,只要加上计算对应系数乘积和便可。

    附:附件中有其简单的基本实现程序。

    展开全文
  • NG机器学习公开课学习笔记,一元线性回归和梯度下降算法,以及R语言实现。
  • //注意这里要更新Rear的,保证在Rear->link } t2 = t2->link; } t1 = t1->link; } } m = P; P = P->link; delete m; return P; } void Print(Polynomial P) { if (!P)return; //在函数...
  • 输入数据包含组测试数据,每组数据包含两行一元多项式。每个多项式包含若干对整数,每对整数的第一个是系数,第二个是指数。每个多项式不超过100,整数间用空格隔开,并且指数是递减的。 输出 每组测试数据输出...
  • 在本文中分享的是用一种启发式算法——遗传算法来完成这工作。 大家对遗传算法不了解的话可以戳这里看简介。 首先介绍我们的主角,也就是目标函数的形式。其定义如下: def F(x): return np.sin(5*x)+ np.cos(4*x)...
  •   对于求取一元函数y = f(x)的极值问题,我们可以利用暴力的手段,通过细分自变量x的定义域区间,不断带入函数表达式中比较结果得到近似的最优解。这样的方法最大的好处就是简单,但是随之带来的问题就是收敛速度...
  • 求解一元高次多项式方程的所有实数根的算法 一元高次多项式的形式可以表示为: ...但这些算法的缺点是计算得到的解受到迭代初始的影响,另外在某些特定情况下,迭代也有可能不收敛。对于拥有个实数
  • 一元最值问题 [例] 求解x为多少时,目标函数y = sinx + 5x² + 2可取得最小值? 接下来分析一下这道题,它是求最值问题,我们按照高中的思路,容易想到求导,然后让导数值为0,求得的x即为极值点,接着通过相关计算...
  • 算法笔记】B1010 一元多项式求导 1010一元多项式求导(25 分) 设计函数求一元多项式的导数。(注:x​n​​(n为整数)的一阶导数为nx​n−1​​。) 输入格式: 以指数递降方式输入...
  • Galton在多项研究上都注意到这个现象,所以尽管这个英文单词跟数值预测没有任何关系,但这种研究方法仍被称作回归 。 那些高个子的后代的身高,有种回归到大众身高的趋势。 eg: 姚明身高2米26,叶莉身高1米90, 但是...
  • 设计函数求一元多项式的导数。 输入格式: 以指数递降方式输入多项式非零系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。 输出格式: 以与输入相同的格式输出导数多项式非零的系数和指数。数字间以...
  • Python实现线性回归简述假设函数、损失函数和梯度下降法Python实现线性回归对比sklearn实现的一元线性回归 简述 线性回归模型是机器学习里面最基础的一种模型,是为了解决回归问题,学习机器学习从线性回归开始最好...
  • 一元线性回归解释 从简单的一元线性回归开始。这里,我们以房屋面积(x)与房屋价格(y)为例,显而易见,二者是一种线性关系,房屋价格正比于房屋面积,我们假设比例为w: y^=w∗x\hat{y} = w * xy^​=w∗x 然而...
  • 加法挺简单的,乘法至今没有想到类似在线处理那样更好的算法,目前有几个思路: 1.把M与N多项式乘法看成M(M&lt;N)个多项式加法,问题转换为多项式加法问题。 2.逐计算,并且依次进行插入,问题可以转换...
  • LR算法

    2020-06-11 14:58:40
    LR算法 一、回归分析 回归分析就是利用已知数据样本产生拟合方程,从而对未知数据进行预测。 回归分析算法分类 回归分析算法分为线性回归算法和非线性回归算法。 2.1、线性回归 一元线性回归和多元线性回归。...
  • 算法】-000 一维多项式求算法】-000 一维多项式求 1、一维多项式的定义 2、普通解法 3、变形解法 4、空间换时间 5、多项式稀疏时的情况 1、一维多项式的定义   一维多项式是指如下所示的一元...
  • 为了计算一元多项式相加,参照书上P40的式子相加,需要建立在有序链表的基础上,跟merge的算法类似。链表的基本操作就不表述了。书P39-P43 二、需要用到的数据结构 1、单链表 //=============单链表=========...
  • 算法

    千次阅读 2013-12-12 16:51:34
    算法 译自From Wikipedia, the free encyclopedia   一种计算在位置名为A和B的两个数字a 和b的最大公约数 (g.c.d.) 的算法(欧几里得的算法)的流程图。  该算法通过在两个循环中连续减进行的:如果测试B≥A产生...
  • 并在此基础上,稍加改动,针对一元多项式建立相应的稀疏多项式ADT,使用单链表ADT的基本操作,设计并实现稀疏一元多项式的加法计算的算法设计。 内容:(1)请参照单链表的ADT模板,设计稀疏一元多项式的抽象数据...
  • NOMT 近似在线的目标跟踪算法

    千次阅读 2020-01-04 19:46:08
    目标跟踪算法可以分类两类:在线法和全局(批处理)方法。在线方法逐帧处理,适应大多数实际应用的需求;而全局方法考虑整个时间范围内的所有检测,具有更高的数据关联精度。在求解时,以往的工作会着眼于特征度量...
  • 手写算法-python代码实现Ridge(L2正则)回归

    千次阅读 热门讨论 2020-12-06 17:43:57
    手写算法-python代码实现Ridge回归Ridge简介Ridge回归分析与python代码实现1、标准方程法实现Ridge回归2、梯度下降法实现Ridge回归调用sklearn对比 Ridge简介 前面2篇文章,我们介绍了过拟合与正则化,比较全面的讲...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,416
精华内容 4,166
关键字:

一元多项值算法