fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int josephus(int N, int M)
  5. {
  6.     struct node { int player_id; struct node *next; };
  7.  struct node *p, *q;
  8.  int i, count;
  9.  
  10. // Create circular linked list containing all the players:
  11.  
  12. p = q = (struct node*)malloc(sizeof(struct node));
  13.  
  14. p->player_id = 1;
  15.  
  16. for (i = 2; i <= N; ++i) {
  17.     p->next = (struct node*)malloc(sizeof(struct node));
  18.     p = p->next;
  19.     p->player_id = i;
  20. }
  21.  
  22. p->next = q;//Close the circular linkedlist by having the last node point to the 1st   
  23.  
  24. // Eliminate every M-th player as long as more than one player remains:
  25. printf("M=%d, Elimination:\n", M);
  26.  
  27. for (count = N; count > 1; --count) {
  28. 	printf("%d\n",p->next->player_id);	  
  29. 	p->next = p->next->next;
  30.  
  31.    for (i = 0; i < M - 1; ++i)
  32.     p = p->next;     
  33.      }    
  34. 	 return p->player_id;
  35.  
  36. }
  37.  
  38. int jos(int N)
  39. {
  40. 	int i=1;
  41. 	int res;
  42. 	while(1)
  43. 	{
  44. 		res=josephus(N,i);
  45. 		if(res==13)
  46. 		  return i;
  47. 		else 
  48. 		  i++;
  49. 	}
  50. }
  51.  
  52. int main()
  53. {
  54. 	int N=17;
  55. 	printf("The solution for N=17: M=%d\n",jos(N));
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 1920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
M=1, Elimination:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
M=2, Elimination:
1
3
5
7
9
11
13
15
17
4
8
12
16
6
14
10
M=3, Elimination:
1
4
7
10
13
16
3
8
12
17
6
14
5
15
11
2
M=4, Elimination:
1
5
9
13
17
6
11
16
7
14
4
15
10
8
12
3
M=5, Elimination:
1
6
11
16
5
12
2
9
17
10
4
15
14
3
8
13
M=6, Elimination:
1
7
13
3
10
17
9
2
12
6
4
16
5
11
8
15
M=7, Elimination:
1
8
15
6
14
7
17
11
5
3
2
4
10
16
9
12
The solution for N=17: M=7
https://ideone.com/4GWhu1
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!