ジョセフループ問題C++

ジョセフループ問題

問題説明

データ構造設定

プロセスコード

問題の説明
n人の子供は1周して、番号はそれぞれ1-nで、2番の子供は1番の子供の時計回りの方向に座って、3番の子供は2番の子供の時計回りの方向に座って......1番の子供はn番の子供の時計回りの方向に座っています;与えられた入力n,kに対して、1番目の子供からカウントを開始し、1番目の子供のカウントは1であり、次の子供はカウントが1増加するたびに、ある子供のカウントがkの整数倍またはカウントの桁数がkになったとき、その子供は淘汰される.最終的には1人の子供が残っていて、この子供は優勝者です.入力:n,k出力:優勝した子供の番号
データ構造による問題のシンプル化
問題を分析すると,記憶する必要があるのは子供の番号,子供の状態(淘汰されるかどうか),子供のカウントであり,環状構造はmod nを行うことによって実現される.したがって、構造体配列を選択してデータの格納を行います.
構造体の設定

    struct Item{
        int id;
        int num;
        bool state;
        Item(int _id,int _num,bool _state=true){
            id = _id;
            num = _num;
            state = _state;
        }
    };

プロセスコード
データ構造の適切な選択を経て、プロセスは極めて簡単になり、前の報数者と後の報数者の配列の下付きを見つけるだけでよい.2つの下付き文字が等しい場合、ゲームは終了します.完全なコードは次のとおりです.

    #include 
    #include 
    using namespace std;

    struct Item{
        int id;
        int num;
        bool state;
        Item(int _id,int _num,bool _state=true){
           id = _id;
            num = _num;
            state = _state;
        }
    };


    int main(){
    int n,k;
    cin >> n >> k;
    vector loop;
    for(int i=0;i1,0));
    int pre=0,next;
    loop[0].num = 1;
    while(1){
        next = (pre+1)%n;
        while(loop[next].state!=true)
            next = (next+1)%n;
        if(next==pre){
            cout << loop[next].id;
            return 0;
        }
        else{
            loop[next].num = loop[pre].num+1;
            if(loop[next].num%k==0 || loop[next].num%10==k)
                loop[next].state=false;
            pre = next;
        }
    }
}