アルゴリズム論特論（塩田）第13回 (1) 数当てゲーム
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
数当てゲーム
まずは次のゲームで遊んでみてください。
セレクトボックスで数字を選んで「答」のボタンを押せば答が表示されます。
数当てゲーム ２桁の自然数をひとつ思い浮かべてください。
その数を当てて見せましょう。
２桁の数字をループで回して条件を満たす数を表示させてるだけじゃないの、
と思かもしれませんが、もっと巨大な数でもできます。
「乱数生成」ボタンで乱数で余りを設定したら「答」ボタンを押してください。
数当てゲーム 128-bit ver. $m_1$, $m_2$, $m_3$ で割った余りから数 $x$ を当てて見せます。
これだって、$x$ を先に作って余りを表示して、それらしく検算を書いてるだけじゃないの、
と思うかもしれませんが、入力欄は自分でも入力できますので、
違う数字を入れてみてください。
（$m_i$ を超える数字が入力されたら $m_i$ で割った余りに取り換えます。）
もはや全検索で求められるサイズではありませんが瞬時に答えが出ていますよね。
その仕組みを今日は勉強します。