Rekursion Tage Ansteckung gesamte Bevölkerung

[Martina1909]

Hallo,

wir haben folgende Aufgabenstellung bekommen:
Für das neuartige Coronavirus geht das deutsche Robert-Koch-Institut von einer Basisreproduktionszahl ungefähr 3 aus. Das heißt: Ohne Gegenmaßnahmen steckt jede infizierte Person etwa drei weitere Personen an. Wie viele Tage würde es bei ca. 200.000 Einwohnern dauern, bis das alle angesteckt sind, wenn sich am Tag 0 eine Person angesteckt hat, keine Einschränkungen gesetzt werde und angesteckte Personen pro Tag drei weitere Personen anstecken?

Dieser Algorithmus soll 1x nichtrekursiv und 1x rekursiv programmiert werden.

Nicht rekursiv wäre meine Idee so (Ergebnis 9 Tage):


Nur rekursiv weiß ich überhaupt nicht, was ich machen soll? Kann mir da vl. jemand weiterhelfen? Ich weiß nicht, wie ich die Tage rekursiv ausdrücken soll, also was der Sprung von einem Tag zum anderen ist (Idee: Logarithmus??).

Tausend Dank!

 

[kneitzel]

Bitte Code immer als Text in Code Tags (das Menu mit den drei Punkten über dem Eingabefeld!) posten. So ein Bild ist ja kaum zu entziffern!

 

[Martina1909]

public static void main(String args[]) throws FileNotFoundException {
        
        System.setOut(new PrintStream(new FileOutputStream("Aufgabe1a.csv")));
        System.out.println("Ausgabe fuer Aufgabe 1a:");
        System.out.println("tag;infiziert");
        System.out.println();
    
        int population = 200_000;
        int d = 0;
        int infectedPop = 1;
                
        if (population == 1) {
            System.out.println(d + ";" + infectedPop);
            return;
        }
    
        System.out.println(d + ";" + infectedPop);
        
        for (d = 1; infectedPop <= population; d++) {
            infectedPop *= 4;
            System.out.println(d + ";" + infectedPop);
            
        System.out.println("Es würde " + d + " Tage dauern, bis die gesamte Bevoelkerung infiziert ist");
        
        }

 

[Martina1909]

Hoffe, jetzt ist alles gut lesbar? Danke!

 

[kneitzel]

Ja, vielen dank. So ist es super!

Also ich würde als ersten Schritt die Berechnung in eine eigene Methode schreiben. Als Parameter hast Du ja drei Variablen, die Du übergeben könntest:

        int population = 200_000;
        int d = 0;
        int infectedPop = 1;

Wie würde das aussehen mit der Schleife?

Und wenn Du das hast. Dann wäre die Frage: Wie könnte denn eine Rekursion aussehen?
- Du gehst in der Schleife von Tag zu Tag. Wie ändern ich denn die Eingabewerte? Kannst Du da einen Aufruf zusammen stellen?
- Was wäre das Abbruch - Kriterium? Rekursion braucht immer ein Abbruch-Kriterium.

 

[Xyz1]

Ah, du rechnest mal 4, du sollst aber mit 3 rechnen...

 

[httpdigest]

Mal 4 ist korrekt. Jeder steckt 3 weitere an, bleibt aber selber auch noch angesteckt.
Explizit wäre es also: infectedPop = infectedPop + infectedPop * 3
Was dasselbe ist wie infectedPop *= 4

 

[fhoffmann]

        for (d = 1; infectedPop <= population; d++) {
            infectedPop *= 4;
            System.out.println(d + ";" + infectedPop);
            
        System.out.println("Es würde " + d + " Tage dauern, bis die gesamte Bevoelkerung infiziert ist");
        
        }

Hier stimmt zwar die Einrückung aber nicht die Klammerung.

 

[httpdigest]

Da es sich hier um eine exponentielle Funktion handelt, gibt es auch eine geschlossene, analytische Lösung und die einfachste "iterative" Lösung wäre eigentlich:

int population = 200000;
int R0 = 3; // <- Basisreproduktionszahl
int tage = (int) Math.ceil(Math.log(population) / Math.log(R0 + 1));

 

[Xyz1]

und System.out sollte man eigentlich nicht in eine Datei umleiten:

	public static void main(String args[]) {
		try (PrintStream s = new PrintStream(new FileOutputStream("Aufgabe1a.csv"))) {
			s.println("Ausgabe fuer Aufgabe 1a:");
			s.println("tag;infiziert");
			s.println();

			final int population = 200_000;
			int infectedPop = 1;

			int d;
			for (d = 1; infectedPop <= population; d++) {
				s.println(d + ";" + infectedPop);
				infectedPop *= 4;
			}
			s.println(d + ";" + infectedPop);
			System.out.println("Es würde zwischen " + (d - 1) + " und " + (d)
					+ " Tage dauern, bis die gesamte Bevoelkerung infiziert ist");
		} catch (IOException io) {
			io.printStackTrace();
		}
	}

 

[Martina1909]

@ Xyz1: Danke für deine Anleitung zur Entfernung von den System.outs, die auf eine Datei umleiten!! Das ist sehr lieb & hilfreich von dir!! (P.S. ist allerdings ein Vorschlag unserer Profs gewesen, das Excel soll einer bestimmten Vorgabe entsprechen und muss von uns auch abgegeben werden...) Und auch danke für die restlichen Korrekturen, werde ich mir ansehen =)

