Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
SS18 3 b) Schuld begleichen
Hallo,
in der o.g. Aufgabe sollen Schulden in einem Schuldennetzwerk aus Freunden beglichen werden.
Dazu ist folgender Algorithmus gegeben:
- Bestimme pro Person P die Differenz ∆P der insgesamt bei P eingehenden und ausgehenden Geldbeträge.
- Ermittle daraus den größten Schuldner S sowie den größten Geldgeber G.
- Begleiche den betragsmäßig kleineren Betrag ∆min von ∆S und ∆G.
- War @min = |∆S|, dann entferne S aus der Betrachtung (andernfalls G), speichere die Geldübergabe in Höhe von ∆min zwischen S und G im Ergebnis, korrigiere ∆G (bzw. ∆S) und wiederhole den Ablauf für die verbliebenen n-1 Personen.
class Schuld {
final String s; // Schuldner
final long b; // Betrag
final String g; // Geldgeber
public Schuld(String s, long b, String g) { // [s --b--> g] ... }FSI-Lösungsvorschlag:
a) Methode zur Bestimmung der initialen ∆P für jede Person P:
HashMap<String, Long> deltas(List<Schuld> schulden) {
HashMap<String, Long> ds = new HashMap<>();
Long dAlt; // altes Delta in ds
for (Schuld s : schulden) {
// ausgehender Betrag (von Schuldner):
dAlt = ds.get(s.s);
dAlt = dAlt == null ? 0L : dAlt;
ds.put(s.s, dAlt - s.b); //muss es nicht heissen dAlt + s.b?
// eingehender Betrag (zu Geldgeber):
dAlt = ds.get(s.g);
dAlt = dAlt == null ? 0L
: dAlt;
ds.put(s.g, dAlt + s.b); //muss es nicht heissen dAlt - s.b?
// Z.B. ist A Geldgeber ggü. B und D, gibt also 60. Ist ggü. C Schuldner in Höhe von 10.
//Laut der Angabe ist ∆A: -50, mit den hier Im Lösungsvorschlag
//angegebenen Vorzeichen würde sich für
// ∆A aber +50 ergeben wenn ich mich nicht täusche.
}
return ds;
}
b) Vervollständigen Sie die eigentliche Minimierung. Das minimierte Schuldennetzwerk wird in
ergebnis
aufgebaut und zurückgegeben.
List<Schuld> minimiere(List<Schuld> schulden) {
List<Schuld> ergebnis = new LinkedList<>();
HashMap<String, Long> deltas = deltas(schulden);
while (deltas.size() > 1) {
// ermittle groessten Schuldner S bzw. Geldgeber G:
String S = null, G = null;
long dS = 0, dG = 0; // Deltas von S bzw. G
for (String p : deltas.keySet()) {
long d = deltas.get(p);
if(S == null) {
S = p;
dS = d;
}
if (dS > d) {
S = p; //(Ergänzt) auch der String des groessten Schuldners muss
m.E.n. angepasst werden.
dS = d;
}
if (G == null) {
G = p;
dG = d;
}
if (dG < d) {
G = p; //(Ergänzt) auch der String des groessten Geldgebers muss
m.E.n. angepasst werden.
dG = d;
}
}
// begleiche Schuld von S nach G:
long dmin = Math.min(Math.abs(dS), Math.abs(dG));
if (deltas.size() == 2){ <------- HIER!
Schuld result = new Schuld (S, dMin, G);
ergebnis.add(result);
}
// aktualisiere deltas von S bzw. G:
if (dmin == Math.abs(dS)) {
long dNeuG = deltas.get(G) ;
dNeuG += dS; // hier habe ich: dNeuG -= dmin;
deltas.put(G, dNeuG);
deltas.remove(S);
} else {
long dNeuS = deltas.get(S);
dNeuS += dG; // hier habe ich: dNeuS += dmin;
deltas.put(S, dNeuS);
deltas.remove(G);
}
}
return ergebnis;
}Liebe Grüße
Speedy
Was passiert an der in Teilaufgabe b) mit “<— HIER” markierten Stelle? Warum prüfe ich, ob die Größe von delta gleich zwei ist? Bedeutet das nicht dass ich das Ergebnis nur dann ändere, wenn die übergebene Liste mit deltas nur 2 Einträge enthält?
Liebe Grüße,
Speedy
Ja, die if-Bedingung "if (deltas.size() == 2){ " ist falsch.
Vielleicht war >= 2 gemeint, aber das ist auch nicht nötig, da die while-Schleife nur bei deltas.size() > 1 ausgeführt wird.
Ich habe die Zeile also herausgenommen.