2010-08-11から1日間の記事一覧
問題 順序づけられたリストによる集合表現の union-set を、Θ(n) で実装せよ。 解答 intersection-set と同じ感じでやってみよう。 (define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) (else (let ((x1 (car set1)) (x2 (car set…
問題 順序づけられた表現を使った adjoin-set の実装を示せ。 element-of-set? の類推で、順序付けられない表現に比べ、約半分のステップ数を必要とする手続を作るのに、順序の利点をどう用いるか示せ。 解答 element-of-set? の類推でいいんだからこんな感…
このセクションでは集合演算を加速(効率化?)するための内容が記載されている。 概略としては、要素をなんらかの規則(シンボルなら辞書順、あるいは要素に数値を付加するなりしてその大きさ順等)整列させて考えてみようという話。ここでは話を簡単にする…