Not logged in. · Lost password · Register

SpeedyGonzalez
Member since Jul 2017
103 posts
Subject: 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:
1. Bestimme pro Person P die Differenz ∆P der insgesamt bei P eingehenden und ausgehenden Geldbeträge.
2. Ermittle daraus den größten Schuldner S sowie den größten Geldgeber G.
3. Begleiche den betragsmäßig kleineren Betrag ∆min von ∆S und ∆G.
4. 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
This post was edited on 2019-03-13, 12:13 by SpeedyGonzalez.
SpeedyGonzalez
Member since Jul 2017
103 posts
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
andi-erlangen
Member since Apr 2019
1 post
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.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen