我正在学习sicp书,我对程序的替换模型有疑问:
(defn A
[x,y]
(cond (= y 0) 0
(= x 0) (* 2 y)
(= y 1) 2
:else (A (- x 1) (A x (- y 1)))))
此过程是练习 1.10 的一部分。 如果我使用以下参数 (A 1 10) 在 REPL 中运行该函数,结果是 1024。我决定使用替换模型验证结果,但结果是 2048。
这是我写的替代模型。有什么不对劲,但我不知道是什么。
(A 1 10)
(A (- 1 1) (A 1 (- 10 1))))
(A 0 (A 1 9)))
(A 0 (A (- 1 1) (A 1 (- 9 1)))))
(A 0 (A 0 (A 1 8))))
(A 0 (A 0 (A (- 1 1) (A 1 (- 8 1))))))
(A 0 (A 0 (A 0 (A 1 7)))))
(A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1)))))))
(A 0 (A 0 (A 0 (A 0 (A 1 6))))))
(A 0 (A 0 (A 0 (A 0 (A (-1 1) (A 1 (- 6 1))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (-1 1) (A 1 (- 5 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (-1 1) (A 1 (- 4 1)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (-1 1) (A 1 (-3 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (-1 1) (A 1 (- 2 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (* 2 32))))))
(A 0 (A 0 (A 0 (A 0 (A 0 64)))))
(A 0 (A 0 (A 0 (A 0 (* 2 64)))))
(A 0 (A 0 (A 0 (A 0 128))))
(A 0 (A 0 (A 0 (* 2 128))))
(A 0 (A 0 (A 0 256)))
(A 0 (A 0 (* 2 256)))
(A 0 (A 0 512))
(A 0 (* 2 512))
(A 0 1024)
2048 ????
谁能指出我做错了什么? 对于问题的长度,我深表歉意。
最佳答案
考虑这些行:
(A 0 (A 0 (A 0 (A 1 7)))))
(A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1)))))))
(A 0 (A 0 (A 0 (A 0 (A 1 6))))))
(A 0 (A 0 (A 0 (A 0 (A (-1 1) (A 1 (- 6 1))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))
剥掉多余的外层:
(A 1 7))
(A (- 1 1) (A 1 (- 7 1))))
(A 0 (A 1 6)))
(A 0 (A (-1 1) (A 1 (- 6 1)))))
(A 0 (A 0 (A 0 (A 1 5)))))
这里的某个地方你最终得到了不匹配的括号,但这并不重要。请注意,从 A 1 7
开始至A 1 6
,单个外层A 0 _
已创建,如预期。从 A 1 6
出发至A 1 5
,您已经有了两个新层 A 0 _
。其中每一个最终都会使结果加倍,所以这就是为什么你的答案偏离了 2 倍。
关于clojure - 使用 Clojure 帮助建立替换模型 [Sicp],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6673647/