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 Complete Code

Comments

No comments yet