C语言程序设计基础|约瑟夫环

题目描述：

有n个人围成一个圈，从第一个人开始顺序报号1，2，3。凡是报到3退出圈子中的人原来的序号。要求打印出退出人的序号。以及找出最后留在圈子中的人原来的序号。

输入要求：

输入n

输出要求：

退出人的序号，并找出最后留在圈子里的人原来的序号

#include<iostream>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n], brr[n], count, circal, xin;
    count = 0;//用来记报数，从而依次找出报3的倍数的位置
    circal = 0;//化圈为直线，一直对n取余，从而不断来回
    xin = 0;
    for (int i = 0; i < n; i++)
    {
        arr[i] = i + 1;//编号是从1开始排
    }
    while (xin < n)//当还退出的人数小于总人数时执行循环
    {
        if (arr[circal % n] != 0)//如果目前所在的位置不是0就报数，是0就跳过
        {
            count++;//报数
            if (count % 3 == 0)//在圈子中报到3就退出相当于在一排中报到3的倍数就退出
            {
                brr[xin] = arr[circal % n];//将报到3的倍数位置上的数传递给另一个数组
                arr[circal % n] = 0;//原位置清零
                xin++;//退出的数+1
            }
        }
        circal++;//圈子不断向后走
    }
    for (int i = 0; i < n - 1; i++)
    {
        cout << brr[i] << " ";
    }
    cout << endl;
    cout << brr[n - 1];
    return 0;
}

本题的思路就是将圈子化为直线，不断进行排列，从而找到符合条件的数……

如果将3改为任意数，可以依次找到报任意数的位置，代码如下：

#include<iostream>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int arr[n], brr[n], count, circal, xin;
    count = 0;//用来记报数，从而依次找出报3的倍数的位置
    circal = 0;//化圈为直线，一直对n取余，从而不断来回
    xin = 0;
    for (int i = 0; i < n; i++)
    {
        arr[i] = i + 1;//编号是从1开始排
    }
    while (xin < n)//当还退出的人数小于总人数时执行循环
    {
        if (arr[circal % n] != 0)//如果目前所在的位置不是0就报数，是0就跳过
        {
            count++;//报数
            if (count % x == 0)//在圈子中报到x就退出相当于在一排中报到x的倍数就退出
            {
                brr[xin] = arr[circal % n];//将报到x的倍数位置上的数传递给另一个数组
                arr[circal % n] = 0;//原位置清零
                xin++;//退出的数+1
            }
        }
        circal++;//圈子不断向后走
    }
    for (int i = 0; i < n - 1; i++)
    {
        cout << brr[i] << " ";
    }
    cout << endl;
    cout << brr[n - 1];
    return 0;
}