Hofstadter Q sequence: Difference between revisions
Go solution
(Add Seed7 example) |
(Go solution) |
||
Line 340:
print("value is smaller than previous $count times");
}</lang>
=={{header|Go}}==
Sure there are ways that run faster or handle larger numbers; for the task though, maps and recursion work just fine.
<lang 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))
}</lang>
Output:
<pre>
Q(1) = 1
Q(2) = 1
Q(3) = 2
Q(4) = 3
Q(5) = 3
Q(6) = 4
Q(7) = 5
Q(8) = 5
Q(9) = 6
Q(10) = 6
Q(1000) = 502
count: 49798
Q(1000000) = 512066
</pre>
=={{header|Icon}} and {{header|Unicon}}==
| |||