Thread: Please , i need help with this Josephus Problem

well , i have an assignment

" the josephus problem is as follows : n people , numbered 1 -> n are sitting in a circle starting at person 1 , a hot potato is passed,after m passes , the person holding the hot potato is eliminated , the circle gets smaller, and the game continues . the person next to the eliminated person picks up the hot potato. the last remaining person wins , for example , if n=5 and m =1 , player 3 wins and the order of elimination is 2,4,1,5 . Write a program to play the josephus problem for general values n,m , using a linked list "

here is my code , but has an error , and i dont know whats wrong , can any one help me ?

Code:

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

struct node;
typedef struct node *PtrToNode;

struct node
{
       int element;
       PtrToNode next;
       };
                                   // Make Empty //
PtrToNode MakeEmpty(PtrToNode L)
{
          L=new struct node;
          if(L==NULL)
                     printf("Out of Memory :( ");
                     L->next=NULL;
                     return L;
}
                   
                        //************* InsertLast *************//
void InsertLast(int i,PtrToNode L)
{
     if(L != NULL)
     {
      PtrToNode TmpCell=new struct node;
      TmpCell->element=i;
      PtrToNode P=L;
      while(P->next!=NULL)
      { 
        P=P->next;
        }
        P->next=TmpCell;
        TmpCell->next=NULL;
      }
}
                        
                        //********** Join ********** //
void Join(PtrToNode L)
{
     PtrToNode P=L;
     while(P->next!=NULL)
     {
       P=P->next;
     }
     P->next=L->next;
}           
                          //********** Delete ********** //
void Delete(PtrToNode Q)
{
     PtrToNode TmpCell; 
     TmpCell=Q->next;
     Q->next=TmpCell->next;
     delete(TmpCell);  
}

                   //********** Another DecreasingNodes ********** //
/*                 // has error if m = 2 or more :(
int DecreasingNodes(int m,int n,PtrToNode L){
     PtrToNode P=L; // pointer to the player
     PtrToNode Q=L; // cleaner pointer ;) 
    for(int i=0;i<n-1;i++)
     {
            
            P=P->next;   
            for(int x=0;x<m;x++)
            {
                    P=P->next;
                    Q=Q->next;
                    printf("\n Player # %d Out",P->element);
                    Delete(Q); // Deletes the node that P step on previously
             }
      }
       return (P->next->element);  
}*/
//********** DecreasingNodes ********** //
int DecreasingNodes(int m,int n,PtrToNode L)
{
    PtrToNode P=L;
    
    
    for(int i=0;i<n-1;i++)
    {
            PtrToNode T=P->next;       
            for(int x=0;x<m;x++)
            {
                    
                    T=T->next;
                    printf("\n Player # %d Out",T->element);
                    }
    P=T->next;
    Delete(T);
            
    }
    return (P->element);
    }
                         //********** MAIN ********** //
          
 main()
{
     int m,n; // n=number of persons , m = #of passes 
     int result;
     PtrToNode L;
     L=MakeEmpty(NULL);
                  // initiate list of Nodes
     printf("plz enter # of nodes\t");
     scanf("%d",&n);
     printf("plz enter # of Steps to Jump \t");
     scanf("%d",&m);
     
     for(int i=1;i<n+1;i++)
     {
             InsertLast(i,L);
             }    
    Join(L); // join the last node with the node after header         
    result=DecreasingNodes(m,n,L);
    printf("\n Player # %d wins",result);
    

   
   
    
    
     
     
     getch();
     return 0;
 }

Thanks in advance
Haytham

as mentioned, what _are_ the errors?

also, do you really need this?

Code:

typedef struct node *PtrToNode;

i think removing this will make things easier.

if im not mistaken, there is no 'new' keyword in C. 'new' is used in C++ to create dynamic memory, in C you would use 'malloc'.

Code:

PtrToNode TmpCell=new struct node;

