Josephus-Problem - Programmieraufgaben.ch

Josephus-Problem (Felder)

Es stehen n Personen in einem Kreis. Die Personen sind nummeriert von 1 bis n. Beginnend bei Person Nummer p wird nun jede p-te Person aus dem Kreis entfernt und der Kreis danach sofort wieder geschlossen (jede Person behält dabei ihre anfänglich zugewiesene Nummer).

Geben Sie die Nummern der entfernten Personen in der Reihenfolge an, in der sie entfernt wurden.

Diese Reihenfolge wird Josephus-Permutation genannt.

Als Eingabe Ihres Programmes benötigen Sie lediglich die Zahlen n und p.

4 Kommentare (ansehen)

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (4)

gressly 23. November 2013 21:56
crouser es wurde nicht erwähnt ob nach dem Aufrücken auch die Nummer, die der Person zugewiesen wurde, eins nach unten rutscht durch den Verlust der anderen Person. Bleibt diese Konstant erhällt man ein deutlich anderes Ergebniss, als wenn diese sich ändert. Ich habe die Aufgabe dahingehend abgeändert. Nummerierte Personen behalten hier ihre ursprüngliche Nummern (Wie beim Skirennen oder beim Marathon). Wenn wir es so handhaben, dann ergibt sich auch immer eine Permutation, also eine Vertauschung der Nummern, ohne dass neue Nummern hinzukommen oder verschwinden. Besten Dank für den Hinweis.
BKluszynski 14. März 2012 17:57
the one Solution in "generic" is actually written in abap. There was no select option for this programming language available at the time of this posting. Probably i can correct this later :-).. have fun..
gressly 18. August 2011 22:34
__jn Unter "Verifikation/Checksumme" sollte in der zweiten Zeile meines Erachtens p = 5 stehen. Ja klar, besten Dank für den Hinweis, habe es eben korrigiert. Gruß philipp
__jn 17. August 2011 03:06
Unter "Verifikation/Checksumme" sollte in der zweiten Zeile meines Erachtens p = 5 stehen.

19 Lösung(en) (ansehen)

/* this file is hereby released into the public domain */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
static void put_number(int n)
{
    static int init;
 
    if (init)
        printf(", ");
    else
        init = 1;
 
    printf("%d", n);
}
 
static void josephus(int n, int p)
{
    char *array;
    int i; /* Arrayiterator */
    int v; /* virtuelle Position, d.h. Position im aktuellen Kreis */
    int removed;
 
    if (n < 1 || p < 1) {
        printf("Ungültige Eingabe: n = %d, p = %d\n", n, p);
        exit(EXIT_FAILURE);
    }
 
    array = malloc(n);
    if (!array) {
        printf("Zu wening Arbeitsspeicher (n = %d)\n", n);
        exit(EXIT_FAILURE);
    }
 
    memset(array, 0, n);
 
    v = 1; /* der Erste (Nullte) wird übersprungen */
    for (i = removed = 0; removed < n; ) {
        if (!array[i]) {
            if ((v % p) == 0) {
                array[i] = 1;
                removed++;
                /* +1 um ab Eins zu zählen */
                put_number(i + 1);
            }
            v++;
        }
 
        if (++i == n)
            i = 0;
    }
 
    free(array);
 
    putchar('\n');
}
 
int main(int argc, char **argv)
{
    if (argc == 3)
        josephus(atoi(argv[1]), atoi(argv[2]));
    else
        printf("Aufruf: %s <Anzahl Personen> <Schrittweite>\n", argv[0]);
 
    return EXIT_SUCCESS;
}

Lösung von: Jonathan Neuschäfer (St.-Bernhard-Gymnasium, 47877 Willich)

/**
 * @author Till Hardenbicker
 * @version 1 28. August 2011 mit BlueJ (Java)
 */
public class Josephus
{static int n; static int p;
 static int index=n-1;
 static int[] Kreis;
    
   public Josephus(int anzahl_personen, int ausscheidungsrate)
   {
       n=anzahl_personen;
       p=ausscheidungsrate;
        
       Kreis = new int[n];
       for(int i=0; i<n; i++)
          {Kreis[i]=i+1;}
           
       main();
   }
    
   static int weiter()
   {
       if(index==n-1)
       {index=0;} //wenn wir am Ende des Kreises sind, müssen wir wieder zum Anfang zurückspringen. 
       else{index++;} //sonst gehts normal weiter. 
       if(Kreis[index]==0) //ist die Person ausgeschieden...
         {weiter();} //...gehts nochmal weiter. 
       return Kreis[index]; //jetzt wird die Person "neben" uns zurückgegeben. 
   }
    
