VB.NET Josephus Problem, blutiger Anfänger

exc-jdbi · 5. Dezember 2020, 17:15

Beim 11-er gehe ich genau so vor wie beim 4-er.

Habs jetzt oben hingeschrieben. Kann es auch hier nochmals schreiben.

n = 11, k = 7. Der Index 6 (0-basieren) bekommt die Personenzahl 1, der Index 2 (Position 13 % 11 = 2) bekommt die Personennummer 2 , die nächste Position wäre 21, das ist der Index 10 mit Personennummer 3 etc.

Position 17 (17 % 11 = Index 6) wird übersprungen, da schon besetzt.

VaporiZed · 5. Dezember 2020, 17:24

Gut, ob man jetzt immer dieselbe Liste hernimmt oder 2 (wie ich, siehe Post#37) kann man ja machen wie man will. Kommt eben drauf an, was man für die weitere Handhabung (Berechnung/Auflistung) einfacher findet.

exc-jdbi · 5. Dezember 2020, 17:32

Ich habe bei meinem Algo den Iter einfach immer weiter zählen lassen. Das macht schlussendlich den Algo zwar ein bisschen langsamer, aber ich finde ist genau so wirksam. Wie die Zahlen schlussendlich daher kommen, habe ich bis jetzt auf keiner Tabelle im Netzt gefunden.

Ich denke wenn's Schlussendlich mit der Permutation (egal in welcher Reihenfolge) klappt, ist es sicher eine Lösung für das Josephius-Problem.

Ich habe meine mit der auf Wiki beschriebenen Methode gegeneinander ausgespielt. Der Endwert ist immer identisch.

nogood · 5. Dezember 2020, 18:51

Hier doch noch eine Änderung. Beim Konvertieren von C# zu VB hatten sich ein paar Zeilen Eingeschlichen die nicht nötig sind. Oder es geht doch noch kürzer u. einfacher 41 Zeilen übrig:

Spoiler anzeigen

VB.NET-Quellcode

Module Module1
'Klasse Person
Public Class Person
Public Property Id As Integer
Public Sub New(nr As Integer)
Id = nr
End Sub
End Class
'Hauptprogramm
Private NochStehendePersonen As List(Of Person) = New List(Of Person)()
Sub Main()
For i As Integer = 1 To 1000
NochStehendePersonen.Add(New Person(i))
Next
Console.WriteLine("1000 Personen stehen im Kreis jeder siebte setzt sich hin bis nur noch drei stehen:")
Play(NochStehendePersonen)
Console.WriteLine("Es stehen zum Schluss noch Position:")
For Each p As Person In NochStehendePersonen
Console.WriteLine(p.Id)
Next
Console.ReadLine()
End Sub
'Methode Play
Private CounterStehender As Integer = 0
Private Sub Play(ByVal personen As List(Of Person))
If personen.Count() <= 3 Then
Return
End If
NochStehendePersonen = New List(Of Person)()
For Each p As Person In personen
CounterStehender += 1
If CounterStehender <> 7 Then
NochStehendePersonen.Add(p)
End If
If CounterStehender = 7 Then
CounterStehender = 0
End If
Next
Play(NochStehendePersonen)
End Sub
End Module

Benutzername · 5. Dezember 2020, 19:12

nogood schrieb:

@Benutzername Ich kann mich noch zu gut an die Zeit erinnern. Hier heute mal ein Freilos (vorausgesetzt, dass meine Lösung stimmt)!

Visual Studio neues Consolen Vb.net App Framework Projekt erstellen und Copy Paste

Spoiler anzeigen

VB.NET-Quellcode

Module Module1

'//Bauplan Person mit nur einer Eigenschaft jede Person hat seine "Sitz/Stehplatznummer"

Public Class Person

Public Property Id As Integer

Public Sub New(nr As Integer)

Id = nr

End Sub

End Class

'//^^^Bauplan Person Ende

'//Hauptprogramm

'//Liste mit dem Namen "Personen" die Person-Objekte enthält wird reserviert

'//Konvention ist die Liste im Plural der enthaltenden Ojekte zu benennen

'// Also Personen = Liste of Person

Public Personen As List(Of Person) = New List(Of Person)()

Sub Main()

'//Erzeugung der Liste Personen = (Person(Id=1), Person(Id=2), ... Person(Id=1000))

For i As Integer = 1 To 1000

Personen.Add(New Person(i))

Next

Console.WriteLine("1000 Personen stehen im Kreis jeder siebte setzt sich hin bis nur noch drei stehen:")

'//erster Aufruf von Play mit der Liste der 1000 Personen

Play(Personen)

'//Ergebnis Darstellung in der ehemals 1000 Personen Liste stehen nur noch 3 drin

Console.WriteLine("Es stehen zum Schluss noch Position:")

For Each p As Person In NochStehendePersonen

Console.WriteLine(p.Id)

Next

Console.ReadLine()

End Sub

'//^^^Hauptprogramm Ende

'//Play Methode (o. auch Funktion genannt) die die "echte Arbeit" macht und die Position findet

Private CounterStehender As Integer = 0

Private NochStehendePersonen As List(Of Person) = New List(Of Person)()

Private Sub Play(ByVal personen As List(Of Person))

'//Abbruch Kriterium

If personen.Count() <= 3 Then

'//Übergabe der Liste der Stehenden Personen nach "außerhalt" der Play Methode

'//falls da dann nur 3 drin stehen wird die Play Methode ja abgebrochen

personen = New List(Of Person)()

personen.AddRange(NochStehendePersonen)

Return

End If

'//Neue Liste der jetzt noch stehenden Personen wieder bei null anfangen

NochStehendePersonen = New List(Of Person)()

'//jeder 7 setzt sich hin

For Each p As Person In personen

CounterStehender += 1

If CounterStehender <> 7 Then

NochStehendePersonen.Add(p)

End If

If CounterStehender = 7 Then

CounterStehender = 0

End If

Next

'//Rekursion: die Methode Play wird jetzt mit dieser Liste(PersonenDieNochStehen) neu aufgerufen bis

Play(NochStehendePersonen)

End Sub

'//^^^Play Ende

End Module

webspace.ship.edu/deensley/mathdl/Joseph.html

Das ist beeindruckend. Danke auch für die Kommentare dazu.

Wie ist denn folgender Code zu bewerten? Das ist noch etwas, was ich online gefunden habe und auch ungefähr meinem bisherigen Verständnis entspricht/entsprechen sollte. Quelle des Codes
Hierbei ist auch wieder das altbekannte Josephus-Problem zu lösen allerdings nicht wie in meiner Aufgabenstellung mit 1000 Personen/jede 7. Person.

Anhand der bisherigen zwei Seiten Skript über Enumerationen bzw. zwei Seiten über Listen, kann ich den Code leider nicht entziffern. Woher weiß denn das Programm, um wie viele Personen es insgesamt geht bzw. wie groß der Abstand zwischendrin ist?
Besteht zwischen Zeile 4 und Zeile 17 bzw. 19 ein Zusammenhang? Wieder möglicherweise falsch ausgedrückt sehe ich, dass in Zeile 4 in Sub Josephus drei Variablen (n, k, m) in der Klammer stehen bzw. initialisiert wurden und sich in Zeile 17 bzw 19 ebenfalls 3 Zahlen in der Klammer befinden.

VB.NET-Quellcode

Module Module1
'Determines the killing order numbering prisoners 1 to n
Sub Josephus(n As Integer, k As Integer, m As Integer)
Dim p = Enumerable.Range(1, n).ToList()
Dim i = 0 Console.Write("Prisoner killing order:")
While p.Count > 1 i = (i + k - 1) Mod p.Count
Console.Write(" {0}", p(i))
p.RemoveAt(i)
End While
Console.WriteLine()
Console.WriteLine("Survivor: {0}", p(0))
End Sub
Sub Main()
Josephus(5, 2, 1)
Console.WriteLine()
Josephus(41, 3, 1)
End Sub
End Module

Edit: mittlerweile habe ich durch ausprobieren herausgefunden, dass Zeile 17 bzw. 19 tatsächlich die Anzahl der Personen und den Abstand untereinander angeben. Was die letzte Ziffer soll, oben als m deklariert, habe ich nicht herausgefunden, da mir die Software auch sagt "IDE0060 Remove unused parameter 'm' " in zeile 4

RodFromGermany · 5. Dezember 2020, 19:23

Ich hab das ganze mal als reine Index-Rechnung formuliert:

VB.NET-Quellcode

Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
' Werte von WiKi
Dim Anzahl = 41
Dim Modulo = 3
Dim Rest = 2
If True Then
' Werte vom Forum
Anzahl = 1000
Modulo = 7
Rest = 3
End If
Dim ll = Josephus(Anzahl, Modulo, Rest)
For i = 0 To ll.Count - 1
ListBox1.Items.Add(ll(i))
Next
End Sub
Private Function Josephus(Anzahl As Integer, Modulo As Integer, Rest As Integer) As List(Of Integer)
Dim ll = New List(Of Integer)
' Aufstellen der Delinquenten
For i = 1 To Anzahl
ll.Add(i)
Next
Dim index = 0
For i = Anzahl To Rest + 1 Step -1
index += Modulo - 1 ' Korrektur für das herausgenommene Element
While index >= i ' Index-Begrenzung
index -= i
End While
ll.RemoveAt(index) ' Sä sollen säch sätzen
Next
Return ll
End Function
End Class

ErfinderDesRades · 5. Dezember 2020, 19:32

@nogood: Ich denke, eine Schleife wäre hier besser als eine (End-) Rekursion.
Bei dir wird ja für jeden Durchlauf eine neue List(Of Person) gebildet, mit zwischen 3 und 1000 Elementen. Diese Listen werden alle im Speicher festgehalten, während sich die Rekursion immer weiter vertieft.
Bei 1 Mio Elementen könnte das ungemütlich werden - stell ich mir vor.
Auch geht bei 1Mio Elementen der Rekursions-Stack ziemlich hoch - kann ich nicht ausrechnen. Jedenfalls mit jeder Runde wird die Elemente-Zahl ja um 1/7 verringert - weiss nicht, wieviele Runden das bei 1Mio ergibt.
Jedenfalls pro Runde ein Selbst-Aufruf, also Erhöhung des Rekursions-Stacks.
Ich weiss nicht, wie gross der werden kann, aber iwann gibts den berühmten StackOverflow.

In einer Schleife hingegen würden die nicht mehr gebrauchten Listen automatisch weggeworfen, wenn eine neue Liste an dieselbe Variable zugewiesen wird.

nogood · 5. Dezember 2020, 22:15

@Benutzername Gib mal eine Rückmeldung, egal welchen Code Du genommen hast ob Du ihn bei dir so zum laufen bekommst, dass alles i.O. ?
Geht jetzt die Diskussion eher ums Verstehen oder kämpfst Du "immer noch" mit VS etc.

@Benutzername ich bin hier eher auch neu! Hör lieber auf @VaporiZed @ErfinderDesRades @RodFromGermany und alle anderen mit deutlich mehr wissen als ich.

@ErfinderDesRades Ist das wirklich der Fall, dass die Listen immer noch im Stack gehalten werden? Gebraucht werden Sie nicht mehr. Es ist ein Loop das sich mit einer "neuen" Liste selbst aufruft. Die alte Liste wird in dem Moment des Rücksprunges nicht mehr benötigt.

Liste (1000) rein -> neue Liste mit 850 noch stehenden Personen entsteht -> jetzt erfolgt der Aufruf der selben Funktion eben mit dieser Liste. Die Liste mir 1000 kann/ist weg.
NochStehendePersonen = New List(Of Person)() steht in der Methode drin und diese Liste wird wieder und wieder neu gefüllt mit immer weniger Personen und zum aufrufen der Methode benutzt.
(Eventuell ist de Begriff Rekursion falsch, aber da fehlt mir das theoretische Wissen; Rekursion ist bei mir im Moment so def. das eine Methode sich immer wieder selbst aufruft. In diesem Fall ist es aber nicht, so dass immer ein neues genestetes Loop im Loop im Loop ... entsteht)

---------------------
Deine Meinung hat natürlich Gewicht für mich.

Ich bin immer noch eher froh wenn mein Code endlich fehlerfrei kompiliert und das rauskommt was ich erwarte ... mehr Wissen hab ich nicht (Lebensdauer Speicher Stack garbge collector etc. Value vs Ref muss ich noch immer mal wieder nachsehen).

Ich hatte ja 1 Mio Personen probiert in Post 25 steht die Zeit. Eben auch noch mal für 10 Mio. probiert ging in ca 2 Sek. (aber mit dem orig. C# Code der ganz ein bissel anders ist).

ErfinderDesRades · 5. Dezember 2020, 23:01

nee - du hast recht - die Listen werden entsorgt. NochStehendePersonen wird ja nicht lokal erstellt in der Play()-Methode, sondern NochStehendePersonen ist eine Modul-Variable, und wird somit in post#44, zeile#29 immer überschrieben (wodurch die vorherige dem GC anheimfällt).

Eine Rekursion ists aber dennoch, deine def. davon ist richtig: Die Methode ruft sich selbst auf.
EndRekursion ists deshalb, weil der Selbst-Aufruf ganz am Ende steht, bevor die Methode returnt.

EndRekursion braucht man eiglich nur in Sprachen, die keine Schleifen kennen, wie glaub f# - habich mal gehört.
Eine EndRekursion ist relativ einfach in eine SchleifenForm zu transformieren:

VB.NET-Quellcode

'aus
Private Sub Play(ByVal personen As List(Of Person))
If personen.Count() <= 3 Then
Return
End If
NochStehendePersonen = New List(Of Person)()
For Each p As Person In personen
CounterStehender += 1
If CounterStehender <> 7 Then
NochStehendePersonen.Add(p)
End If
If CounterStehender = 7 Then
CounterStehender = 0
End If
Next
Play(NochStehendePersonen)
End Sub
'wird
Private Sub Play(ByVal personen As List(Of Person))
Do
If personen.Count() <= 3 Then
Return
End If
NochStehendePersonen = New List(Of Person)()
For Each p As Person In personen
CounterStehender += 1
If CounterStehender <> 7 Then
NochStehendePersonen.Add(p)
End If
If CounterStehender = 7 Then
CounterStehender = 0
End If
Next
personen = NochStehendePersonen
Loop
End Sub
'daraus wiederum könnte werden:
Private Sub Play(ByVal kandidaten As List(Of Person))
Do
If kandidaten.Count() <= 3 Then Return
NochStehendePersonen = New List(Of Person)()
For Each p As Person In kandidaten
CounterStehender += 1
If CounterStehender < 7 Then NochStehendePersonen.Add(p) Else CounterStehender = 0
Next
kandidaten = NochStehendePersonen
Loop
End Sub

Benutzername · 6. Dezember 2020, 13:29

@nogood
Deinen überarbeiteten Code aus Beitrag Nr. 44 kann ich nachvollziehen, da sich dieser - was die verwendeten Befehle angeht - ungefähr auf meinem bisherigen Kenntnisstand befindet. Zumindest was das Verständnis angeht. Das ganze eigenständig Programmieren, da muss ich nach wie vor passen. Vielleicht schaue ich ja in 3-4 Wochen nochmal zurück und werfe mit Codes nur so um mich.
Also long story short, ich kämpfe immer noch

Aber ich werde wohl vom guten Josephus erstmal Abstand nehmen. Ich habe aber die Befürchtung, dass ich mich in den kommenden Tagen nochmals hier im Forum melden werde mit weiteren Verständnisproblemen...

Edit: falls es doch Mitleser aus meinem Kurs hier gibt, denkt daran, dass identische Abgaben gleich rausfliegen also versucht es erst gar nicht

exc-jdbi · 6. Dezember 2020, 21:48

Ich bin mir sicher, das es eine wenn auch vielleicht kleinere Gemeinschaft gibt, die immer gerne solche Aufgaben löst.

Also jederzeit melden, wenn es dir danach ist.

Hier ist noch meiner den ich gemacht habe. Ich weiss zwar nicht wie schnell der ist, aber vielleicht habe ich glück und der Algo kommt auch an solche Werte wie die von @nogood.

Ist in der Konsole gemacht, und sollte genau das machen, was er muss. Ich hoffe die Zahlen stimmen, da der Vergleich ein bisschen fehlt.

SpecialPermutation

C#-Quellcode

using System;
using System.Linq;
using System.Diagnostics;
namespace JosephusCs
{
class Program00
{
public static void Main()
{
int k = 7;
int count = 3;
int n = 10_000_000;
Console.WriteLine($"n = {n}, k = {k}, cnt = {count}");
//Ähnlich aber nicht Josephus
SpecialPerm(n, k);
Console.ReadLine();
}
private static void SpecialPerm(int n, int k)
{
var sw = Stopwatch.StartNew();
var result = SpecialPermutation(n, k);
Console.WriteLine($"t = {sw.ElapsedMilliseconds} ms");
Console.WriteLine();
Enumerable.Range(0, result.Length).ToList()
.ForEach(x => Console.Write($"{result[x]} "));
Console.WriteLine();
}
private static int[] SpecialPermutation(int n, int k)
{
int it = 1;
int persnr = k;
if (n <= 1) return new[] { n };
// Bei dieser Variante wird der Sitzende mitgezählt, und die
// Array wird wiederum zirkular duchlaufen.
// Wenn z.B. Personenanzahl n = 1000 und der k = 7 teilerfremd
// zueinander sind, dann werden immer alle Teilnehmer sich setzen.
// In diesem speziellen Fall, Resultat = 0 bzw. alle Personen im
// Kreis sitzen.
// Wenn sie nicht teilerfremd sind, wird irgendwann ein
// Sitzender nochmals gebeten zu sitzen, nur das geht nicht
// mehr, also wird abgebrochen. Resultat >= 0
// Ist ein sehr wichtiger Algorithmus um z.B. die Schlüsseldurchläufe
// in der Kroyptographie zu verändern. D.h. Statt den Schlüssel
// iterativ mit Step = 1 zu durchlaufen, wird ein Step > 1 hinzugefügt.
// Bei Rückläufen sind die Step-Werte dann einfach kleiner 0.
// Es werde natürlich nur Werte verwendet die teilerfremd zueinander sind,
// damit der Schlüssel immer vollkommen durchlaufen werden kann.
// Dieser Algo entspricht auch einer Permutation, denn es werden bei
// Teilerfremdheit alle Plätze in eine andere Anordnung gebracht.
// (Plätze werden vertauscht wie bei einer Transposition)
var place = new int[n];
while (true)
{
if (place[(persnr - 1) % place.Length] != 0 || it > place.Length)
break;
place[(persnr - 1) % place.Length] = it;
it += 1;
persnr += k;
}
if (it > place.Length) return place;
// Ist 0-basierend darum korrekter Wert >> Index (i) + 1
return place.Select((x, i) => x == 0 ? i + 1 : -1)
.Where(i => i != -1).ToArray();
}
}
}

Josephus Iterativ

C#-Quellcode

using System;
using System.Linq;
using System.Diagnostics;
namespace JosephusCs
{
public class Program01
{
public static void Main()
{
int k = 7;
int count = 3; //Wenn 0 >> Ganzer Kreis ausgeben
int n = 1_000_000;
if (count == 0 && n > 20)
n = 20;
Console.WriteLine($"n = {n}, k = {k}, cnt = {count}");
var sw = Stopwatch.StartNew();
var result = JosephusIterativ(n, k, count);
Console.WriteLine($"t = {sw.ElapsedMilliseconds} ms");
Console.WriteLine();
Enumerable.Range(0, result.Length).ToList()
.ForEach(x => Console.Write($"{result[x]} "));
Console.WriteLine();
Console.ReadLine();
}
private static int[] JosephusIterativ(int n, int k, int cnt)
{
if (n < 2) return new[] { n };
//Kleiner Nachteil: Bei grossen k-Werten, wird wiederum
//immer wieder durch alle Teilnehmer iteriert, was den Algo
//quasi nicht zum Abschluss bringen möchte. Daher hier eine
//Performenceeinbusse.
var it = 0;
var kiter = k;
var setter = 0;
var iteration = (k - 1) % n;
var place = new int[n];
var result = new int[cnt];
while (true)
{
if (setter >= n) //Abbruchbedingung
break;
if (kiter == k && place[iteration] == 0)
{
setter += 1;
place[iteration] = setter;
if (setter > n - cnt)//Füllen der letzten Werte
result[it++] = iteration + 1;
kiter = 0;
}
if (kiter != 0 && place[iteration] != 0)
kiter -= 1;
kiter += 1;
iteration += 1;
if (iteration == n)
iteration = 0;
}
if (cnt == 0) return place;
return result;
}
}
}

WIKI-Test

C#-Quellcode

using System;
using System.Diagnostics;
namespace JosephusCs
{
class WikiTest00
{
public static void Main()
{
TestWIKI(10, 7, 1000);
TestWIKI_K2(10, 1000);
}
static void TestWIKI(int n, int k, int cnt)
{
for (int i = 0; i < cnt; i++)
{
var r1 = JosephusIterativ(n, k, 1);
var r2 = JosephusWIKI3(n++,k);
Debug.Assert(r1[0] == r2);
}
}
static void TestWIKI_K2(int n, int cnt)
{
var k = 2;
for (int i = 0; i < cnt; i++)
{
var r1 = JosephusIterativ(n, k, 1);
var r2 = JosephusWIKI2(n);
var r3 = JosephusWIKI(n++);
Debug.Assert(r1[0] == r2);
Debug.Assert(r1[0] == r3);
}
}
static int JosephusWIKI(int n)
{
if (n == 1)
return 1;
if ((n % 2) == 0)
return 2 * JosephusWIKI(n / 2) - 1;
if ((n % 2) == 1)
return 2 * JosephusWIKI((n - 1) / 2) + 1;
return default;
}
static int JosephusWIKI2(int n)
{
var m = Math.Floor(Math.Log(n, 2));
var l = n - Math.Pow(2, m);
var j = 2 * l + 1;
return (int)j;
}
static int JosephusWIKI3(int n, int k)
{
if (n <= 1) return n;
return (JosephusWIKI3(n - 1, k) + k - 1) % n + 1;
}
private static int[] JosephusIterativ(int n, int k, int cnt)
{
if (n < 2) return new[] { n };
var it = 0;
var kiter = 0;
var setter = 1;
var iteration = (k - 1) % n;
var place = new int[n];
var result = new int[cnt];
place[iteration] = setter;
while (true)
{
if (setter >= n)
break;
if (kiter == k && place[iteration] == 0)
{
setter += 1;
place[iteration] = setter;
if (setter > n - cnt)
result[it++] = iteration + 1;
kiter = 0;
}
if (kiter != 0 && place[iteration] != 0)
kiter -= 1;
kiter += 1;
iteration += 1;
if (iteration == n)
iteration = 0;
}
if (cnt == 0) return place;
return result;
}
}
}

nogood · 7. Dezember 2020, 10:06

@ErfinderDesRades Ich hab jetzt nochmal Zeit gehabt mir deine Lösung mit dem Do Loop anzusehen. Danke für das teilen! Die LSG ist noch besser

Ich freue mich über den Austausch.

@Benutzername Viel Erfolg mit der HA und ich denke, dass sich einige freuen wenn es neuen Knobelstoff gibt.

VB.NET Josephus Problem, blutiger Anfänger

VB.NET-Quellcode

nogood schrieb:

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

C#-Quellcode

C#-Quellcode

C#-Quellcode

Benutzer online 1

Ähnliche Themen

7 Benutzer haben hier geschrieben