Question

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical prob- lem related to a certain counting-out game.) People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a spec- ified number of people are skipped, the next person is executed. The procedure is repeated with the remain- ing people, starting with the next person, going in the same direction and skipping the same number of peo ple, until only one person remains, and is freed. The problem - given the number of people, starting point, di rection, and number to be skipped is to choose the position in the initial circle to avoid execution. [source https://en.wikipedia.org/wiki/Josephus_problem Instead of using bit-manipulating operations (as indicated on the Wikipedia web page, for example), implement your program by using an array to represent the circle of soldiers and loop and conditional constructs to "simu- late" the counting-out game.) Throughout this assignment (and the entire EECS22 course), you may assume that the user only enters valid input. Thus, there is no need for you to "bullet-proof" your implementation against invalid data entered by the user. Here specifically, you may assume that the number of soldiers is a positive natural number below 1,000 FIVE SOLDIERS FIVE SLPIERS FIVE SOLPIERS (a) all alivie (b) 1 kills 2 (c) 3 kills4 FIVL SOLDIURS FIVE SOLDIERS Kee 3 LIVES (d) 5 kills1 (e) 3 kills 5 Figure 1: Example with 5 persons taken from https: //www. youtube. com/watch?v=uCsD32G2MgE The problem is fully animated in https: / /www. youtube. com/watch?v=uCsD32G2MgE. Your program takes as input the number of people in the circle and outputs the safe spot. The interface of the C program should look like the following: ./josephus 3 How many people are in the circle? 41 The spot 19 is safe.

Answer 1

Here is the code for you:

//Josephus Problem
#include <stdio.h>
#include <stdlib.h>

int main()
{ int i, N, M;
   printf("How many people are in the circle? ");
   scanf("%i", &N);
   M = 2;
int count = N;
int array[N];
for(int i = 0; i < N; i++)
   array[i] = i+1;
  
int current = 0;
int temp = 0;
while(count != 1)
{
    if(array[current] != 0)
        temp++;
    current++;
    if(current == N)
        current = 0;
    if(temp >= M-1 && array[current] != 0)
    {
       temp = 0;
       array[current] = 0;  
       count--;
    }  
}
for(int i = 0; i < N; i++)
   if(array[i] != 0)
   {
      printf("The spot %i is safe.\n", array[i]);
      break;
   }
}

And the output screenshot is: