Joseph ring problem of array method c language implementation

  • 2020-04-02 02:04:07
  • OfStack

Problem specification
The question is named after flavio josephus, a 1st century jewish historian. He wrote in his diary that he and his 40 comrades were surrounded by Roman troops in the cave. They debated whether to kill themselves or be captured, and finally decided to kill themselves, drawing lots to decide who would kill whom. Josephus and the other man were the last two left. Josephus convinced the man that they would surrender to the Roman army and not commit suicide. Josephus attributed his survival to luck or providence. He did not know which clever Joseph!

      There are N numbered 1~N people in a circle, now every two people (such as: 1, 4 between 2, 3) will be eliminated from a person, ask the last is numbered for what people?

The algorithm code is as follows


#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    int people_count = 0;
    int *peoples = NULL;
    printf("please input people number: ");
    scanf("%d", &people_count);
    if (people_count < 2){
        printf("can't do Josephn");
    }
    peoples = (int *)calloc(people_count, sizeof(int));
    int i;
    for(i = 0; i < people_count; i++){
        peoples[i] = i+1;
    }
    i = 0;
    int j = 0;
    int rest = people_count;
    while(rest){
        if (i >= people_count){
            i %= people_count;
        }
        if (peoples[i] == 0){
            i++;
            continue;
        }
        if (j++ % 3 ==0 && rest > 1){
            printf("kill people NO. %dn", peoples[i]);
            peoples[i] = 0;
            rest--;
        }else if (rest==1){
            printf("NO. %d is aliven", peoples[i]);
            rest--;
        }
        i++;
    }
    system("pause");
    return 0;
}


Related articles: