求两个多项式乘积的问题相信大家在中学时经常碰到,它是这样的一个问题: 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
List
HashMap
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
Set
for(Map.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 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); } } 代码中没有针对一个多项式,另一个为空或""的情况进行处理,根据本人的理解,不应该出现这种情况。