数组法解决约瑟夫环问题

Sapphire

2022/2/12

解题思路:

在输入人数n后，我们设置一个数组arr[n]并把其中每个元素设值为1，定义count=0(用来记人数)，counter=0(用来记报数)，然后开始遍历数组，每遍历一个元素，counter++，当counter=3时再把当前遍历到的这个数组元素赋值为0，这样下次就不会再数到这个数字了，并且count也++，表示被退出圈的人增加一个，最外层用一个while循环while(count!=n-1)就会一直执行数数，计数，赋值，直到count==n-1为止。

思路是不是非常清晰呢~~

注意事项:1.最后输出还保留在圈子里的那个人的编号时记得+1噢，因为数组的下标是从0开始的，与常理不同。

参考代码:

#include<stdio.h>
int main()
{
    int count=0;
    int counter=0;
    int n;
    scanf("%d",&n);//输入圈中有多少人 
    int arr[n];
    int i;
    for(i=0;i<n;i++)//把每个人定义为1，方便计数 
    {
        arr[i]=1;
    }
    while(count!=n-1)
    {
        for(i=0;i<n;i++)
        {
            counter+=arr[i];
            if(counter==3)//当计数君数到3时，把当前数组元素赋值为0避免再数到 
            {
                arr[i]=0;
                count++;
                counter=0;
            }
        }
    }
    for(i=0;i<n;i++)
    {
        if(arr[i]==1)
        {
            printf("%d",i+1);//这里千万记得要+1 
        }
    } 
    return 0;
}