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
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.