1. ## 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;
}```
Haytham

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

4. 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. 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. nope , new works in C too , or my compiler accept it , malloc() and free() is equivalent to new() and delete

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

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. 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. Originally Posted by Haytham
nope , new works in C too
You are completely wrong, unless "works" means "doesn't work".

Originally Posted by Haytham
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.

Originally Posted by Haytham
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. i am using Dev-C++ ...

and it runs the code

also it runs on borland C++ version 5.02 for windows

11. 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. 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. It maybe works for you, it doesn't even compile for me.

14. what compiler are you using?

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