Exercise 3.56 · 习题

Exercise 3.56: A famous problem, first raised by
R. Hamming, is to enumerate, in ascending order with no repetitions, all
positive integers with no prime factors other than 2, 3, or 5. One obvious way
to do this is to simply test each integer in turn to see whether it has any
factors other than 2, 3, and 5. But this is very inefficient, since, as the
integers get larger, fewer and fewer of them fit the requirement. As an
alternative, let us call the required stream of numbers S and notice the
following facts about it.

S begins with 1.

The elements of (scale-stream S 2) are also
elements of S.

The same is true for (scale-stream S 3)
and (scale-stream S 5).

These are all the elements of S.

Now all we have to do is combine elements from these sources. For this we
define a procedure merge that combines two ordered streams into one
ordered result stream, eliminating repetitions:

(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond (( s1car s2car)
(cons-stream
s1car
(merge (stream-cdr s1)
s2)))
((> s1car s2car)
(cons-stream
s2car
(merge s1
(stream-cdr s2))))
(else
(cons-stream
s1car
(merge
(stream-cdr s1)
(stream-cdr s2)))))))))

Then the required stream may be constructed with merge, as follows:

(define S (cons-stream 1 (merge ⟨??⟩ ⟨??⟩)))

Fill in the missing expressions in the places marked ⟨??⟩ above.

练习 3.56：R. Hamming 最先提出的一个著名问题是：按升序且不重复地枚举所有除 2、3、5 之外没有其他质因数的正整数。一种显而易见的做法是依次检验每个整数，看它是否只含 2、3、5 这三个质因数。但这非常低效，因为随着整数增大，满足要求的数越来越稀少。作为替代，设所求的数流为 S，注意以下事实：

S 以 1 开头。

(scale-stream S 2) 的各元素也是 S 的元素。

(scale-stream S 3) 和 (scale-stream S 5) 亦然。

这些就是 S 的全部元素。

现在只需将这些来源的元素合并。为此，我们定义过程 merge，它将两个有序流合并为一个有序结果流，并消除重复：

(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond (( s1car s2car)
(cons-stream
s1car
(merge (stream-cdr s1)
s2)))
((> s1car s2car)
(cons-stream
s2car
(merge s1
(stream-cdr s2))))
(else
(cons-stream
s1car
(merge
(stream-cdr s1)
(stream-cdr s2)))))))))

然后可用 merge 构造所求的流：

(define S (cons-stream 1 (merge ⟨??⟩ ⟨??⟩)))

填入上面 ⟨??⟩ 处缺少的表达式。