『剣指offer』ジョセフリング問題

一、テーマの説明0, 1, ..., n - 1このnの数字は1つの円に並んでいて、数字0からこの円からm番目の数字を毎回削除します.この丸に残っている最後の数字を求めます.
入力:2個の整数n個とm個を含むデータのセットの行は、0個からn - 1個のシーケンスと、削除された第m個の数字をそれぞれ表す.
出力:
最後まで残る数字を出力します.
サンプル入力:

5 3

サンプル出力:

3

二、テーマ分析
古典的なジョセフリング問題では、最も簡単で乱暴な方法は、配列またはリングチェーンテーブルを使用して要素を削除するプロセス全体をシミュレートすることです.ここでは、標準ライブラリのlistを使用してリングチェーンテーブルを実現しています.遍歴するときは、反復器がチェーンテーブルの最後に遍歴するときに、チェーンテーブルの頭を再び指す必要があることに注意してください.
もう1つのネット上で議論されている多くの方法は、O(n)の時間的複雑さとO(1)の空間的複雑さを実現するために、数学的導出法を用いて繰返し式を求めることである.しかし、この導出過程は比較的困難で、ネット上の説明はたくさんあります.ここでは他の人の導出手順を引用します.
(1)n個の数からなるシーケンスについて,最初に削除された数は,(m - 1) % nであった.(2)2回目の削除を仮定すると,初期数字はm % nである.k = m % nとすると、残りのn - 1個の数に対して構成されるジョセフリングは、k, k + 1, k + 2, k +3, .....,k - 3, k - 2である.次のようにマッピングします.

k      ------>   0 
k+1    ------>   1 
k+2    ------>   2 
... 
... 
k-2    ------>   n-2 

すなわち、n - 1個のうちの1個の数kであり、n個の数に対応した場合の下付き符号は0である.したがって,n - 1個のシーケンスが最終的に最後に残る数をxとし,マッピング関係を逆プッシュすることでn個の数が得られる場合,最後に残る数は:(x + k) % nである.次のようになります.

(x + k) % n  
= (x + (m % n)) % n
= (x % n + (m % n) % n) % n
= (x % n + m % n) % n
= (x + m) % n

(3)同様に,2番目に削除された数:(m−1)%(n−1)を考慮する.(4)第3ラウンドの開始数字がpであると仮定すると、このn−2個の数からなるジョセフリングはp, p + 1, p + 2,..., p - 3, p - 2である.同様に、次のマッピングが得られます.

p      ------>   0 
p+1    ------>   1 
p+2    ------>   2 
... 
... 
p-2    ------>   n-3 

すなわち、n - 2個のうちの1個の数pであり、n - 1個の数に対応した場合の下付き符号は0である.n - 2個のシーケンスが最終的に最後に残る数をyとし、マッピング関係を逆プッシュしてn - 1個の数を得ることができる場合、最後に残る数は(y + p) % (n - 1)であり、そのうちpはm % (n - 1)に等しい.代入可得:(y + m) % (n - 1).
以上より,要求されたn個の数のシーケンスが最後に残した値は,n - 1個の数の解で求めることができることが分かった.1人しかいない場合、最後の数字は0です.以上より、以下の繰返し式が得られる.f[1] = 0; f[i] = (f[i -1] + m) % i;
繰返し式があれば,実現は非常に簡単で,サイクルの2つの実現方式を与える.標準ライブラリの使い勝手を改めて示します.
三、サンプルコード

#include <iostream>
#include <list>
using namespace std;

// The first method
// Link List of Josephus
int Josephus1(int n, int m)
{
    if (n < 1 || m < 1) return -1;
    list<int> circle;
    for (int i = 0; i < n; ++i)
        circle.push_back(i);

    list<int>::iterator it = circle.begin();
    while (circle.size() > 1)
    {
        for (int j = 0; j < m - 1; ++j)
            if (++it == circle.end()) it = circle.begin();

        list<int>::iterator del = it;
        if (++it == circle.end()) it = circle.begin();
        circle.erase(del);
    }
    return *it;
}

// The second method
int Josephus2(int n, int m)
{
    if (n < 1 || m < 1) return -1;
    int last = 0;
    for (int i = 2; i <= n; ++i)
        last = (last + m) % i;
    return last;
}

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    int result1 = Josephus1(n, m);
    int result2 = Josephus2(n, m);
    cout << "The first method, the last member is No: " << result1 << endl;
    cout << "The second method, the last member is No: " << result2 << endl;
    system("pause");
    return 0;
}

四、参考リンク
http://blog.csdn.net/wuzhekai1985/article/details/6628491