How to solve Josephus problem using c?

Answer 1

Previous answer was in C++, please learn the difference.

/**********************************************************

*josephus.c: Solve the josephus problem for an arbitrary number of players *and an arbtitrary number of players missed each time.

*

*Author: XXX

*

*Input1:Number of players

*Input2:Number of players to miss each time

*Output:The lucky Survivor

**********************************************************

#include <stdlib.h> /*For calloc, free and sizeof*/

#include <stdio.h> /*For printf, scanf*/

/*---Global structure to hold player details and a pointer to the next player---*/

struct player{

int player_num;

struct player *next;

};

int main (void) {

int i, j; /*Loop counters*/

int n; /*Number of players*/

int k; /*Number to skip each time*/

struct player *firstplayer; /*Hold firstplayer, so list can be circular linked*/

struct player *current_player; /*Hold current player*/

struct player *victim; /*Hold victim, for freeing*/

/*---Welcome statement---*/

printf("\njosephus.c: Program to solve the Josephus problem for an arbitrary number of "

"\n players and an arbitrary choice of count. The output will be the "

"\n number of the surviving player.\n\n");

/*---Request the number of players and assign to n---*/

printf("Please input the number of players.\n>>");

scanf("%d", &n) ;

/*---Request how many players to miss and assign to k---*/

printf("Please input the number of players you want to miss before execution.\n>>");

scanf("%d", &k);

/*---Alert the user, and exit the program, if they entered the wrong type of input---*/

if (n<=0 k<=0) {

printf("\a\n\nPlease enter positive integers only for the player and count!! "

"\nExiting...\n\n");

return 0;

}

/*---Set initial current player and firstplayer to be the same and assign space dynamically to hold them---*/

firstplayer=current_player=(struct player *)calloc(1, sizeof(struct player));

/*---Detect allocation failure---*/

if (current_player==NULL) {

printf("\a\nAllocation failure. Program terminates...\n\n");

exit(1);

}

current_player->player_num=1; /*Set the first/initial current players number to one*/

/*---Loop over n, assigning space for all the players and linking each successive one to

* the previous. Note: we do not count from 1, since already done above---*/

for (i=2; i<=n; ++i) {

current_player->next=(struct player *)calloc(1, sizeof(struct player));

/*---Detect allocation failure---*/

if (current_player->next==NULL) {

printf("\a\nAllocation failure. Program terminates...\n\n");

exit(1);

}

current_player=current_player->next; /*Current player now points to the next player*/

current_player->player_num=i; /*Define each player number*/

}

/*Finally link the final current player to the firstplayer, to make the list circular*/

current_player->next=firstplayer;

/*---Loop over n, counting up one every time a player dies---*/

for (i=1; i<n; ++i) {

/*Cycle through players until the one just before the unlucky one is reached*/

for (j=1; j<k; ++j) {

current_player=current_player->next;

}

/*Victim is the player just after the current player*/

victim=current_player->next;

/*Set the current player to point at the space just after where the victim was*/

current_player->next=current_player->next->next;

/*Set space now pointed to by victim free*/

free(victim);

}

/*Notify user of the game survivor*/

printf("\nThe lucky survivor is = %d\n\n", current_player->player_num);

/*---Set the final players space free---*/

free(current_player);

return 0;

}