C++: Josephus Problem

Josephus problem is a math puzzle with a grim description: $n$ prisoners are standing on a circle, sequentially numbered from $0$ to $n - 1$ .

An executioner walks along the circle, starting from prisoner $0$ , removing every $k$ -th prisoner and killing him.

As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed.
For example, if there are $n = 5$ prisoners and $k = 2$ , the order the prisoners are killed in (let’s call it the “killing sequence”) will be 1, 3, 0, and 4, and the survivor will be #2.

Task Given any $n, k > 0$ , find out which prisoner will be the final survivor. In one such incident, there were 41 prisoners and every 3rd prisoner was being killed ( $k = 3$ ). Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale. Which number was he?

#include <iostream>
#include <vector>
 
//--------------------------------------------------------------------------------------------------
using namespace std;
typedef unsigned long long bigint;
 
//--------------------------------------------------------------------------------------------------
class josephus
{
public:
    bigint findSurvivors( bigint n, bigint k, bigint s = 0 )
    {
	bigint i = s + 1;
	for( bigint x = i; x <= n; x++, i++ )
	    s = ( s + k ) % i;
 
	return s;
    }
 
    void getExecutionList( bigint n, bigint k, bigint s = 1 )
    {
	cout << endl << endl << "Execution list: " << endl;
 
	prisoners.clear();
	for( bigint x = 0; x < n; x++ )
	    prisoners.push_back( x );
 
	bigint index = 0;
	while( prisoners.size() > s )
	{
	    index += k - 1;
	    if( index >= prisoners.size() ) index %= prisoners.size();
	    cout << prisoners[static_cast<unsigned int>( index )] << ", ";
 
	    vector<bigint>::iterator it = prisoners.begin() + static_cast<unsigned int>( index );
	    prisoners.erase( it );
	}
    }
 
private:
    vector<bigint> prisoners;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
    josephus jo;
    bigint n, k, s;
    while( true )
    {
	system( "cls" );
	cout << "Number of prisoners( 0 to QUIT ): "; cin >> n;
	if( !n ) return 0;
	cout << "Execution step: "; cin >> k;
	cout << "How many survivors: "; cin >> s;
 
	cout << endl << "Survivor";
	if( s == 1 )
	{
	    cout << ": " << jo.findSurvivors( n, k );
	    jo.getExecutionList( n, k );
	}
	else
	{
	    cout << "s: ";
	    for( bigint x = 0; x < s; x++ )
		cout << jo.findSurvivors( n, k, x ) << ", ";
 
	    jo.getExecutionList( n, k, s );
	}
 
	cout << endl << endl;
	system( "pause" );
    }
    return 0;
}
//--------------------------------------------------------------------------------------------------

Output:

Number of prisoners( 0 to QUIT ): 41
Execution step: 3
How many survivors: 1

Survivor: 30

Execution list:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36
, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15,


Number of prisoners( 0 to QUIT ): 41
Execution step: 3
How many survivors: 3

Survivors: 30, 15, 34,

Execution list:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36
, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3,


Number of prisoners( 0 to QUIT ): 71
Execution step: 47
How many survivors: 11

Survivors: 29, 58, 41, 14, 39, 28, 35, 45, 64, 49, 27,

Execution list:
46, 22, 70, 48, 26, 5, 56, 36, 17, 0, 54, 38, 23, 9, 66, 55, 43, 33, 25, 16, 11,
6, 2, 69, 68, 1, 4, 10, 15, 24, 32, 42, 53, 65, 20, 40, 60, 19, 47, 8, 44, 13,
52, 31, 12, 62, 57, 50, 51, 61, 7, 30, 59, 34, 18, 3, 21, 37, 67, 63,

SOURCE

Content is available under GNU Free Documentation License 1.2.