Python Josephus |
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Dr.Java: 13.06.2016 16:52.
|
|
13.06.2016 16:48 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
13.06.2016 16:56 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
13.06.2016 17:44 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
13.06.2016 18:02 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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?
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
14.06.2016 09:13 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.06.2016 07:30 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
15.06.2016 18:48 |
|
|
|
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).
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.06.2016 18:50 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
15.06.2016 19:37 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.06.2016 20:08 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
16.06.2016 10:15 |
|
|
|
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.
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
__________________ Syntax Highlighting fürs Board (Link)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 16.06.2016 10:53.
|
|
16.06.2016 10:51 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
16.06.2016 13:02 |
|
|
|