Python Josephus

Neue Frage »

Auf diesen Beitrag antworten »
Dr.Java 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
 
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

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.
 
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

Das -1 ist, um keine zu große Schrittweite zu haben.
Das Modulo sorgt gerade dafür, dass es wieder von vorne losgeht.
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

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).
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
Dr.Java

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
Auf diesen Beitrag antworten »
eulerscheZahl

Freut mich, dass du es verstanden hast.
Und der Code ist C#, damit bin ich einfach schneller.
Auf diesen Beitrag antworten »
Dr.Java

Zitat:
Freut mich, dass du es verstanden hast.

Ja, hat ja lange genug gedauert, danke nochmal.
C also, die Sprachen sehen für mich noch alle recht ähnlich aus, ich denke mit der Zeit,werde ich dann auch die feinen Unterschiede feststellen können.

lg
Auf diesen Beitrag antworten »
eulerscheZahl

Nein, nicht C. C# (sprich: C Sharp).
Das ist Microsofts Reaktion auf einen Rechtsstreit mit Sun Microsystems (Java).
Zumindest Consolenanwendungen laufen aber auch unter Linux.

Von der Syntax her ähnlich zu Java. Python sieht doch ziemlich verschieden aus.
Auf diesen Beitrag antworten »
Dr.Java

Ach das soll ein anderes Programm sein, wieder was gelernt. Ok, anders als Python ,wohl schon wegen den geschweiften Klammern und dem using statt import(?),aber ansonsten gibt es ,zumindest beim ersten Blick,einige Parallelen,beim näheren hinschauen bekommt man schon den Verdacht das es eine andere Sprache ist .

lg
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »