Solution To Josephus Problem

Code Id 24
Date Updated 3/7/2010
Title Solution to Josephus problem  
Description
This is a program to solve Josephus problem. The Josephus problem consists of a group of soldiers surrounded by an overwhelming enemy force. There is a single horse available for escape. To determine which soldier is to escape, they form a circle and a number n is picked from a hat. A name is also picked from the hat. They begin to count clockwise around the circle, beginning with the soldier, whose name is picked. One soldier is removed from the circle, on which count reached n and the count starts again with next soldier, removing another soldier each time the count reaches n. The last remaining soldier is the one to take the horse. 
                                  
Codes Snippet
#include 
#include 
struct node
{
        char name[20];
        struct node *next;
};
struct node *getnode(void)
{
        struct node *tp;
        tp=(struct node *)malloc(sizeof (struct node));
        printf(�n Input name n�);
        scanf(�%s�,tp->name);
        tp->next=NULL;
        return (tp);
}
void addnode(struct node **pplh, struct node *tp)
{
        struct node *travel;
        travel=NULL;
        if (*pplh=NULL) 
        {
                *pplh = tp;
                (*pplh) -> next=*pplh;
        }
        
 
else
        {
                travel=*pplh;
                while(travel->next != (*pplh))
                        travel=travel->next;
                tp->next=*pplh;
                travel->next=tp;
        }
}
void create (struct node **pplh)
{
        struct node *getnode(void);
        void addnoce( struct node **pplh, struct node *tp);
        struct node *ltp;
        char ch1=�y�;
        ltp=NULL;
        while(ch1==�y�)
{
                ltp=getnode();
                addnode(pplh,ltp);
                printf(�nWant to add more names ?�);
                ch1=getchar();
        }
}
void countnode(struct node **pphl,int *lpn)
{
        struct node *travel, *tp;
        int ctr;
        tp=travel=NULL;
        travel=*pplh;
        if (*lpn==1)
        {
                while(travel->next !=*pplh)
                        travel=travel->next;
                printf(�nNAME LEFT IS %sn�,travel->name);
                return;
        }

        else
        {
                while(travel->next !=travel)
                {
                for(ctr=1, ctr< (*lpn); ctr++)
                                travel=travel->next;
                        tp=travel->next;
                        travel->next=travel->next->next;
                travel=travel->next;
                        free(tp);
                }
                printf(�nNAME LEFT IS %sn�,travel->name);
        }/*end else*/
}
main()
{
        struct node *getnode();
        void addnode (struct node **pphl,struct node *tp);
        void create (struct node *pphl);
        void countnode (struct node **pplh, int *lpn);
        struct node *phg;
        int n;
        phg=NULL;
        printf(�ninput the namesn�);
        create(&phg);
        printf(�ninput num to be moved�);
scanf(�%d�,&n);
        countnode(&phg, &n);
        getch();
}

Comments are closed.