Josephus problem
The Josephus problem belongs to the history and is a perfect example that how mathematics can save your life.
There were Jewish soldiers who were captured by roman army, but in order to avoid the capture and probably torture they devised a method of suicide which will ensure the death of each individual. They formed a circle and numbered each member starting from 1 to n, n being the number of soldiers, they decided that the first person will kill the second one then next remaining alive person will kill next person alive to him and this goes on and the last person obviously has to kill himself.
However, there was a soldier named Josephus who preferred capture over suicide, so he wanted to know where he should take position so he remain alive as the last person
Here is the illustration how it works for n = 10.
I am not going to go into mathematics required to solve this problem, I have already explained the problem very clearly in the mathematics section, those people who are unaware of terms like f(n), c, a, I recommend to go through mathematics first, the link can be found at the end of this article.
Now let's get into coding part,
The code is very simple and self explainatory.
Just defining a function f(int n) which is same as the mathematics version f(n) , but it also calculates value of a, c inside itself and returns the value f(n).
Link:
http://sdjee2015.wixsite.com/whyandhow/single-post/2017/01/18/The-Josephus-Problem
Full C++ implementation/code:
int f(int k) { int a=0,c; int i; int temp = k; while(temp > 1) { temp = temp/2; a++; } c = k-pow(2,a); int result = 2*c + 1; return result; }
int main() { cout<<"Enter the number of soldiers "; int n; cin>>n; int Result = f(n); cout<<endl; cout<<"The safe position number is "<<Result<<endl;
}
Sample INPUT/OUTPUT:
In history there were 41 soldiers, hence test case for n=41
Other cases:
