SICP 1.16 题 题解

2017年02月24日 |

blog

| sicp

• 题目描述
• 分析
• 源代码

刚刚做出来 sicp 里的 1.16 题，深有感触。看了一下网上的题解 ，并没有题目的分析过 程，因此把我的分析过程在这里记录了一下。

题目描述

根据书中给出的关系 ，并且使用一个不变量记录中间结果，写出对数步数内迭代计算幂的函数。

分析

题目中说到令 ，而 a 的初始值为 1，在最后 a 为运算的 结果（b 的 n 次方）。可得公式： 。因此推知迭代终点为 n = 0 。

令初始公式为 。

• 当 n = 0 时，迭代结束
• 当 n 为偶数时，可得 ，在结果中可以把 b² 看作新 的 b，把 n/2 看作新的 n，然后继续迭代
• 当 n 为奇数时，n-1 为偶数或者 0，有 ，可以把 a*b 看作新的 a，把 b^n-1 看作新的 b。

由此，所有的情况已经分析完毕。

源代码

#lang racket
(define (expt-iter b n a)
  [cond ([= n 0] a)
        ([even? n]
         (expt-iter (* b b) (/ n 2) a))
        (else
         (expt-iter b (- n 1) (* a b)))])

(define (expt b n)
  (expt-iter b n 1))