<%@ page pageEncoding="utf-8" %><%!
class Item implements Cloneable {
double coef;
int power;
Item prev;
Item next;
public Item() {
}
public Item(double coef, int power) {
this.coef = coef;
this.power = power;
}
@Override
public Item clone() {
try {
return (Item)super.clone();
} catch (CloneNotSupportedException e) {
return null;
}
}
@Override
public String toString() {
String coef_s = String.valueOf(coef);
if (power == 0) {
return coef_s;
} else if (power == 1) {
return coef_s + "<i>x</i>";
} else {
return coef_s + "<i>x</i>^" + power;
}
}
}
class Poly {
private Item head;
private Item rear;
public void add(double coef, int power) {
Item item = new Item(coef, power);
add(item);
}
public void add(Item item) {
if (item.coef == 0.0) {
return;
}
if (rear != null) {
rear.next = item; // 當前尾節點的下一個節點指向該節點
item.prev = rear; // 該節點的前一個節點指向尾節點
} else {
head = item;
item.prev = item.next = null;
}
rear = item;
}
public void add(Poly b) {
Item p = head;
Item q = b.head;
while (p != null && q != null) {
if (p.power == q.power) {
p.coef += q.coef;
if (p.coef == 0.0) {
delete(p);
}
p = p.next;
q = q.next;
} else if (p.power > q.power) {
insertBefore(q.clone(), p);
q = q.next;
} else {
p = p.next;
}
}
while (q != null) {
add(q.clone());
q = q.next;
}
}
public void delete(Item item) {
if (item == head) {
head = head.next;
} else {
item.prev.next = item.next;
if (item == rear) {
rear = item.prev;
}
}
}
public void insertBefore(Item item, Item pos) {
if (pos == head) {
item.prev = null;
item.next = head;
head.prev = item;
head = item;
} else {
item.prev = pos.prev;
item.next = pos;
pos.prev.next = item;
pos.prev = item;
}
}
@Override
public String toString() {
if (head == null) {
return "0";
}
String str = "";
for (Item p = head; p != null; p = p.next) {
if (p != head && p.coef >= 0.0) {
str += '+';
}
str += p.toString();
}
return str;
}
}
%><!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>多項式求值</title>
</head>
<body>
<%
Poly a = new Poly();
a.add(15.7, 0);
a.add(40.8, 1);
a.add(0.35, 2);
a.add(-0.14, 4);
out.println("<i>a</i> = " + a.toString() + "<br>");
Poly b = new Poly();
b.add(-3.1, 0);
b.add(-40.8, 1);
b.add(0.45, 2);
b.add(1.33, 3);
b.add(0.14, 4);
b.add(9.675, 5);
b.add(1.382, 6);
out.println("<i>b</i> = " + b.toString() + "<br>");
a.add(b);
out.println("<i>a</i>+<i>b</i> = " + a.toString() + "<br>");
out.println("<hr>");
Poly c = new Poly();
c.add(4, -1);
c.add(3.1, 0);
c.add(39.8, 1);
c.add(-0.14, 4);
c.add(-0.675, 5);
out.println("<i>c</i> = " + c.toString() + "<br>");
b.add(c);
out.println("<i>b</i>+<i>c</i> = " + b.toString() + "<br>");
%></body>
</html>
|
目前共有2篇帖子。
【演算法】用Java實現的一元多項式求和的演算法
回復帖子 |
