*[[Problem 527:https://projecteuler.net/problem=527]] 「ランダム化された二部探索」 [#n482730e]
秘密の整数 '''t''' が範囲 1 ≤ '''t''' ≤ '''n''' の中からランダムで選択されている.
整数 '''g''' を使って推測を繰り返すことで, '''t''' の値を当てるのが今回の目的だ. 推測を行った後には, 3 つの結果が起こり得る, つまり '''g''' < '''t''', '''g''' = '''t''', あるいは '''g''' > '''t''' かのいずれかが明らかとなる.
通常, 平均的に必要とされる推測の回数は二分探索で最小化することができる. 下界 '''L''', 上界 '''H''' (L = 1, H = n に初期化されている) が与えられているとき, g = ⌊('''L'''+'''H''')/2⌋ としよう, ここで ⌊⋅⌋ は整数床関数とする. もし '''g''' = '''t''' ならば, 作業は終了する. そうでない場合, もし '''g''' < '''t''' なら, '''L''' = '''g'''+1 と設定する. '''g''' > '''t''' であれば, '''H''' = '''g'''−1 に設定する. 新しい範囲が設定された後, 探索作業を繰り返し, '''t''' がひとたび見つかれば作業は完全に終了する. たとえ '''t''' を探索すること無く見つけても, その探索では値を確かめる何らかの作業が必要であると仮定する.
友人のボブは, 標準的な二分探索よりも彼が考えるランダム化バージョンの二分探索のほうが優れていると信じている. その方法は, '''g''' = ⌊('''L'''+'''H''')/2⌋ に設定するのではなく, '''g''' を '''L''' から '''H''' までの（それぞれ '''L''', '''H''' 自身を含んだ）ランダムな値にただ設定する. 残りのアルゴリズムは標準の二分探索と同様だ. この新しい検索ルーチンは「ランダム二分探索」と呼ばれる.
1 ≤ '''t''' ≤ '''n''' となるようなランダムの値 '''t''' が与えられ, 標準的な二分探索による推測回数の期待値を '''B'''('''n''') とし, ランダム二分探索による推測回数の期待値を '''R'''('''n''') としよう. 例えば, 小数点以下 8 桁となるよう四捨五入すると, '''B'''(6) = 2.33333333, '''R'''(6) = 2.71666667 となる.
'''R'''(10&sup{10};) − '''B'''(10&sup{10};) を求め, 小数点以下 8 桁となるよう四捨五入して答えよ.
![[PukiWiki]](edit.png "[PukiWiki]")
