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