Archangel Macsika
Suppose there are n people standing in a circle. Person no.1 has a sword and he uses it kill no.2 and passes it onto person no.3. All the persons does the same until only 1 survives. Which number will survive at last and what algorithm can be applied to solve this?
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
Solution in C++ Programming Language
#include <iostream>
using namespace std;
int find_power(int n)
{
n = n | (n>>1);
n = n | (n>>2);
n = n | (n>>4);
n = n | (n>>8);
return ((n+1)>>1);
}
int main()
{
int nearest_power, n;
cout<<"Enter the number of people standing in a circle"<<endl;
cin>>n;
nearest_power = find_power(n);
int survivor = 2*(n - nearest_power) + 1;
cout<<survivor<<" will survive at last!";
return 0;
}
The Algorithm used is recursion with the formula 2n+1.
Where n is the value you get when you use the given n value to subtract the closest power of 2 to the given n number but less than it.
Another Solution in C++ Programming Language as Requested by a User
#include
using namespace std;
int find_power(int a, int b)
{
int e=1;
for(int i=0;i<b;i++)
{
e=e*a;
}
return e;
}
int main()
{
int survivor, num, k, i=0;
cout<<"Enter the number of people standing in a circle: ";
cin>>num;
for(int i=0;i<num;i++)
{
k=find_power(2,i);
if(k>num)
{
k=find_power(2,i-1);
int x=num-k;
survivor=(2*x)+1;
break;
}
}
cout<<survivor<<" will survive at last!";
return 0;
}
The Algorithm used is recursion with the formula 2n+1.
Where n is the value you get when you use the given n value to subtract the closest power of 2 to the given n number but less than it.
If you would like to see a different solution or an implementation in a different programming language Kindly let us know