@ httpdigest: Danke für deine zusätzliche Lösung!!

@ fhoffmann: Danke für den Hinweis mit den Klammern, hab ich korrigiert...

@ JustNobody: Danke für deine Hinweise zur rekursiven Programmierung, das, was du bezüglich Schleife und Aufruf geschrieben hast, ist exakt, wo ich hänge... Aber damit ich mal die Richtung habe... Glaubst du, dass es darum geht, durch den rekursiven Aufruf die Tage zu zählen oder? Nicht die infizierte Bevölkerung, und die Tage erhalte ich als Nebenprodukt? Und könnte es eine Strategie sein, quasi von hinten anzufangen, also am Tag x sind mind. 200.000 infiziert, am Tag x-1 /4 weniger usw...? Irgendwie finde ich den Knopf nicht, dass ich mir das "Rekursive" vorstellen kann...

Coool, dass ihr mir alle so schnell geholfen habt!

 

[kneitzel]

Mir fehlt jetzt die Erkenntnis, wo es bei dir gerade scheitert. Daher sehe ich gerade keinen Ansatzpunkt, wie ich Dir weiter helfen kann, ohne eine Lösung zu präsentieren. Daher skizziere ich die Lösung etwas deutlich und hoffe, dass es etwas hilft.

Bisher hattest Du:

        int population = 200_000;
        int d = 0;
        int infectedPop = 1;
                
        if (population == 1) {
            System.out.println(d + ";" + infectedPop);
            return;
        }
    
        System.out.println(d + ";" + infectedPop);
        
        for (d = 1; infectedPop <= population; d++) {
            infectedPop *= 4;
            System.out.println(d + ";" + infectedPop);
        }

        System.out.println("Es würde " + d + " Tage dauern, bis die gesamte Bevoelkerung infiziert ist");

Was wir also als Eingang haben ist infectedPop und population, zurückgegeben wird d.

Also wird aus dem Code:

        int population = 200_000;
        int infectedPop = 1;

        int d = getDaysTillAllInfected(population, infectedPop);              
        System.out.println("Es würde " + d + " Tage dauern, bis die gesamte Bevoelkerung infiziert ist");

In der Funktion hast Du nun natürlich noch den Code der Berechnung.

        if (population == 1) {
            System.out.println(d + ";" + infectedPop);
            return;
        }
    
        System.out.println(d + ";" + infectedPop);
        
        for (d = 1; infectedPop <= population; d++) {
            infectedPop *= 4;
            System.out.println(d + ";" + infectedPop);
        }
        return d; // d ist ja das Ergebnis, das du vorher ausgegeben hattest.

Nun musst Du Dir überlegen, wie Du das Ergebnis rekursiv berechnen kannst.

Du kannst das doch aufschreiben mit

Tag, Poplulation, Erkrankt
0, 200_000, 1
1, 200_000, 4
2, ......

Das sieht doch schon wie eine Rekursion aus:
- Tag wird um eins erhöht, Population bleibt gleich, Erkankt verändert sich mit *4.
- Wann brichst du ab?
- Was ist dann das Ergebnis?

Das wäre erst einmal zu verstehen. Wenn Du diese Reihe von Hand aufschreiben kannst, sagen kannst, wann du aufhörst und was du dann zurück gibst, dann kannst Du es umsetzen.

 

[Martina1909]

Danke, danke!! Jetzt hab ich es, glaub ich, verstanden... Mein Problem war, dass ich mir gedacht habe, Rekursion bedeutet, dass man die Folge 2x durchlaufen muss, von vorne nach hinten und wieder retour... Aber Rekursion kann ja auch bedeuten, dass man einen Teil, der sich immer wieder wiederholt, in eine Funktion gibt, und diesen solange aufruft, bis man beim gewünschten Ergebnis abbrechen kann... So in etwa oder?

 

[Martina1909]

Jedenfalls hab ich jetzt den Code fertig, danke, danke, danke für die Unterstützung!
LG

 

[kneitzel]

Also die Idee der Rekursion ist schon, dass Du immer (mehr oder weniger) dieses Pattern hast:
Funktion:
-> Prüfe Abbruchbedingung und brich ab.
-> Mache etwas vor dem rekursiven Aufruf
-> Rekursiver Aufruf
-> Mache etwas nach dem rekursiven Aufruf.
-> Gebe Ergebnis zurück.

Wobei da vor/nach dem rekursiven Aufruf auch leer sein kann. Aber ja: Das ist der Ablauf bei Rekursion und etwas wie:
Eine Schleife
-> Rufe etwas auf.
ist keine Rekursion, da hier dieses "sich selbst immer wieder aufrufen" fehlt. Das ist ja eben der Unterschied. Dieser Rekursive Aufruf ist unter dem Strich eine Schleife.

Du kannst gerne einmal Dein Ergebnis zeigen. Wenn Du das auch abgeben musst und die Plagiats-Prüfung ggf. umgehen musst, dann kannst Du es auch gerne direkt als PM an mich schicken. Dann würde ich (so du das möchtest) noch einmal schauen, ob Du das mit der Rekursion richtig hast oder nicht.

 

[Martina1909]

Danke für die Erklärungen, ich denke, ich hab schon alles, was ich brauche... Hat nur ein wenig länger gedauert, danke für die Geduld!