SDNU 1263.C语言程序设计教程（第三版）课后习题10.5（约瑟夫环）

Description

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

Input

初始人数n

Output

最后一人的初始编号

Sample Input

3

Sample Output

2

Source

Unknown

///
///                            _ooOoo_
///                           o8888888o
///                           88" . "88
///                           (| -_- |)
///                           O\  =  /O
///                        ____/`---‘\____
///                      .‘  \\|     |//  `.
///                     /  \\|||  :  |||//  ///                    /  _||||| -:- |||||-  ///                    |   | \\\  -  /// |   |
///                    | \_|  ‘‘\---/‘‘  |   |
///                    \  .-\__  `-`  ___/-. /
///                  ___`. .‘  /--.--\  `. . __
///               ."" ‘<  `.___\_<|>_/___.‘  >‘"".
///              | | :  `- \`.;`\ _ /`;.`/ - ` : | |
///              \  \ `-.   \_ __\ /__ _/   .-` /  /
///         ======`-.____`-.___\_____/___.-`____.-‘======
///                            `=---=‘
///        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
///                      Buddha Bless, No Bug !
///
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define ll long long

int n, num = 0, sum = 0, id;
bool sign[1000000+8];

int main()
{
    num = 0, sum = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        sign[i] = 1;
    id = 0;
    while(sum < (n - 1))
    {
        if(sign[id])num++;
        if(num == 3)
        {
            sign[id] = 0;
            num = 0;
            sum++;
        }
        id++;
        if(id == n)id = 0;
    }
    for(int i = id; i < n; i++)
        if(!sign[id])
            id++;
        else
            break;
    printf("%d\n", id + 1);

    return 0;
}