約瑟夫環(huán)問題(數(shù)組法)c語言實(shí)現(xiàn)

2020-01-26 15:39:15

字體：大中小

供稿：網(wǎng)友

問題說明
這個問題是以弗拉維奧?約瑟夫斯命名的，它是1世紀(jì)的一名猶太歷史學(xué)家。他在自己的日記中寫道，他和他的40個戰(zhàn)友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，并以抽簽的方式?jīng)Q定誰殺掉誰。約瑟夫斯和另外一個人是最后兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因于運(yùn)氣或天意，他不知道是哪一個機(jī)智的約瑟夫！

有N個編號為1~N的人圍成一圈，現(xiàn)在每隔兩個人（比如：1、4 之間隔了2、3）就將一個人淘汰出去，問最后剩下的是編號為幾的人？

算法代碼如下

復(fù)制代碼代碼如下:

#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 Joseph/n");
    }
    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. %d/n", peoples[i]);
            peoples[i] = 0;
            rest--;
        }else if (rest==1){
            printf("NO. %d is alive/n", peoples[i]);
            rest--;
        }
        i++;
    }
    system("pause");
    return 0;
}