   static void main()
   {for(int j=1; j<=n; j++) //insgesamt müssen n personen ausscheiden. 
       {for(int k=1; k<=p; k++) 
           {weiter(); //jedesmal gehen wir p schritte weiter(); im kreis. 
            }
            System.out.println(Kreis[index]);
            Kreis[index]=0; //die person scheidet aus. wird also =0 gesetzt. 
       }
        
   }
}

Lösung von: Till Hardenbicker (St. Angela Gymnasium Wipperfürth)

package ch.programmieraufgaben.josephus;
 
import java.util.Scanner;
 
/**
 * Josephus Problem mit Ausgabe der Josephus Permutation.
 * @author Philipp Gressly (phi@gressly.ch)
 */
public class Josephus {
     
  class Person {
      int    nummer;
      Person next;
  }
     
  public static void main(String[] args) {
    new Josephus().top();
  }
   
  void top() {
      Person startPerson = init(leseInt("Anzahl Personen"));
      eliminiereAlle(startPerson, leseInt("Löschindex (p)"));
  }
   
  /**
   * Erstelle Kreis komplett mit ".next" verlinkt.
   * @return Zeiger auf erste Person (mit Nummer 1)
   */
  Person init(int anzahl) { 
     Person erster = new Person();
     erster.nummer = 1;
     Person letzter = erster;
     for(int i = 2; i <= anzahl; i++) {
         Person neuePerson = new Person();
         neuePerson.nummer = i;
         letzter.next = neuePerson;
         letzter = neuePerson;
     }
     letzter.next = erster;
     return erster;
  }
   
  void eliminiereAlle(Person erste, int p) {
      if(erste.next == erste) {
          System.out.println(erste.nummer); // ende
          return;
      }
      Person prev = erste;
      Person akt = erste;
      for(int i = 1; i <= p-1; i++) {
          prev = akt;
          akt = akt.next;
      }
      System.out.println(akt.nummer);
      prev.next = akt.next; //Eliminationsschritt
      eliminiereAlle(akt.next, p);
  }
   
  Scanner sc = new Scanner(System.in);
  int leseInt(String frage) {
      System.out.println(frage + ": ");
      return sc.nextInt();
  }
   
}  // end of class Josephus

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

def josephus(n,p)
  da = Array.new(n, true)   # Wer ist noch da (0-basiert)
  raus = []                 # Reihenfolge wer raus ist
  position = n-1;           # Startposition (damit p-1 zuerst raus muss).
  n.times {                 # n-Mal
    p.times {               # p Positionen vorrücken
      begin
        position = (position + 1) % n
      end until da[position]  # vorrücken, bis die Person noch da ist
    }
    raus.push(position)     # Position merken
    da[position] = false    # Person rausschmeissen
  }
  return raus.map{|i| i+1}  # Indizies um 1 erhöhen
end
 
 
print "n = "
n = gets.to_i               # n einlesen
 
print "p = "
p = gets.to_i               # p einlesen
 
puts josephus(n,p).join(",")   # Lösung ausgeben

Lösung von: Ivo Blöchliger (Kantonsschule Wohlen)

# Und jetzt noch wirklich quick & dirty ;-)
 
print "n = "
n = gets.to_i               # n einlesen
 
print "p = "
p = gets.to_i               # p einlesen
 
personen = (1..n).to_a      # [1,2,3, ... ,n]
 
position = 0;               # Position für Rauswurf
raus = [];
 
n.times {            #  \/ -1 weil die Position auf der fehlenden Person ist
  position = (position+p-1) % personen.size   # Vorrücken 
  raus.push(personen.delete_at(position));    # Rauswerfen
}
 
puts raus.join(", ")   # Lösung ausgeben

Lösung von: Ivo Blöchliger (Kantonsschule Wohlen)

*&---------------------------------------------------------------------*
*& Report  Z_JOSEPHUS_PROB
*&
*&---------------------------------------------------------------------*
*& !!! PROGRAMMING LANGUAGE IS ABAP !!! 
*& PROGRAMMER: Benjamin Kluszynski
*&---------------------------------------------------------------------*

REPORT  z_josephus_prob.

PARAMETERS: l_m TYPE i, "amount of people in the circle
            l_n TYPE i. "step to kill them .. :-)


DATA: gt_input TYPE STANDARD TABLE OF i,
      gl_input LIKE LINE OF gt_input,
      gt_already_dead TYPE STANDARD TABLE OF I,
      gl_already_dead LIKE LINE OF gt_already_dead,
      l_already_dead_amount TYPE I,
      l_table_count TYPE I,
      l_relevant_count TYPE I.

"initialize table
DO l_m TIMES.
gl_input = l_m.
APPEND l_m TO gt_input.
ENDDO.

WHILE l_already_dead_amount < l_m. " until all people are dead

WHILE l_relevant_count < l_n. " until the next l_n of relevant person are found

ADD 1 TO l_table_count. " go ahead

IF l_table_count GT l_m. " if the end of array is reached.. go to index 1 again
  l_table_count = 1.
ENDIF.

"look if its already "dead"
READ TABLE gt_already_dead WITH TABLE KEY table_line = l_table_count INTO gl_already_dead.

"if not, then this one is relevant for counting
IF gl_already_dead IS INITIAL.

  ADD 1 TO l_relevant_count.

ENDIF.

CLEAR gl_already_dead.

ENDWHILE.

"save this one to the already murdered ones.. :-)
gl_already_dead = l_table_count.
APPEND gl_already_dead to gt_already_dead.
WRITE: / gl_already_dead, ' is dead now.'.
l_relevant_count = 0.
ADD 1 TO l_already_dead_amount.

CLEAR gl_already_dead.

ENDWHILE.

Lösung von: Benjamin Kluszynski (( Coder :-) ))

// Autor:               Andy Großhennig
// Solution for task:   Josephus-Problem (Felder)
 
#include <iostream>
 
using namespace std;
 
// Function: Get the size of the circle and the selection of people
void getNumbers(int i_arrCircleSize[2], int &iMultiplier)
{
    cout << "Wieviel Personen stehen im Kreis? ";
    cin >> i_arrCircleSize[0];
    cout << "\nJede wievielte Person wird entfernt? ";
    cin >> iMultiplier;
    cout << "\n\n";
 
    i_arrCircleSize[1] = i_arrCircleSize[0];
}
 
// Function: Simulates the circle and the decrease of the selection
void circle()
{
    int i_arrCircleSize[2]; //1: Original size, 2: Current size
    int iMultiplier; //Selection of people
 
    getNumbers(i_arrCircleSize, iMultiplier);
     
    // Loop: Repeat the decrease until the last people is removed
    while(i_arrCircleSize[1] >= iMultiplier)
    {
        i_arrCircleSize[1] -= iMultiplier; //Remove the next people
        cout << (i_arrCircleSize[0] - i_arrCircleSize[1]) << endl; //Show the current removed people
    }   
}
 
int main()
{
    circle();
 
    cout << "\n\n";
    system("Pause");
    return 0;
}

Lösung von: Andy Großhennig (Bundeswehr)

k = 2
n = 4
//Alle Personen im Kreis, true = lebt, false = tot
kreis = [true] * n
println kreis
pos = -1
anzFalse = 0
while (anzFalse < n) {
    for (int counter = 0; counter < k; counter++) {
      pos = pos + 1
        //wenn die nächsten schon tot sind, werden sie übersprungen
        while (!kreis [pos.mod(n)]) {
          pos = pos + 1
        }
        if (counter == k - 1) {
          kreis[pos.mod(n)] = false
          anzFalse = anzFalse + 1
            //das ist der Letzte
            if (anzFalse == n) {
                println ((pos.mod(n) + 1) + " überlebt")    
            } else {
                println ((pos.mod(n) + 1) + " ist tot")
            }
        }
    }
}

Lösung von: Silvia Rothen (rothen ecotronics)

function josephus2(n,k: byte): integer;
  var r,i: integer;
  begin
  r:= 0; i:= 2;
  while i <= n do begin
    r:= (r+k) mod i;
    inc(i)
  end;  
  result:= r+1
 end; 
  
 
 
//As a recursion!:
 
function josephus_rec(n,k: byte): integer;
  begin
  if n = 1 then
    result:= 1
  else
    result:= (josephus_rec(n-1,k) +k-1) mod n+1
  end;

Lösung von: Max Kleiner (BFH)

// shows circel rounds as lines, '1' survived, 'X' is dead
// http://www.softwareschule.ch 
//
procedure josephusProblem_Graphic(n,k: integer);
var i,p,kt: smallint;
    aist: array of char;
