Skip to content

Instantly share code, notes, and snippets.

@stormxuwz
Created January 9, 2015 06:37
Show Gist options
  • Save stormxuwz/d03613b5ce7c6e21cd2c to your computer and use it in GitHub Desktop.
Save stormxuwz/d03613b5ce7c6e21cd2c to your computer and use it in GitHub Desktop.
Josephus problem
# include <iostream>
using namespace std;
struct person{
person * previousPerson;
person * nextPerson;
int sword;
int num;
};
person * createCircle(int n){
person * firstPerson=new person;
firstPerson->sword=1;
person * index;
index=firstPerson;
firstPerson->num=0;
for(int i=1;i<n;i++){
index->nextPerson=new person;
index=index->nextPerson;
index->num=i;
index->sword=0;
}
index->nextPerson=firstPerson;
return firstPerson;
}
person *kill (person * startPerson){
person * myNeighbor=startPerson->nextPerson;
startPerson->nextPerson=myNeighbor->nextPerson;
startPerson->nextPerson->sword=1;
startPerson->sword=0;
delete myNeighbor;
return startPerson->nextPerson;
}
int main(){
person * pointer=createCircle(100);
while(pointer->num!=pointer->nextPerson->num){
pointer=kill(pointer);
}
cout<<"The final Person is:"<<endl;
cout<<pointer->num+1;
delete pointer;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment