Coders Packet

The Joshephus Problem using C++

By Tanmay Ahuja

The Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game using C++.

The Josephus Problem

Problem: There are n no. of people in a circle and a number k which represents the kth person to be killed. We have to tell the position of the last person.

Josephus

My Approach to the Question:

In this approach,

1)I first made a vector and saved elements from 1 to n in it.

2)Now I run a while loop until the size of the array <1 i.e. I keep on deleting the elements from our initial vector.

3)The formula I have used for deleting the elements is postion=(position+(no. of person to be skipped))%total no. of elements in the vector.

 

Below output is shown for 18 people and k=2 i.e we kill every second element in the circle therefore the last person to survive is the person sitting at position 5.

Josephus Output

Download project

Reviews Report

Submitted by Tanmay Ahuja (tanmay140)

Download packets of source code on Coders Packet