たまたま見つけたネタ。
タイトルが長くなったので省略しちゃったけど、ちゃんと引用すると、こう。
フィボナッチ数列のうち、各桁の数字を足した数で割り切れる数を以下の例に続けて小さいほうから5個求めてください。2 → 2 ÷ 2
3 → 3 ÷ 3
5 → 5 ÷ 5
8 → 8 ÷ 8
21 → 21 ÷ 3・・・2 + 1= 3で割る
144 → 144 ÷ 9・・・1 + 4 + 4 = 9で割る
引用してもわかりにくいな。要するに、フィボナッチ数列を {Fn} （n=0,1,2…）として、Fn の各桁の数を足し合わせたものを S(Fn) とすると、S(Fn) で割り切れる Fn を小さい順に5つ（ただし、例に出ている 114 までを除く）求めよ、ってことだ。
「 これはメモ化と大きな桁を扱う事についての問題です 」なんて書いてあるけど、大きな桁はその通りだけど、n から Fn を求めようとするからメモ化なんかが必要になるんであって、この問題では小さい順に調べればいいんだから素直にフィボナッチ数列の頭から生成すればいい。
というわけで、Go でやってみた。ただやってみるだけじゃなくて、あんまり使ったことのないゴルーチンとチャネルを使ってみたよ。
まずは単純にフィボナッチ数列を生成するところから。
package main
import (
"fmt"
)
func main() {
s := makeFib()
for i := 0; i < 10; i++ {
f := <- s
fmt.Println(f)
}
}
type Stream chan int
func makeFib() Stream {
s := make(Stream)
go func() {
a, b := 0, 1
for {
f := a
a, b = b, a + b
s <- f
}
}()
return s
}
関数 makeFib は、チャネルを返す。で、このチャネルからフィボナッチ数列を一つずつ取り出せる。makeFib の中のゴルーチンは無限ループになっているので、（アルゴリズム上は）無限に取り出すことができる（実際はどうだかわからない）。実行結果は次の通り。
^o^ > go run fib_chan.go
0
1
1
2
3
5
8
13
21
34
さて、それじゃ本題に入ろう。といってもフィボナッチ数列はもう得られているんだから、あとは条件に合う数 Fn を5つ出力するだけだ。こうなった。
package main
import (
"fmt"
)
func main() {
s := makeFib()
i := 0
for i < 5 {
f := <- s
if f > 144 && isDivisible(f) {
i++
fmt.Println(f)
}
}
}
type Stream chan int
func makeFib() Stream {
s := make(Stream)
go func() {
a, b := 0, 1
for {
f := a
a, b = b, a + b
s <- f
}
}()
return s
}
func sumOfPlaces(n int) int {
sum := 0
for n > 0 {
sum += n % 10
n /= 10
}
return sum
}
func isDivisible(n int) bool {
return (n % sumOfPlaces(n)) == 0
}
実行結果。
^o^ > go run fib_divisible.go
2584
14930352
86267571272
498454011879264
160500643816367088
OK。ちゃんとできた。