アルゴリズムとは 年齢当てゲーム、二分探索法
問題解決力を鍛える!アルゴリズムとデータ構造 (大槻 兼資(著)、秋葉 拓哉(監修)、講談社)の第1章(アルゴリズムとは)、章末問題1.1の解答をGoで求めてみる。
コード
package main
import "fmt"
func main() {
for age := 20; age < 36; age++ {
fmt.Printf("%v歳\n", age)
lower, upper := 20, 35
var mid int
for {
mid = (lower + upper + 1) / 2
fmt.Printf("\t質問 : 「%v歳未満ですか？」\n", mid)
if age < mid {
fmt.Printf("\tAさん: 「はい。」\n")
upper = mid - 1
} else {
fmt.Printf("\tAさん: 「いいえ。」\n")
lower = mid
}
if lower == upper {
fmt.Printf("\t質問 : 「%v歳ですね！\n", lower)
if age == lower {
fmt.Print("\tAさん: 「正解です。」\n")
} else {
fmt.Print("\tAさん: 「不正解です。」\n")
}
break
}
}
}
}
入出力結果
% go run ./main.go
20歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「はい。」
質問 : 「22歳未満ですか？」
Aさん: 「はい。」
質問 : 「21歳未満ですか？」
Aさん: 「はい。」
質問 : 「20歳ですね！
Aさん: 「正解です。」
21歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「はい。」
質問 : 「22歳未満ですか？」
Aさん: 「はい。」
質問 : 「21歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「21歳ですね！
Aさん: 「正解です。」
22歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「はい。」
質問 : 「22歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「23歳未満ですか？」
Aさん: 「はい。」
質問 : 「22歳ですね！
Aさん: 「正解です。」
23歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「はい。」
質問 : 「22歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「23歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「23歳ですね！
Aさん: 「正解です。」
24歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「26歳未満ですか？」
Aさん: 「はい。」
質問 : 「25歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳ですね！
Aさん: 「正解です。」
25歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「26歳未満ですか？」
Aさん: 「はい。」
質問 : 「25歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「25歳ですね！
Aさん: 「正解です。」
26歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「26歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「27歳未満ですか？」
Aさん: 「はい。」
質問 : 「26歳ですね！
Aさん: 「正解です。」
27歳
質問 : 「28歳未満ですか？」
Aさん: 「はい。」
質問 : 「24歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「26歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「27歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「27歳ですね！
Aさん: 「正解です。」
28歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「はい。」
質問 : 「30歳未満ですか？」
Aさん: 「はい。」
質問 : 「29歳未満ですか？」
Aさん: 「はい。」
質問 : 「28歳ですね！
Aさん: 「正解です。」
29歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「はい。」
質問 : 「30歳未満ですか？」
Aさん: 「はい。」
質問 : 「29歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「29歳ですね！
Aさん: 「正解です。」
30歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「はい。」
質問 : 「30歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「31歳未満ですか？」
Aさん: 「はい。」
質問 : 「30歳ですね！
Aさん: 「正解です。」
31歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「はい。」
質問 : 「30歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「31歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「31歳ですね！
Aさん: 「正解です。」
32歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「34歳未満ですか？」
Aさん: 「はい。」
質問 : 「33歳未満ですか？」
Aさん: 「はい。」
質問 : 「32歳ですね！
Aさん: 「正解です。」
33歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「34歳未満ですか？」
Aさん: 「はい。」
質問 : 「33歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「33歳ですね！
Aさん: 「正解です。」
34歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「34歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「35歳未満ですか？」
Aさん: 「はい。」
質問 : 「34歳ですね！
Aさん: 「正解です。」
35歳
質問 : 「28歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「32歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「34歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「35歳未満ですか？」
Aさん: 「いいえ。」
質問 : 「35歳ですね！
Aさん: 「正解です。」
%