Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
--- Python Josephus (http://www.informatikerboard.de/board/thread.php?threadid=3089)


Geschrieben von Dr.Java am 13.06.2016 um 16:48:

  Python Josephus

Hallo. Ich habe so meine Probleme mit dem Josephusproblem(ich hoffe der Sachverhalt ist bekannt).
Folgenden Code konnte ich durch testen und Suchen zusammenfügen
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
def josephus_iter(n, k):
    objects=list(range(1, n+1))
    i=0
    while len(objects)>0:
        i=(i+k-1)% len(objects)
        yield objects[i]
        del objects[i]

def print_josephus_seq(n, k):
    for o in josephus_iter(n, k):
        print(o, end='')
    print()

Funktioniert ,soweit ich weiß richtig.Meine Frage klingt vielleicht etwas sonderbar,aber ich verstehe das erste Programm irgendwie nicht. Ich meine ich verstehe das mit list range und n+1 usw. ,aber bei del und yield bin ich mir nicht so sicher wie das funktioniert und besonders mit der Formel in der vierten Zeile habe ich so meine Probleme. Könnte jemand vielleicht erläutern das man darauf kommt?

Vielen Dank nochmal

lg



Geschrieben von eulerscheZahl am 13.06.2016 um 16:56:

 

i ist die aktuelle Position. Die wird um k-1 erhöht. Die -1 kommt, weil aus der Liste etwas gelöscht werden soll, die Indizes verschieben sich also alle. Um im Kreis zu bleiben, wird dann noch modulo dessen Länge gerechnet.
yield gibt dann die aktuelle Person an den Iterator zurück. del entfernt die Person aus der Liste.

Ich finde es übrigens sehr verwirrend, dass du dich Dr. Java nennst und Fragen zu Python stellst.



Geschrieben von Dr.Java am 13.06.2016 um 17:44:

 

Erneut danke euler. Ich heiße nur so aus mangelnder Kreativität ,mir ist damals auf die schnelle nichts eingefallen und ich wollte keinen zu spezifischen Namen,deshalb Dr. (wie zum Beispiel DrRacket) und eben Java sodass ich jetzt diesen Namen trage. Aber Fragen zu Java werden bestimmt auch noch irgendwann kommen.

Zum Thema

Zitat:
Die -1 kommt, weil aus der Liste etwas gelöscht werden soll

Ist das so eine Regel in Python oder ist das eher was mathematisches?

Zitat:
Um im Kreis zu bleiben, wird dann noch modulo dessen Länge gerechnet.

Ich fürchte ich kann dir nicht ganz folgen.Was meinst du genau mit im Kreis bleiben? Man dividiert doch die Position im Kreis durch die Länge des Objekts(mit Rest) um zu ermitteln welches Element des Objekts entfernt wird,aber warum so, gibt es da eine Formel oder ist das ein logischer Schluss, ich komme einfach nicht dahinter.

Zitat:
yield gibt dann die aktuelle Person an den Iterator zurück. del entfernt die Person aus der Liste.

Und dann wird mit dem neuen objects und dem neuen i der nächste Wert bestimmt ,bis nichts mehr da ist,oder?

lg



Geschrieben von eulerscheZahl am 13.06.2016 um 18:02:

 

Die -1 ist mathematisch:
Wenn du mitten aus einer Liste etwas löschst, verschieben sich die folgenden Indizes.
code:
1:
2:
3:
4:
5:
6:
index: 0 1 2 3 4 5
wert:  1 2 3 4 5 6

del objects[2]
index: 0 1 - 2 3 4
wert:  1 2 3 4 5 6


Zum Kreis:
code:
1:
2:
index: 0 1 2 3 4 5 0 1 2 3 4 5
wert:  1 2 3 4 5 6 1 2 3 4 5 6

Nach Index 5 (Wert 6) käme ohne das Modulo Index 6. Mit Modulo wird sichergestellt, dass du im Bereich 0-5 bleibst. Auch das ist eine mathematische Überlegung.

Zitat:
Und dann wird mit dem neuen objects und dem neuen i der nächste Wert bestimmt ,bis nichts mehr da ist,oder?

Ja.



Geschrieben von Dr.Java am 14.06.2016 um 09:13:

 

Okay danke,ich verstehe das ganze schon mehr.

Zitat:
Die -1 ist mathematisch:

Also ist das nur vorbeugend weil sonst bei der Löschung von objects was verloren gehen würde?Aber das würde doch eigentlich nicht das k sondern das Intervall von objects betreffen?

Zitat:
Zum Kreis:

Ach so, dann sorgt das Modulo dafür das sich das Intervall nicht wiederholt,was es sonst tun würde da es ein Kreis ist?

lg



Geschrieben von eulerscheZahl am 14.06.2016 um 11:32:

 

Das -1 ist, um keine zu große Schrittweite zu haben.
Das Modulo sorgt gerade dafür, dass es wieder von vorne losgeht.



Geschrieben von Dr.Java am 14.06.2016 um 17:45:

 

Zitat:
Das -1 ist, um keine zu große Schrittweite zu haben.

Okay, und dafür sorgt man also indem man bei k eins abzieht.Aber warum betrifft das k ,sollte und müsste man das nicht bei objects machen?

Zitat:
Das Modulo sorgt gerade dafür, dass es wieder von vorne losgeht.

Das Modulo ist also da um zu sorgen das das Intervall und der Index sich wiederholen. Weil ansonsten die Rechnung über das Intervall hinaus gehen würde?

lg



Geschrieben von eulerscheZahl am 15.06.2016 um 07:30:

 

Aus k ergibt sich ja der Index dessen, was als nächstes gelöscht wird. Die -1 verringert diesen Index.
Zitat:
Ach so, dann sorgt das Modulo dafür das sich das Intervall nicht wiederholt,was es sonst tun würde da es ein Kreis ist?

Durch das Modulo geht es wieder von vorne los. Ohne würden die Zahlen immer größer werden, sodass der Index irgendwann außerhalb des Kreises liegt und es keine zweite Runde gibt.



Geschrieben von Dr.Java am 15.06.2016 um 18:48:

 

Zitat:
Aus k ergibt sich ja der Index dessen, was als nächstes gelöscht wird. Die -1 verringert diesen Index.

Ah,das klingt natürlich einleuchtend.

Zitat:
Durch das Modulo geht es wieder von vorne los. Ohne würden die Zahlen immer größer werden, sodass der Index irgendwann außerhalb des Kreises liegt und es keine zweite Runde gibt.

Das ganze lässt also den Index iterieren,und du meintest ja das ganze würde auf mathematischen Überlegungen beruhen, was wären diese denn ganz konkret?

lg



Geschrieben von eulerscheZahl am 15.06.2016 um 18:50:

 

Lass' das modulo doch einfach weg und gib i aus. Dann siehst du, was ich meine (das yield und del solltest du dann auch rausnehmen).



Geschrieben von Dr.Java am 15.06.2016 um 19:37:

 

Einfach beim Programm das Modulo ,die yield und del Zeile streichen?

Also so ?
code:
1:
2:
3:
4:
5:
6:
7:
def josephus_iter(n, k):
    objects=list(range(1, n+1))
    i=0
    while len(objects)>0:
        i=(i+k-1) 
        return i  

Dann gibt er mir nur eine Zahl aus,2. Die seq Funktion funktioniert dann aber überhaupt nicht mehr .Falls du das ganze auch ohne return meintest, das funktioniert bei mir nicht,die Shell friert dann nur ein. Und mit yield und del gibt seq_josephus mir nur ne Fehlermeldung aus.

lg



Geschrieben von eulerscheZahl am 15.06.2016 um 20:08:

 

Du sollst ja auch print schreiben und nicht return.
Du wirst eine Fülle von Zahlen bekommen. Du sollst einfach nur sehen, dass sie außerhalb des Arraybereichs liegen.



Geschrieben von Dr.Java am 16.06.2016 um 10:15:

 

Oh, ich sehs. Das passiert also wenn man das ganze ohne modulo rechnet. Entschuldige,wenn ich mich etwas blöd anstelle, aber was ist die mathematische Logik dahinter, ich meine das ist ja jetzt nur wie sich das ganze in Python verhält und auswirkt.

lg



Geschrieben von eulerscheZahl am 16.06.2016 um 10:51:

 

Ich kann nicht glauben, dass ich das gerade tue:

Code zum Bilder erzeugen:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
using System;
using System.Linq;
using System.IO;
using System.Diagnostics;
using System.Text;
using System.IO.Compression;
using System.Collections.Generic;
using System.Drawing;

public class MainClass
{
	public static void Main (string[] args)
	{
		int n = 8;
		List<int> objects = Enumerable.Range (1, n).ToList ();
		int i = 0;
		int k = 3;
		int image = 0;
		while (objects.Count > 0) {
			i = (i + k - 1);
			Draw (objects, i, image++, n);
			if (i >= objects.Count) {
				i %= objects.Count;
				Draw (objects, i, image++, n);
			}
			objects.RemoveAt (i);
			Draw (objects, i, image++, n);
		}
	}

	public static void Draw(List<int> numbers, int index, int id, int max) {
		Font font = new Font ("Lucida Console", 16);
		Bitmap bmp = new Bitmap (200, 300);
		Graphics g = Graphics.FromImage (bmp);
		g.Clear (Color.White);
		for (int i = 0; i < numbers.Count; i++) {
			double x = 100 + 70 * Math.Cos (2 * Math.PI * numbers[i] / max);
			double y = 100 + 70 * Math.Sin (2 * Math.PI * numbers[i] / max);
			g.FillEllipse (i == index ? Brushes.Green : Brushes.Gray, new RectangleF ((float)x - 20, (float)y - 20, 40, 40));
			g.DrawString (numbers[i].ToString (), font, Brushes.Black, new RectangleF ((float)x - 10, (float)y - 10, 40, 40));
		}
		g.FillEllipse (Brushes.Green, new RectangleF (5 + index * 20, 220, 30, 30));
		g.DrawString (string.Join(" ", numbers), font, Brushes.Black, new RectangleF (10, 220, 180, 40));

		g.DrawString ("i = " + index, font, Brushes.Black, new RectangleF (10, 270, 180, 40));
		bmp.Save ("image" + id.ToString("00") + ".png");
		g.Dispose ();
		bmp.Dispose ();
				font.Dispose();
	}
}


Bild (animiert, musst du anklicken):
Oben siehst du den Kreis, unten die Liste, wie sie im Speicher steht. Wie du siehst, kommt man aus der Liste heraus und muss sich zurücksetzen.



Geschrieben von Dr.Java am 16.06.2016 um 13:02:

 

Vielen lieben Dank für deine Bemühungen. Ist das ein Python Code?
Ich kann den Ablauf des Programms inzwischen vollkommen nachvollziehen .Und ich denke ich verstehe jetzt auch das mit dem Modulo,im nachhinein betrachtet hatte ich wohl ein Brett vorm Kopf .
Vielen Dank nochmal für deine Geduld und Mühen.

lg


Forensoftware: Burning Board, entwickelt von WoltLab GmbH