ウツギ博士への電話における同一メッセージの最大連続数を求める

AbuseMaxChainDrUtsugi.cpp

#include <iostream>
#include <iomanip>

using namespace std;

// 次の乱数を取得
uint32_t next(uint32_t s) {
    return 0x41C64E6D * s + 0x00006073;
}

// 実乱数を取得
uint16_t r(uint32_t s) {
    return (uint16_t) (s >> 16);
}

// ``r[n] % 3``が連続で``n``になる回数を返す
int count_chain(uint32_t s_n, int n) {
    int count = 0;
    uint32_t s = s_n;
    while (r(s) % 3 == n) {
        count++;
        s = next(s);
    }
    return count;
}

int main(void) {
    cout << setw(12) << "r[n] % 3";
    cout << setw(12) << "max chain";
    cout << setw(12) << "S[n]" << endl;

    for (int i = 0; i < 3; i++) {
        int max_chain = 0;
        uint32_t max_chain_s = 0;

        // ``S[n]``を総当り
        for (uint64_t s_n = 0; s_n < 0x100000000; s_n++) {
            int chain = count_chain((uint32_t) s_n, i);
            if (chain > max_chain) {
                max_chain = chain;
                max_chain_s = (uint32_t) s_n;
            }
        }

        cout << setw(12) << dec << noshowbase << i;
        cout << setw(12) << dec << noshowbase << max_chain;
        cout << setw(12) << hex << uppercase << showbase << max_chain_s << endl;
    }


    return 0;
}