Programmieren lernen

/* 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)