Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

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.

5 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (5)

gressly 23. November 2013 21:56   reply report
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.
crouser 21. November 2013 17:27   reply report
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.
BKluszynski 14. März 2012 17:57   reply report
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   reply report
__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   reply report
Unter "Verifikation/Checksumme" sollte in der zweiten Zeile meines Erachtens p = 5 stehen.

15 Lösung(en)

/* 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 Gressly Freimann (SANTIS Training AG)

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)

Verifikation/Checksumme:

n=7, p=4 -> 4, 1, 6, 5, 7, 3, 2

n=8, p=5 -> 5, 2, 8, 7, 1, 4, 6, 3

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: Mittel
Webcode: zqch-t09b
Autor: Philipp Gressly Freimann (SANTIS Training AG)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen