约瑟夫环

文章时效性提示

本文发布于 495 天前，部分信息可能已经改变，请注意甄别。

题目：有n个人围成一圈，顺序排号。
从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

#include <stdio.h>
int Cal_Josephus(int input,int* arr)
{
    int i = 0;
    int j = 0;
    int stay = input;
    int ret = 1;
    while (stay>1)//当现在留下的人数大于1的时候，一直循环
    {
        for (i=0; i<input; i++)
        {
            if (arr[i] == 1)
            {
                j++;
            }
            if (j==3)
            {
                arr[i] = 0;
                j = 0;
                stay--;
            }
        }
    }
    i = 0;
    while (arr[i] != 1)
    {
        ret++;
        i++;
    }
    return ret;
}
int main(int argc, const char * argv[]) {
    int input;
    scanf("%d",&input);
    int arr[input];
    int x;
    for (x=0; x<input; x++)//先把整个数组都赋值1，代表现在留下
    {
        arr[x] = 1;
    }
    int ret = Cal_Josephus(input,arr);
    printf("留下的是第%d个人",ret);
    return 0;
}