Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Python Josephus » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Seiten (2): [1] 2 nächste » Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Python Josephus
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Python Josephus Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Zitat:
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson

14.06.2016 09:13 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Syntax Highlighting fürs Board (Link)
14.06.2016 11:32 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Zitat:
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Dr.Java: 14.06.2016 18:00.

14.06.2016 17:45 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:
image.gif



__________________
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 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Dr.Java Dr.Java ist männlich
Foren As


images/avatars/avatar-71.jpg

Dabei seit: 21.03.2016
Beiträge: 99

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 Dr.Java ist offline Beiträge von Dr.Java suchen Nehmen Sie Dr.Java in Ihre Freundesliste auf
Seiten (2): [1] 2 nächste » Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Python Josephus