首页 > 试题广场 >

设计如何表示一个多项式并写出两个多项式相乘的程序。

[问答题]
求两个多项式乘积的问题相信大家在中学时经常碰到,它是这样的一个问题:
pa=an*x^n + an-1*x^(n-1) + … + a1*x + a0
pa=bm*x^m + bm-1*x^(m-1) + … + b1*x + b0
其中,an, an-1, …,a0, bm, bm-1, … ,b0 都是整数,范围[-10000, 10000]。0<=n, m <=1000。
pa*pb的结果也是一个多项式,请你编程来解决这个问题,你需要设计如何表示一个多项式并写出两个多项式相乘的程序。
C++:
string multiplyPolynormial(const string&pA,const string&pB)
Java:
String multiplyPolynormial(String pA,String pB)
其中pA和pB的格式都是“(-3,5),(87,4),(93,3),(3,0)”,表示一个多项式:-3*x^5 + 87*x^4 + 93*x^3 + 3
输入都是合法的,除了数字,左右括号和逗号没有别的任何字符,并且幂次都是从高到低排列的,输出也要求是这样一个标准的格式。
class Bag implements Comparable {
    int a;
    int n;
    Bag(int a, int n){
        this.a = a;
        this.n = n;
    }

    @Override
    public int compareTo(Object o) {
        Bag b = (Bag) o;
        return b.n-this.n;
    }
}
public class Multinomial {
    List<Bag> aa = new LinkedList<Bag>();
    List<Bag> bb = new LinkedList<Bag>();

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public void init(String a,String b){
        String[] as = a.split("\\),\\(");
        String[] bs = b.split("\\),\\(");
        if(as.length>0){
            as[0] = as[0].replace("(","");
            as[as.length-1] = as[as.length-1].replace(")","");
        }
        if(bs.length>0){
            bs[0] = bs[0].replace("(","");
            bs[bs.length-1] = bs[bs.length-1].replace(")","");
        }

        for(String s:as){
            String[] s1 = s.split(",");
            Bag b1 = new Bag(Integer.parseInt(s1[0]),Integer.parseInt(s1[1]));
            aa.add(b1);
        }
        for(String s:bs){
            String[] s1 = s.split(",");
            Bag b1 = new Bag(Integer.parseInt(s1[0]),Integer.parseInt(s1[1]));
            bb.add(b1);
        }
    }

    public void calculate(){
        for(Bag bag1:aa){
            for(Bag bag2:bb){
                int a = bag1.a*bag2.a;
                int n = bag1.n+bag2.n;
                if(map.containsKey(n)){
                    map.put(n,a + map.get(n));
                } else{
                    map.put(n,a);
                }
            }
        }
    }

    public String getRst(){
        List<Bag> rst = new LinkedList<Bag>();
        Set<Map.Entry<Integer, Integer>> entry = map.entrySet();
        for(Map.Entry<Integer, Integer> ent:entry){
            if(ent.getValue()!=0){
                rst.add(new Bag(ent.getValue(),ent.getKey()));
            }
        }
        if(rst.size()>0){
            Bag[] bags = new Bag[rst.size()];
            rst.toArray(bags);

            Arrays.sort(bags);
            StringBuilder sb = new StringBuilder("");
            for(int i=0;i<bags.length-1;i++){
                sb.append("(").append(bags[i].a).append(",").append(bags[i].n).append("),");
            }
            sb.append("(").append(bags[bags.length-1].a).append(",").append(bags[bags.length-1].n).append(")");
            return sb.toString();
        }
        else
            return "";
    }

    public static void main(String[] args){
        Multinomial mu = new Multinomial();
        mu.init("(2,3),(1,2),(5,0)","(0,2)");
        mu.calculate();
        String rst = mu.getRst();
        System.out.println(rst);
    }
}
代码中没有针对一个多项式,另一个为空或""的情况进行处理,根据本人的理解,不应该出现这种情况。
发表于 2015-01-26 14:59:47 回复(2)
#include<iostream>
#include<vector>
#include<map>
#include<sstream>

using namespace std;

void string2map(const string &pA,map<int, int> &map_pA)
{
	string A = pA;

	for(int i = 0; i<A.size();i++)
	{
		if(A[i]=='('||A[i]==','||A[i]==')')
		{
			A[i]=' ';
		
		}	
	}

	//cout<<A<<endl;
	stringstream ss;
	ss << A;
	int temp;
	vector<int> A_string2_int;

	while(ss>>temp)
	{
		//cout << temp <<endl;
		A_string2_int.push_back(temp);

	}

	for(int j = 0; j <(int)A_string2_int.size()-1;j = j+2)
	{
		map_pA[A_string2_int[j+1]] = A_string2_int[j];	

	}


}

string multiplyPolynormial(const string &pA,const string &pB)
{
	

	map<int, int> map_pA; 
	map<int, int> map_pB; 
	map<int, int> map_ANS; //存放当前pA项乘以pB的结果
	map<int, int> map_ANS_total; //幂次相同的相加,为最终结果

	vector<int>map_ANS_total2vector;

	string2map(pA,map_pA);//string 存入map中 key:幂数,value:当前幂数的系数
	string2map(pB,map_pB);

	int n =  map_pA.size()+map_pB.size() + 1;

	for(int k = 0; k <n;k++ )//map初始化
	{
		map_ANS.insert(pair<int,int>(k,0));
		map_ANS_total.insert(pair<int,int>(k,0));
	
	
	}
	
	for(int i = 0; i < map_pA.size(); i++)
	{
		for(int j = 0; j < map_pB.size();j++ )
		{
			map_ANS[i+j] = map_pA[i]*map_pB[j];   
			map_ANS_total[i+j] = map_ANS_total[i+j] + map_ANS[i+j]; 
		
		}
			
	}

	cout<<"the size of map_ANS_total is :"<<map_ANS_total.size()<<endl;
	int count = map_ANS_total.size();
	string answer;

	for(int m = 0; m < map_ANS_total.size();m++)//map转为string
	{
		count--;
		if(map_ANS_total[count]!=0)
		{
			char str[100];
			sprintf(str,"(%d,%d)",map_ANS_total[count],count);
			answer = answer + str;
		}	
	}

	cout<<answer<<endl;
	return answer;	
	
}


int main()
{

	string A = "(-3,5),(87,4),(93,3),(3,0)";
	string B = "(1,5),(2,4),(3,3),(4,0)";

	string answer;
	answer = multiplyPolynormial(A,B);
	cout<<answer<<endl;

	return 0;

}

发表于 2015-10-06 22:41:15 回复(0)
public static void main(String[] args) {
        // TODO Auto-generated method stub
           String pA = "(-3,5),(87,4),(93,3),(3,0)";
            String pB = "(-3,5),(87,4),(93,3),(3,0)";
            int[] a = multiplyPolynormial(pA, pB);
            print(a);
    }
    
    public static int[] multiplyPolynormial(String pA,String pB)
    {
        int a[]=replace(pA);
        int b[]=replace(pB);
        int []c=new int[a[1]+b[1]+1];// 新建一个字符串数组
    //用于存储各个 系数
        for(int i=0;i<c.length;i++)
        {
            c[i]=0;
        }
        
        for(int i=0;i<a.length;i++)
        {
            if(i%2==0)
            {
                for(int j=0;j<b.length;j++)
                {
                    if(j%2==0)
                    {
                        int xishu=a[i+1]+b[j+1];
                        c[xishu]=c[xishu]+a[i]*b[j];
                    }
                }
            }
            
        }
        return c;
    }
    
    public static void print(int []a)
    {
        int length=a.length;
        if(a[0]!=0)
        {
            System.out.print(a[0]);
            
        }
        
        for(int i=1;i<length;i++)
        {
            if(a[i]>0)
            {System.out.print("+"+a[i]+"x^"+i);}
            
            else if(a[i]<0)
            {System.out.print(a[i]+"x^"+i);}
        }
        
        
    }
    
    
    // 运用正则表达式 将格式转换
    public static int[] replace(String s1)
    {String ss=s1;
    String t=ss.replace("(", "");
    String s=t.replace(")", "");
    
    String []ss1=s.split(",");    
    int []a= new int[ss1.length];
    for(int i=0;i<a.length;i++)
    {
        a[i]=Integer.parseInt(ss1[i]);//将字符串数组转换为数字数组
        
    }
    return a;
    }
    
