There are n persons numbered from 0 to n - 1 standing in a circle. The person number k, counting from the person number 0, is executed. After that the person number k of the remaining persons is executed, counting from the person after the last executed one. The process continues until only one person is left. This person is a survivor. The problem is, given n and k detect the survivor's number in the original circle.
'Quoted from http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3521

:)I've written the code below.It works properly unless the user enters '1' as the period of counting:\$

``````// Joseph Problem

#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<conio.h>

class node
{
friend class list;
int info;
node *next;
};

class list
{
private:
node *first;
public:
list();
//~list();
void insert(int);
void count_delete(int);
int is_one_left();
int first_info();
void print();
};

list::list()
{
first=NULL;
}

void list::insert(int x)
{
if(first==NULL)
{
first=new node;
first->info=x;
first->next=first;
}
else
{
node *Temp=first;
while(Temp->next!=first)
Temp=Temp->next;
Temp->next=new node;
Temp=Temp->next;
Temp->info=x;
Temp->next=first;
}
}

void list::count_delete(int x)
{
node *Now=first;
node *Pre=NULL;
if(first->next!=first)
{
while(--x>0)
{
Pre=Now;
Now=Now->next;
}
Pre->next=Now->next;
delete Now;
}
first=(Pre->next) ;
}

int list::is_one_left()
{
if (first->next==first) return(1);
else return(0);
}

int list::first_info()
{
return first->info;
}
void list::print()
{
if(first==NULL) cout<<"List is empty\n";
else
{
node *Temp=first;
do
{
cout<<Temp->info<<" -> ";
Temp=Temp->next;
}while(Temp!=first);
cout<<endl;
}
}
void main(){
int n,   //number of nodes
x;       //period of counting
list people;
cout<<"Number of nodes: ";
cin>>n;
cout<<"Enter "<<n<<" numbers\n";
while(n-->0){
cin>>x;
people.insert(x);
}
people.print();
cout<<"Enter the period of lottery: ";
cin>>x;
while(!people.is_one_left()) people.count_delete(x);
cout<<"The winner is Number "<<people.first_info();
getch();
}``````
``````void list::count_delete(int x)
{
node *Now=first;
node *Pre=NULL;

if(first->next!=first)
{
while(--x>0)
{
Pre=Now;
Now=Now->next;
}
//What is the value of Pre, at this point, if the initial value of x is 1 ?
Pre->next=Now->next;
delete Now;
}
//What is the value of Pre, at this point, if first->next == first ?
//This one never actually becomes a problem, as you never call count_delete if first->next == first
first=(Pre->next) ;
}

//You need to make sure that Pre points to a previous node.
//If the initial value of x is 1, you have to traverse the entire list, to get the last node.``````
commented: really attentive +1

Oh my gosh!;)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.