约瑟夫环问题

ACM模版

约瑟夫环问题

/* * n个人(编号 1...n),先去掉第m个数,然后从m+1个开始报1, * 报到k的退出,剩下的人继续从1开始报数.求胜利者的编号. */

int main(int argc, const char * argv[])
{
    int n, k, m;
    while (cin >> n >> k >> m, n || k || m)
    {
        int i, d, s = 0;
        for (i = 2; i <= n; i++)
        {
            s = (s + k) % i;
        }
        k = k % n;
        if (k == 0)
        {
            k = n;
        }
        d = (s + 1) + (m - k);
        if (d >= 1 && d <= n)
        {
            cout << d << '\n';
        }
        else if (d < 1)
        {
            cout << n + d << '\n';
        }
        else if (d > n)
        {
            cout << d % n << '\n';
        }
    }

    return 0;
}

函数图像法

/* * n 个人数到 k 出列，最后剩下的人编号 */
unsigned long long n, k;

int main()
{
    cin >> n >> k;

    long long y = k % 2;
    long long x = 2, t = 0;
    long long z1 = y, z2 = x;
    while (x <= n)
    {
        z1 = y;
        z2 = x;
        t = (x - y) / (k - 1);
        if (t == 0)
        {
            t++;
        }
        y = y + t * k - ((y + t * k) / (x + t)) * (x + t);
        x += t;
    }

    cout << (z1 + (n - z2) * k) % n + 1 << endl;

    return 0;
}