46 lines
676 B
Go
46 lines
676 B
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
var m map[int]int
|
|
|
|
func initMap() {
|
|
m = make(map[int]int)
|
|
m[1] = 1
|
|
m[2] = 1
|
|
}
|
|
|
|
func q(n int) (r int) {
|
|
if r = m[n]; r == 0 {
|
|
r = q(n-q(n-1)) + q(n-q(n-2))
|
|
m[n] = r
|
|
}
|
|
return
|
|
}
|
|
|
|
func main() {
|
|
initMap()
|
|
// task
|
|
for n := 1; n <= 10; n++ {
|
|
showQ(n)
|
|
}
|
|
// task
|
|
showQ(1000)
|
|
// extra credit
|
|
count, p := 0, 1
|
|
for n := 2; n <= 1e5; n++ {
|
|
qn := q(n)
|
|
if qn < p {
|
|
count++
|
|
}
|
|
p = qn
|
|
}
|
|
fmt.Println("count:", count)
|
|
// extra credit
|
|
initMap()
|
|
showQ(1e6)
|
|
}
|
|
|
|
func showQ(n int) {
|
|
fmt.Printf("Q(%d) = %d\n", n, q(n))
|
|
}
|