int FindWinner(int n, int m)
package brainteasers;
public class FindWinner {
public static void main(String[] args) {
FindWinner finder = new FindWinner();
char winner = finder.findWinner(10,3);
System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
}
private char findWinner(int n, int m){
char[] people = getPeople(n);
boolean[] eliminated = new boolean[n];
//always start from 1st person
int remainingGuys = n;
int current = 0;
while(remainingGuys>1){
int inkiPinki=0;
while( eliminated[current] || ++inkiPinki != m )
current = (current+1) % n;
eliminated[current] = true;
printStatus( eliminated, people );
remainingGuys--;
while(eliminated[(current+1)%n]){
current++;
}
current = (current+1)%n;
}
System.out.println();
return people[current];
}
private void printStatus(boolean[] eliminated, char[] people) {
System.out.println();
for(int i=0;i
if(eliminated[i]){
output = people[i];
}else{
output = (char)(people[i] - 32);
}
System.out.print(output+" ");
}
}
private char[] getPeople(int n) {
char[] people = new char[n];
System.out.println("Participants are...");
for(int i=0;i
System.out.print((char)(people[i]-32)+" ");
}
System.out.println();
return people;
}
}
/*
Participants are...
A B C D E F G H I J
A B c D E F G H I J
A B c D E f G H I J
A B c D E f G H i J
A b c D E f G H i J
A b c D E f g H i J
a b c D E f g H i J
a b c D E f g h i J
a b c D e f g h i J
a b c D e f g h i j
And the winner is D!!
*/
2 comments :
//============================================================================
// Name : puzzle.cpp
// Author : Prabhu Jayaraman
// Version : 0.1
// Copyright : Free
// Description : Find Last man stand
//============================================================================
#include
using namespace std;
int FindWinner(int n, int m)
{
int a[n];
for(int i=0;i<n;i++)
{
a[i] = 1;
}
int e = 0;
int c = 0;
for(int i=0;;i++)
{
if(e == (n-1))
break;
if(a[i%n] == 1)
c++;
if(c == m)
{
a[i%n] = 0;
e++;
c = 0;
}
}
for(int i=0;i<n;i++)
{
if(a[i] == 1)
return i+1;
}
return -1;
}
int main()
{
int x = FindWinner(20,19);
cout << x << endl;
return 0;
}
This is the Josephsus Problem. The problem can be solved using this recurrence:
f(n) = (f(n - 1) + m) % n, f(1) = 0
Thanks to Purav to Providing This Recursive function
Post a Comment