begin
   SetArrayLength(aist,n);
   kt:= 2; //or k
   p:= 0;
   for i:= 0 to length(aist)-1 do aist[i]:= '1'; //init array
   while kt <= length(aist) do begin  
     for i:= 0 to length(aist)-1 do begin
       if aist[i]= '1' then inc(p);
       if p = k then begin
         aist[i]:= 'X';
         inc(kt);
         p:= 0;
       end;
     end;
     for i:= 0 to length(aist)-1 do  //line out
       write(aist[i]+ ' ');
     writeln('');
   end;
   for i:= 0 to length(aist) -1 do  //solution out
     if aist[i]= '1' then writeln('Sol '+inttoStr(i+1));
 end;
 
 
call:
josephusProblem_Graphic(41,3);
 
output:
1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1 X 1 1
X 1 X 1 X X 1 1 X X 1 X 1 X X 1 1 X X 1 X 1 X X 1 1 X X 1 X 1 X X 1 1 X X 1 X 1 X 
X 1 X 1 X X X 1 X X 1 X X X X 1 1 X X X X 1 X X 1 X X X 1 X 1 X X X 1 X X 1 X X X 
X 1 X 1 X X X X X X 1 X X X X 1 X X X X X 1 X X 1 X X X X X 1 X X X 1 X X X X X X 
X 1 X 1 X X X X X X X X X X X 1 X X X X X 1 X X X X X X X X 1 X X X 1 X X X X X X 
X X X 1 X X X X X X X X X X X 1 X X X X X X X X X X X X X X 1 X X X 1 X X X X X X 
X X X X X X X X X X X X X X X 1 X X X X X X X X X X X X X X 1 X X X X X X X X X X 
X X X X X X X X X X X X X X X 1 X X X X X X X X X X X X X X 1 X X X X X X X X X X 
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 1 X X X X X X X X X X 
Sol 31

Lösung von: Max Kleiner (BFH)

import java.util.Scanner;
 
public class josephusproblem {
 
    // Führt die Mutation aus
    private String permutation(int n, int p) {
     
    // Beinhaltet am Ende der Methode das Ergebniss
    String ausgabe = "";
     
    // pickt die Nummern der Personen heraus
    int d = p;
     
    // Setzt das Ergebniss zusammen
    while (d < n + 1) {
     
        // fügt Komma ein wenn mehr als eine Person entfernt wird
        if (d != p) {
        ausgabe = ausgabe + ", ";
        }
         
        // entfernte Person wird mit in den String eingeschrieben
        ausgabe = ausgabe + String.valueOf(d);
        d = d + p;
     
    }
     
    // wenn keine Person entfernt wurde wird der String mit "---" gefüllt
    if (ausgabe.equals("")) {
        ausgabe = "---";
    }
    return ausgabe;
    }
 
    // Hauptmethode
    public static void main(String[] args) {
    // Klassenobjekt um auf die Methode zugreifen zu können
    josephusproblem tue = new josephusproblem();
     
    // Scanner zum Einlesen der Nummern
    Scanner scan = new Scanner(System.in);
     
    // Eingabeaufforderungen + Eingaben
    System.out.println("Geben Sie die Anzahl an Leuten an:");
    int n = scan.nextInt();
    System.out
        .println("Geben Sie den Platz der Person in dem Kreis,\ndie als erstes entfernt werden soll, an:");
    int p = scan.nextInt();
    scan.close();
     
    // Ergebniss wird ausgegeben
    System.out.println("Die Persone/n an den/m Platz/Plaetzen "
        + tue.permutation(n, p) + " wurden aus dem Kreis enfternt");
    }
 
}

Lösung von: Sebastian Littel ()

n = int(raw_input('Anzahl der Personen: '))
p = int(raw_input('Schrittweite: '))
 
reihe = range(1,n+1)
gefunden  = []
 
while len(gefunden)<n:
 
        # i...Reihen-Index
        i = p%len(reihe)
        if i == 0:
                i = len(reihe)
        i -= 1
         
        gefunden.append(reihe.pop(i))
        reihe = reihe[i::]+reihe[0:i]
 
print gefunden
 
''' -*- Bsp für n=8, p=5, 1. Durchlauf: 
 
reihe = [1 2 3 4 5 6 7 8]
 
i = p%len(reihe) = 5%8 = 5
i = i-1 = 4 (Person '5' steht in Liste an Stelle 4)
 
gefunden = [reihe[i]]  = [reihe[4]] = [5]
reihe = [1 2 3 4 6 7 8]
 
reihe = reihe[i::]+reihe[0:i]
reihe = [6 7 8 1 2 3 4]
 
  -*- Ende 1. Durchlauf '''

Lösung von: Steffen Jähn ()

