脚本宝典收集整理的这篇文章主要介绍了OO第三单元总结,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
public int kruskal(int id) throws PersonIdNotFoundException {
ArrayList<Integer> nodes = new ArrayList<>();
ArrayList<Edge> edges = new ArrayList<>();
int[] ends = new int[2505];
int result = 0;
for (Person person : people) {
if (isCircle(id, person.getId())) {
nodes.add(person.getId());
edges.add(new Edge(person.getId(), person.getId(), 0));
}
}
for (Edge value : edgeArrayList) {
if (nodes.contains(value.getStart()) && nodes.contains(value.getEnd())) {
if (getPosITion(nodes, value.getStart()) < getPosition(nodes, value.getEnd())) {
edges.add(value);
} else {
edges.add(new Edge(value.getEnd(), value.getStart(), value.getWeight()));
}
}
}
edges.sort(Edge::compareTo);
for (Edge edge : edges) {
int p1 = getPosition(nodes, edge.getStart());
int p2 = getPosition(nodes, edge.getEnd());
int n = getEnd(ends, p1);
int m = getEnd(ends, p2);
if (n != m) {
ends[n] = m;
result += edge.getWeight();
}
}
return result;
}
public int dijkstra(int id1, int id2) {
HashMap<Integer, Integer> pending;
pending = new HashMap<>();
HashMap<Integer, Integer> solved;
solved = new HashMap<>();
ArrayList<Edge> edges = new ArrayList<>();
for (Person person : people) {
if (find(id1) == find(person.getId())) {
pending.put(person.getId(), INF);
}
}
for (Edge edge : edgeArrayList) {
if (pending.containsKey(edge.getStart()) && pending.containsKey(edge.getEnd())) {
edges.add(edge);
}
}
pending.remove(id1);
solved.put(id1, 0);
int lastSolved = id1;
int minValue = 0;
while (lastSolved != id2) {
for (int i = 0; i < edges.size(); i++) {
Edge edge = edges.get(i);
if (solved.containsKey(edge.getStart()) && solved.containsKey(edge.getEnd())) {
edges.remove(edge);
i--;
} else if (pending.containsKey(edge.getStart())
&& solved.containsKey(edge.getEnd())) {
pending.put(edge.getStart(), min(pending.get(edge.getStart()),
edge.getWeight() + solved.get(edge.getEnd())));
} else if (pending.containsKey(edge.getEnd())
&& solved.containsKey(edge.getStart())) {
pending.put(edge.getEnd(), min(pending.get(edge.getEnd()),
edge.getWeight() + solved.get(edge.getStart())));
}
}
minValue = INF;
for (Integer key : pending.keySet()) {
if (minValue > min(minValue, pending.get(key))) {
minValue = min(minValue, pending.get(key));
lastSolved = key;
}
}
solved.put(lastSolved, minValue);
pending.remove(lastSolved);
}
return minValue;
}
每次作业出现的性能问题都是某一方法复杂度大于了O(n^2),需要对算法进行一定程度上的优化,如并查集的算法终止条件,或者对于一些重复性访问操作能否用空间换时间,提前将用户需要求的变量存储起来,访问的时候直接输出就行.
/*@ public normal_behavior
@ requires (exists int i; 0 <= i && i < people.length; people[i].getId() ==
@ customerId && people[i] instanceof Customer) && (exists int i; 0 <= i &&
@ i<= messages.length;messages[i].getId() == advertiseId && messages[i]
@ instance of advertise)
@ assignable poeple[*],money;
@ ensures messages.length == old(messages.length) + 1
@ ensures getPerson(customerId).money == old(getPerson(customerId).money) -
@ getMessage(advertiseId).getPrice()
@ ensures getPerson(getMessage(advertiseId).getProducer()).money ==
@ old(getPerson(customerId).money) + getMessage(advertiseId).getPrice()
@ ensures (forall int i; 0 <= i && i < people.length;
@ (people[i].id != customerId && people[i].id !=
@ getMessage(advertiseId).getProducer() ==> people[i].money == old(people[i].money)
@ also
@ public exceptional_behavior
@ signals (PersonIdNotFoundException e)
@ (forall i; 0 <= i && i < people.size; !people[i].equals(producer))
@ signals (MessageIdNotFoundException e) !containsMessage(id);
@*/
public void buy(int customerId,int advertiseId) throw PersonIdNotFoundException, MessageIdNotFoundException;
/*@ public normal_behavior
@ requires (exists int i; 0 <= i && i < people.length;
@ people[i].getId() == id && people[i] instanceof Producer);
@ assignable products;
@ ensures products.length == old(products.length) + 1;
@ ensures (exists int i; 0 <= i && i < products.length; products[i] ==
@ product);
@ ensures (forall int i; 0 <= i && i < old(products.length);
@ (exists int j; 0 <= j && j < products.length; products[j] ==
@ (old(products[i]))));
@ also
@ public exceptional_behavior
@ signals (PersonIdNotFoundException e)
@ (forall i; 0 <= i && i < people.size; !people[i].equals(producer))
@*/
public void addProduct(Product product, int id) throws PersonIdNotFoundException;
/*@ public normal_behavior
@ requires (exists int i; 0 <= i && i < people.length; people[i].getId() ==
@ id && people[i] instanceof Advertiser) && (exists int i; 0 <= i && i<=
@ products.length;products[i].getId() == adcertise.getProductId())
@ assignable messages;
@ ensures messages.length == old(messages.length) + 1
@ ensures (exists int i; 0 <= i && i < messages.length; messages[i] ==
@ advertise);
@ ensures (forall int i; 0 <= i && i < old(messages.length);
@ (exists int j; 0 <= j && j < messages.length; messages[j] ==
@ (old(messages[i]))));
@ also
@ public exceptional_behavior
@ signals (PersonIdNotFoundException e)
@ (forall i; 0 <= i && i < people.size; !people[i].equals(producer))
@*/
public void advertise(int id,Message advertise) throw PersonIdNotFoundException;
以上是脚本宝典为你收集整理的OO第三单元总结全部内容,希望文章能够帮你解决OO第三单元总结所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。