do you know Java? if so are you trying to use it's 'new' keyword to achieve the same thing here? thats what it looks like to me, but maybe not.

well , its C
and the error is , when i put n = 5 , m =1 like the example , the order of elimination isnt 2,4,1,5 and 3 wins

nope , new works in C too , or my compiler accept it , malloc() and free() is equivalent to new() and delete

we know its (supposed to be) C, but its kind of a mix right now, and wont compile.

and as already stated...

why are you using 'new'? in C++, 'new' is used to allocate memory dynamically, for example, an array whos size is unknown until the program is running. In Java, 'new' is used to create instances of objects, but C isnt object-oriented.

i imagine you want to use 'malloc' in place of 'new', to allocate memory for your nodes?

what compiler are you using? maybe its a C++ compiler. Im using GNU's 'gcc' compiler and it prints about 15 errors for the above code.

then its a C++ program, so include the C++ headers and get rid of the C ones, or leave everything and change the new's and use malloc, and later use free.

pick either c or c++, update the code, post back and then we can go from there. if you choose c++ then request it to be moved to c++ forum or post the new code there.

your code doesnt compile on a _C_ compiler.

here is my final code , it works
thanks alot

Code:

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

struct node;
typedef struct node *PtrToNode;

struct node
{
       int element;
       PtrToNode next;
       };
                                   // Make Empty //
PtrToNode MakeEmpty(PtrToNode L)
{
          L=new struct node;
          if(L==NULL)
                     printf("Out of Memory :( ");
                     L->next=NULL;
                     return L;
}
                   
                        //************* InsertLast *************//
void InsertLast(int i,PtrToNode L)
{
     if(L != NULL)
     {
      PtrToNode TmpCell=new struct node;
      TmpCell->element=i;
      PtrToNode P=L;
      while(P->next!=NULL)
      { 
        P=P->next;
        }
        P->next=TmpCell;
        TmpCell->next=NULL;
      }
}
                        
                        //********** Join ********** //
void Join(PtrToNode L)
{
     PtrToNode P=L;
     while(P->next!=NULL)
     {
       P=P->next;
     }
     P->next=L->next;
}           
                          //********** Delete ********** //
void Delete(PtrToNode Q,PtrToNode L)   // actually only bypass
{
     PtrToNode B=L; // points to the header 
     while(B->next != NULL)
     {
      B=B->next;
      if(B->next==Q)
      {
       B->next=Q->next;
       break;
       }
       }
}

//********** DecreasingNodes ********** //


int DecreasingNodes(int m,int n,PtrToNode L)
{
    PtrToNode P=L; // pointer p points to the header
    
    
    for(int i=0;i<n-1;i++)
    {
            PtrToNode T=P->next;     //pointer t , moving pointer telling p  
            for(int x=0;x<m;x++)     // where to go as a next step
            {
                    
                    T=T->next;
                    
                    }
    P=T;                
    printf("\n Player # %d Out",P->element);
    Delete(T,L);
            
    }
    return (P->next->element);
    }
                         //********** MAIN ********** //
          
 main()
{
     int m,n; // n=number of persons , m = #of passes 
     int result;
     PtrToNode L;
     L=MakeEmpty(NULL);
                  // initiate list of Nodes
     printf("plz enter # of nodes\t");
     scanf("%d",&n);
     printf("plz enter # of Steps to Jump \t");
     scanf("%d",&m);
     
     for(int i=1;i<n+1;i++)
     {
             InsertLast(i,L);
             }    
    Join(L); // join the last node with the node after header         
    result=DecreasingNodes(m,n,L);
    printf("\n Player # %d wins",result);
    

   
   
    
    
     
     
     getch();
     return 0;
 }

It maybe works for you, it doesn't even compile for me.

what compiler are you using?

A C compiler, that compiles C code and not C/C++ mix like your code. I use Dev-C++ in C mode as well as code::blocks.