HTML-Code:
 
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<form action="josephusPermutation.php" method="post">
    <input type="number" min="0" name="anzahl">Tragen Sie hier die Anzahl ein<br></input>
    <input type="number" min="0" name="p">Tragen Sie hier "p" ein<br></input>
    <input type="submit" value="Abschicken" /><input type="reset" />
</form>
 
 
</body>
</html>
 
 
PHP-Code:
 
<?php
$anzahlDerLeute = $_POST["anzahl"]; //Anzahl der Leute
$p = $_POST["p"]; //Beginnend bei der p-ten Person
 
 
$i = $p;
$ausgabe = "";
 
while ($i <= $anzahlDerLeute)
{
    if ($i != $p)
    {
        $ausgabe .= ", ";
    }
 
    $ausgabe .= $i;
 
    $i += $p;
}
 
echo $ausgabe;
 
 
?>

Lösung von: Maik Scheiermann (Powercloud GmbH)

function josephusCount(people, skip) {
  var circle = [],
      executed = [],
      counter;
  for (counter = 1; counter <= people; counter++) circle.push(counter);
 
  counter = 0;
  while(circle.length > 0) {
    counter = (counter - 1 + skip) % circle.length;
    executed.push(circle.splice(counter, 1)[0]);
    }
  return executed;
}
 
console.log(josephusCount(7, 4).join(", "));
console.log(josephusCount(8, 5).join(", "));

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

def josephus(n,k):
    l = list(range(1,n+1))
    josephus_permutation = []
    m=0
    while len(l)>0:
        for i in range(k):
            p = (i+m) % len(l)
        if p == len(l)-1:
            m=0
        else:
            m=p
        josephus_permutation.append(l[p])
        del l[p]
     
    return josephus_permutation

Lösung von: Matthias Richter (BIP Kreativitätsgymnasium, Leipzig)

n, p = int(input("n: ")), int(input("p: "))
in_list, out_list, curr_index = list(range(1, n+1)), [], 0
while in_list:
    out_list.append(in_list.pop((curr_index:=(curr_index+p-1)%len(in_list))))
print(out_list)

Lösung von: Name nicht veröffentlicht

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Josephus_Problem
{
 
    class Program
    {
        static void Main(string[] args)
        {
            int menge = 0;
            int person = 0;
            List<int> kreis = new List<int>();
            List<int> ausgeschPerson = new List<int>();
 
            Console.WriteLine("Wieviele Personen sollen es sein?");
            menge = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Die jeweils wievielte Person soll den Kreis verlassen?");
            person = Convert.ToInt32(Console.ReadLine());
 
            for (int i = 0; i < menge; i++)
            {
                kreis.Add(i);
            }
            for (int i = person; i < kreis.Count; i+=person)
            {
                ausgeschPerson.Add(kreis[i]);
                kreis.Remove(kreis[i]);
            }
            Console.WriteLine();
            foreach (int a in ausgeschPerson)
            {
                Console.WriteLine(a);
            }
            Console.ReadKey();
 
        }
    }
}

Lösung von: Chrischi Leif (S&N Datentechnik)

// NET 6.x | C# 10.x | VS-2022
 
static IEnumerable<int> Josephus(int n, int p) {
    var i = 0;
    var rng = Enumerable.Range(1, n).ToList();
    while (rng.Count > 0) {
        i = (i - 1 + p) % rng.Count;
        yield return rng[i];
        rng.RemoveAt(i);
    }
}
 
Console.WriteLine(string.Join(", ", Josephus(7, 4)));

Lösung von: Jens Kelm (@JKooP)

// C++ 17
#include <iostream>
#include <vector>
#include <numeric>
 
std::vector<int> Josephus(int n, int p) {
    unsigned long long i{ 0 };
    std::vector<int> rng(n);
    std::vector<int> out;
    std::iota(rng.begin(), rng.end(), 1);
 
    while (rng.size() > 0) {
        i = (i - 1 + p) % rng.size();
        out.push_back(rng[i]);
        rng.erase(rng.begin() + i);
    }
    return out;
}
 
int main() {
    auto jos{ Josephus(8, 5) };
    for (const auto& j : jos) {
        std::cout << j << ", ";
    }
}

Lösung von: Jens Kelm (@JKooP)

Zeit:	2
Schwierigkeit:	Mittel
Webcode:	zqch-t09b
Autor:	Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Programmieren lernen

Web-Code:

Josephus-Problem (Felder)

4 Kommentare (ansehen)

Kommentare (4)

19 Lösung(en) (ansehen)

Verifikation/Checksumme: (ansehen)

Aktionen

Bewertung

Meta