Algorithm
Flavious Josephus Legend
By Neilor Tonin, URI 
Brazil
The Josephus' problem is known because of the Flavius Josephus' legend, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which one was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves skipping three in three. Josephus says that, by luck or maybe by the hand of God, he remained the last and gave up to the Romans.”
Input
There are NC (1 ≤ NC ≤ 30 ) test cases. In each input test case there will be a pair of positive integer numbers n (1 ≤ n ≤ 10000 ) and k (1 ≤ k ≤ 1000). The number n represents the quantity of people in the circle, numbered from 1 to n. The number k represents the size of step between two men in the circle.
Follow an example with 5 men and step 2: In this example the remaining element is 3.
The data must be read from standard input.
Output
For each test case we will have an output line, presenting in the following format: Case n: m always with a space before n and m.
| Output Sample | Input Sample |
|
3 |
Case 1: 3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int josephusLoop(int n, int k, int startingPoint)
{
if(n == 1)
return 1;
int newSp, survivor;
newSp = (startingPoint + k - 2) % n + 1;
survivor = josephusLoop(n - 1, k, newSp);
if(survivor < newSp){
return survivor;
}else{
return survivor + 1;
}
}
int josephus(int n, int k)
{
return josephusLoop(n, k, 1);
}
int main()
{
int nc, n, k, s, i;
scanf("%i", &nc);
for (i = 1; i < = nc; ++i)
{
scanf("%i %i", &n, &k);
s = josephus(n, k);
printf("Case %i: %in", i, s>;
}
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
using namespace std;
int josephusLoop(int n, int k, int startingPoint)
{
if(n == 1)
return 1;
int newSp, survivor;
newSp = (startingPoint + k - 2) % n + 1;
survivor = josephusLoop(n - 1, k, newSp);
if(survivor < newSp){
return survivor;
}else{
return survivor + 1;
}
}
int josephus(int n, int k)
{
return josephusLoop(n, k, 1);
}
int main()
{
int nc, n, k, s;
scanf("%i", &nc);
for (int i = 1; i < = nc; ++i)
{
scanf("%i %i", &n, &k);
s = josephus(n, k);
printf("Case %i: %in", i, s>;
}
return 0;
}
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
static FastScanner in = new FastScanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) throws IOException {
int NC = in.nextInt(), n, k;
for (int i = 1; i < = NC; i++) {
n = in.nextInt();
k = in.nextInt();
out.println("Case " + i + ": " + (josephus(n, k) + 1));
}
in.close();
out.close();
}
private static int josephus(int n, int k) {
// Runtime error :/
/* if (n == 1) {
return 0;
}
return (josephus(n - 1, m) + m) % n; */
int ans = 0;
for (int i = 2; i < = n; i++) {
ans = (ans + k) % i;
}
return ans;
}
static class FastScanner implements Closeable {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public FastScanner(InputStream input) {
reader = new BufferedReader(
new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
public String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
String line = reader.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
@Override
public void close() throws IOException {
tokenizer = null;
reader.close();
}
}
}
Input
Output