发表于 2015-05-04 15:43:31 回复(0)
public classDemo3 {
 
    public static voidmain(String[] args){
        String pA ="(-3,5),(87,4),(93,3),(3,0)";
        String pB ="(-3,5),(87,4),(93,3),(3,0)";
        int[] a = multiplyPolynormial(pA, pB);
        duo(a);
    }
     
    public static int[] multiplyPolynormial(String pA, String pB){
        int[] a = replace1(pA);
        int[] b = replace1(pB);
        int[] c =new int[a[1]+b[1]+1];
         
        for(inti =0; i < a.length; i++) {
            if(i%2==0) {
                for(intj =0; j < b.length; j++) {
                    if(j%2==0) {
                        c[a[i+1]+b[j+1]] = c[a[i+1]+b[j+1]] + a[i]*b[j];
                    }
                }
            }
             
        }
        returnc;
    }
    public static voidduo(int[] a){
        StringBuffer sb =newStringBuffer();
        StringBuffer sb1 =newStringBuffer();
        intn =0;
        System.out.println("---------------------------------");
        for(inti = a.length-1; i >=0; i--) {
            if(a[i] !=0) {
                n++;
                if(i !=0) {
                    sb1.append("("+a[i]+","+i+"),");
                }else{
                    sb1.append("("+a[i]+","+i+")");
                }
                if(i!=0) {
                    if(n ==1) {
                        sb.append(a[i]+"*x^"+i+" ");
                         
                    }else{
                        if(a[i]>0) {
                            sb.append("+ "+a[i]+"*x^"+i+" ");
                        }else{
                            sb.append(a[i]+"*x^"+i+" ");
                        }
                    }
                }else{
                    if(a[i]>0) {
                        sb.append("+ "+a[i]);
                    }else{
                        sb.append(a[i]);
                    }
                }
                 
            }
        }
        System.out.println(sb.toString());
        System.out.println("---------------------------------");
        System.out.println(sb1.toString());
         
    }
    public static int[] replace1(String s1){
        String ss = s1;
        String t = ss.replace("(","");
        ss = t.replace(")","");
        String[] ss1  = ss.split(",");
        int[] a =new int[ss1.length];
        for(inti =0; i < a.length; i++) {
            a[i] = Integer.parseInt(ss1[i]);
        }
        returna;
    }
}
发表于 2015-04-02 23:16:25 回复(0)
public class Demo3 {

    public static void main(String[] args){
        String pA = "(-3,5),(87,4),(93,3),(3,0)";
        String pB = "(-3,5),(87,4),(93,3),(3,0)";
        int[] a = multiplyPolynormial(pA, pB);
        duo(a);
    }
    
    public static int[] multiplyPolynormial(String pA, String pB){
        int[] a = replace1(pA);
        int[] b = replace1(pB);
        int[] c = new int[a[1]+b[1]+1];
        
        for (int i = 0; i < a.length; i++) {
            if (i%2 == 0) {
                for (int j = 0; j < b.length; j++) {
                    if (j%2 == 0) {
                        c[a[i+1]+b[j+1]] = c[a[i+1]+b[j+1]] + a[i]*b[j];
                    }
                }
            }
            
        }
        return c;
    }
    public static void duo(int[] a){
        StringBuffer sb = new StringBuffer();
        StringBuffer sb1 = new StringBuffer();
        int n = 0;
        System.out.println("---------------------------------");
        for (int i = a.length-1; i >= 0; i--) {
            if (a[i] != 0) {
                n++;
                if (i != 0) {
                    sb1.append( "("+a[i]+","+i+"),");
                }else {
                    sb1.append( "("+a[i]+","+i+")");
                }
                if (i!=0) {
                    if (n == 1) {
                        sb.append(a[i]+"*x^"+i+" ");
                        
                    }else {
                        if (a[i]>0) {
                            sb.append("+ "+a[i]+"*x^"+i+" ");
                        }else {
                            sb.append(a[i]+"*x^"+i+" ");
                        }
                    }
                }else {
                    if (a[i]>0) {
                        sb.append("+ "+a[i]);
                    }else {
                        sb.append(a[i]);
                    }
                }
                
            }
        }
        System.out.println(sb.toString());
        System.out.println("---------------------------------");
        System.out.println(sb1.toString());
        
    }
    public static int[] replace1(String s1){
        String ss = s1;
        String t = ss.replace("(", "");
        ss = t.replace(")", "");
        String[] ss1  = ss.split(",");
        int[] a = new int[ss1.length];
        for (int i = 0; i < a.length; i++) {
            a[i] = Integer.parseInt(ss1[i]);
        }
        return a;
    }
}

输出结果:
---------------------------------
9*x^10 -522*x^9 + 7011*x^8 + 16182*x^7 + 8649*x^6 -18*x^5 + 522*x^4 + 558*x^3 + 9
---------------------------------
(9,10),(-522,9),(7011,8),(16182,7),(8649,6),(-18,5),(522,4),(558,3),(9,0)


发表于 2015-03-31 20:11:10 回复(0)