Please , i need help with this Josephus Problem

This is a discussion on Please , i need help with this Josephus Problem within the C Programming forums, part of the General Programming Boards category; well , i have an assignment " the josephus problem is as follows : n people , numbered 1 -> ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    14

    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

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    For future reference, it would be great if people give a little more of an idea of what the "error" is they are referring to. For the most part, we can assume that if your code was perfect, you wouldn't have posted.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Want to watch a program crash?
    Code:
    PtrToNode MakeEmpty(PtrToNode L)
    {
              L=new struct node;
              if(L==NULL)
                         printf("Out of Memory :( ");
                         L->next=NULL;
    Using better indenting would help you spot things like this. Overall it's a whole lot better than some that gets posted here, but the bottom line doesn't go with the one above it.
    Code:
    void InsertLast(int i,PtrToNode L)
    {
         if(L != NULL)
         {
          PtrToNode TmpCell=new struct node;
    So is this supposed to be C, or C++? Once you figure that out, doctor up your code, and try again.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    14
    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

  6. #6
    Registered User
    Join Date
    Apr 2007
    Posts
    14
    nope , new works in C too , or my compiler accept it , malloc() and free() is equivalent to new() and delete

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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?

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  9. #9
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Quote Originally Posted by Haytham View Post
    nope , new works in C too
    You are completely wrong, unless "works" means "doesn't work".

    Quote Originally Posted by Haytham View Post
    or my compiler accept it ,
    You are using a C++ compiler, I imagine, which will let you do a few things. The code compiles for me using Borland's C++ compiler.

    Quote Originally Posted by Haytham View Post
    malloc() and free() is equivalent to new() and delete
    No. They are only equivalent in that they both allocate/deallocate memory. But new/delete is responsible for calling constructors/destructors in C++ and is the proper way of managing memory in C++. In C, the proper way of managing memory is to use malloc() and free().

    If you are using C++, you cannot malloc() something and then delete it or use new to allocate memory and then free() it. You must stay consistent, which at least you have done. If you have to use C for this assignment and not C++, you must use malloc() and free().

  10. #10
    Registered User
    Join Date
    Apr 2007
    Posts
    14
    i am using Dev-C++ ...

    and it runs the code

    also it runs on borland C++ version 5.02 for windows
    Last edited by Haytham; 04-07-2007 at 12:11 AM.

  11. #11
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  12. #12
    Registered User
    Join Date
    Apr 2007
    Posts
    14
    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;
     }

  13. #13
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    It maybe works for you, it doesn't even compile for me.

  14. #14
    Registered User
    Join Date
    Apr 2007
    Posts
    14
    what compiler are you using?

  15. #15
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  3. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  4. The Josephus Problem
    By Nakeerb in forum C++ Programming
    Replies: 5
    Last Post: 11-21-2002, 08:43 AM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 05:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21