乐正

Actions speak louder than words.

Sicp-ex2-43

问题

Louis Reasoner 在做练习2.42时遇到了麻烦,他的queens过程看起来能行,但却运行的极慢(Louis 居然无法忍耐到它解$6 \times 6$棋盘的问题)。当Louis请Eva Lu Ator帮忙时,她指出他在flatmap 里面交换了嵌套映射的顺序,将它写成了:

1
2
3
4
5
6
(flatmap
  (lambda (new-row)
    (map (lambda (rest-of-queens)
      (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
    (enumerate-interval 1 board-size))

请解释一下,为什么这样交换顺序会使程序运行得非常慢。估计一下,用Louis的程序去解决八皇后问题大约 需要多少时间,假定练习2.42中的程序需要用的时间为$T$求解这一难题。

解答

Louis的方案问题在重复计算$a_{n-1}$,然后$a_{n-1}$又重复计算$a_{n-2}$,如此反复。假定棋 盘为$k$列,则解决问题需要的时间是:$T^k$。

draft

« sicp-ex2-42 sicp-ex2-44 »

Comments