アルゴリズムとは 年齢当てゲーム、候補の数、二分探索法、最大回数
問題解決力を鍛える!アルゴリズムとデータ構造 (大槻 兼資(著)、秋葉 拓哉(監修)、講談社)の第1章(アルゴリズムとは)、章末問題1.2の解答をGoで求めてみる。
6回の質問で確実に当てることはできない。
7回の質問で確実に当てることができる。
実際に問題1のコードを修正して全ての場合で質問の回数を数えてみる。
コード
package main
import "fmt"
func main() {
counts := map[int]int{}
for age := 0; age < 100; age++ {
lower, upper := 0, 99
count := 0
var mid int
for {
count++
mid = (lower + upper + 1) / 2
if age < mid {
upper = mid - 1
} else {
lower = mid
}
if lower == upper {
counts[age] = count
break
}
}
}
for age := 0; age < 100; age++ {
fmt.Printf("%2d歳 %v回\n", age, counts[age])
}
}
入出力結果
% go run ./main.go
0歳 6回
1歳 7回
2歳 7回
3歳 6回
4歳 7回
5歳 7回
6歳 6回
7歳 7回
8歳 7回
9歳 6回
10歳 7回
11歳 7回
12歳 6回
13歳 7回
14歳 7回
15歳 6回
16歳 7回
17歳 7回
18歳 6回
19歳 7回
20歳 7回
21歳 7回
22歳 7回
23歳 7回
24歳 7回
25歳 6回
26歳 7回
27歳 7回
28歳 6回
29歳 7回
30歳 7回
31歳 6回
32歳 7回
33歳 7回
34歳 6回
35歳 7回
36歳 7回
37歳 6回
38歳 7回
39歳 7回
40歳 6回
41歳 7回
42歳 7回
43歳 6回
44歳 7回
45歳 7回
46歳 7回
47歳 7回
48歳 7回
49歳 7回
50歳 6回
51歳 7回
52歳 7回
53歳 6回
54歳 7回
55歳 7回
56歳 6回
57歳 7回
58歳 7回
59歳 6回
60歳 7回
61歳 7回
62歳 6回
63歳 7回
64歳 7回
65歳 6回
66歳 7回
67歳 7回
68歳 6回
69歳 7回
70歳 7回
71歳 7回
72歳 7回
73歳 7回
74歳 7回
75歳 6回
76歳 7回
77歳 7回
78歳 6回
79歳 7回
80歳 7回
81歳 6回
82歳 7回
83歳 7回
84歳 6回
85歳 7回
86歳 7回
87歳 6回
88歳 7回
89歳 7回
90歳 6回
91歳 7回
92歳 7回
93歳 6回
94歳 7回
95歳 7回
96歳 7回
97歳 7回
98歳 7回
99歳 7回
%