Namaran

Code daily. Without assist.

2026-09-05

random_height.cpp

#include <iostream>
#include <random>

int random_height(std::mt19937 rng) {
    int h = 1;
    while (h < 4 && rng() % 2 == 1) ++h;
    return h;
}

int main() {
    std::mt19937 rng;
    for (int i = 0; i < 8; ++i) std::cout << random_height(rng);
    std::cout << '\n';
}

スキップリストに入れるノードの高さを、乱数が奇数の間だけ1段ずつ上げて決める random_height です(上限は4段)。8個のノードの高さを続けて出すと、いまは 11111111 と出ます。本来は 11124141 です。

Answer

Wrong

int random_height(std::mt19937 rng) {

rng を値で受け取っているので、呼ぶたびに main の rng のコピーが作られます。std::mt19937 は内部状態をまるごと持つ普通の値の型で、コピーは元と同じ状態から始まります。random_height の中の rng() が進めるのはコピーの状態だけで、main の rng は一度も進みません。8回とも同じ乱数列の先頭から読むことになり、既定の種で作った列は最初の値が偶数なので、どれも高さ 1 です。

既定の種がいつも同じだからと考えて std::random_device で種を与えても、直りません。実行するたびに列は変わりますが、1回の実行の中ではやはりすべてのノードが同じ高さになります。高さがそろうと、どの段も同じノードを並べるだけになり、上の段で区間を飛ばせないので、探索は最下段を1つずつたどるのと変わらなくなります。

Right

int random_height(std::mt19937& rng) {

参照で受け取れば、rng() が進めるのは main の rng そのものの状態です。呼ぶたびに乱数列の続きを読むので、高さがばらつきます1。

  1. std::mt19937 の既定の種は 5489 で、生成器がそのまま返す値の列は規格で決まっています。規格は、既定の状態で作った生成器の10000回目の出力が 4123659995 であることまで求めています。一方、std::bernoulli_distribution などの分布クラスの計算方法は処理系ごとに違ってよいので、ここでは rng() % 2 で奇数かどうかを見ています。