39 lines
763 B
Text
39 lines
763 B
Text
link printf
|
|
|
|
procedure main()
|
|
|
|
V := [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
|
|
every i := 1 to *V do
|
|
if Q(i) ~= V[i] then stop("Assertion failure for position ",i)
|
|
printf("Q(1 to %d) - verified.\n",*V)
|
|
|
|
q := Q(n := 1000)
|
|
v := 502
|
|
printf("Q[%d]=%d - %s.\n",n,v,if q = v then "verified" else "failed")
|
|
|
|
invcount := 0
|
|
every i := 2 to (n := 100000) do
|
|
if Q(i) < Q(i-1) then {
|
|
printf("Q(%d)=%d < Q(%d)=%d\n",i,Q(i),i-1,Q(i-1))
|
|
invcount +:= 1
|
|
}
|
|
printf("There were %d inversions in Q up to %d\n",invcount,n)
|
|
end
|
|
|
|
|
|
|
|
procedure Q(n) #: Hofstader Q sequence
|
|
static S
|
|
initial S := [1,1]
|
|
|
|
if q := S[n] then return q
|
|
else {
|
|
q := Q(n - Q(n - 1)) + Q(n - Q(n - 2))
|
|
if *S = n - 1 then {
|
|
put(S,q)
|
|
return q
|
|
}
|
|
else
|
|
runerr(500,n)
|
|
}
|
|
end
|