sicp
問題はaとbの二つ。分かんない手続き名が出てきたので調べる quotientは商を求める事が出来ます。a の答えの動作としては例として、(list 1 3 5 7 9 11)の場合をかきます。partial-treeにかける。 lengthは6なので、left-sizeが2になる。 で、left-resultのp…
問題はaとbの二つ。 aは実際、写経して実行してみると分かる。 普通にリストに変換される。 bの議論は 再帰をもちいるか反復を用いるかの違い議論みたいなもんだと思う。 と思ったけど、結局左から順に処理してるだけなのでどちらもθ(n)っぽい。 これの読書…
問題が単純に書かれ過ぎているし、θ(n)でとか書かれると一瞬ひるむが、 要は今までの流れで問題を解けば良いのだなと思う。 もうちょっというと、p90のintersection-setをパクれば良い。 実装には他の順序づけされた実装も書いておく。 大体にたようなパター…
そんなに難しい問題ではない。 ほとんどの答えが、既にこの問題の前に書いてある。教科書P90に書いてる説明が、順序の利点の答え 最悪の場合、探している者は集合の最大の要素かもしれず、ステップ数は順序づけられていない表現と同じである。ところが、異な…
この問題はθ(n)の手続きをいくつも使ってやっていく。 変な書き方だけど θ(n) = θ(n) + θ(n) + θ(n) だから、いくら使ってもオッケーだ!! そういう訳で、P90のintersection-setと 問題2.62のunion-setを利用する。 戦略としては ・木構造->順序づけられた…
そんなに難しい問題ではない。 重複を考えないぶん、簡単だ。 実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) (define nil '()) (define (element-of-set? x set) (cond ((null? set) #f) ((equal? x (ca…
そんなに難しい問題ではない。 基本的な考え方は、今までやってきたappendとかと大してかわらない。 重複がなければリストに付け加えていけば良いだけ。 実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) (…
aとb二つ問題がある。aの方は、 make-ホニャララ的な手続きと、 ホニャララ?的な判断する手続き、 あと、 加数と乗数の取り出す手続き を修正すれば出来ると思う。 bの方は、多分設計できそうで、 最初に式全体をなめて*が出てきたら、括弧で囲んでやるよう…
これは、要はaugendとmultiplicandの定義を変更して、 (+ 1 2 x) (* 1 2 x) みたいな扱いも出来るように仕様っていうこと。 で、さらにいうと (augend '(+ 1 2 x)) を実行すると (+ 2 x)が返るようにしてやれば良い。 consの定義を考えてやれば、三項目以降…
教科書に書いてある式を書いてみた。 (tex記法が使える事をid:ajiyoshiに教わった。thanks!!!) この式を、 exponentiation?とか、base、exponentとかmake-exponentiation とか、この前の説明のところでやった手続きが、既にあると希望的に考えたうえで、 表…
なかなか面白い。 「''」が内部的にどういう解釈になっているのかわかればいいのかな? って感じでやってみた。 まず、 (car ''abracadabra)と入力した、驚いたことに解釈系はquoteと印字してきた.なぜか. ってあるんだけど、実際にやってみるとそのようにな…
あわよくば髪を切りにいきたいので、問題の後半をあまりよんでいない。 でも、多分出来ているので出来ているのだろうという意味の分からん自信。 P84のmemqの実装を参考にすると分かりやすいと思います。 実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -…
とりあえず、特に難しい事はないので、書いてある通りやる。 出力の予想もあっていたので、とても嬉しい。実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) (define (memq item x) (cond ((null? x) faluse…
実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) (define nil '()) (define (square n) (* n n)) ;;prime? の実装 (define (smallest-divisor n) (find-divisor n 2)) (define (divides? a b) (= (remaind…
このときの俺、実行結果にコメントを書くのが流行っていたようだ。 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) (define nil '()) (define (accumulate op initial sequence) (if (null? sequence) initial…
たしかポイントは、行と列をどうやって表すか?的なような事だったような気がする。 あとは、safeはけっこうごちゃごちゃやらないといけない。ので凄く難しい。 実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-ra…
この問題は虫食い問題。 で、ポイントは、listはペア同士をくっつけたヤツなんだけど、 それがどういう風な構成になっていれば良いのかっていう事を 知っていれば出来ると思う。 consでいくか、appendをつかうか。みたいな。 あとはリストの左から評価される…
この問題は2つやる事がある。 1. 本に書いてある関数を実装して試してみる。 2. fold-leftと、fold-rightが、どのような並びに対しても、同じ値を生じるためにopが満たすべき性質は何か、考える。 「1」の方は実際に試してみれば分かるのだが、 fold-rigth、…
この問題はいろいろ調べた。 そもそも行列の計算方法をうっかりわすれていたから、 問題をみてもあまりピンとこなかったからだ。 手続きの名前をみて matrixは行列 vectorは列 ってのにピンとくればわりかし楽ちん。 あと、問題の順番がちゃんとしてるので、…
この問題は結構好きな問題で、「ハッ!」っとすることがおおかった。 いままでのながれの例に漏れず虫食いの問題です。 ポイントとしては ( (1 2 3) (4 5 6) (7 8 9) (10 11 12)) というリストの、1と4と7と10をどうやって取り出すか?ってことかな。 これは…
この問題も穴埋めです。 またまたaccumulateをよく見ながら考えてみる。 問題をよくみると、mapがある。 虫食いは4つ。 僕の考え方はこんな感じ。 mapの中で受け取ったリストのすべての数字を一旦「1」に変換しちゃう。 また、リストのなかにはいっているリ…
この問題も穴埋めだ。 そしてこの問題もaccumulateとにらめっこすることになる。 ポイントは、accumulateは一回展開してから戻ってくる(自分にしか分からない表現)。 再帰プロセスをとる。 あとは記載されているHornerの方法を頭に入れた方がいい。 なにを言…
この問題は、そもそも map、append、lengthがどういう手続きか知らないと出来ない。 それは理解してると前提にする。 あとaccumulateの定義は説明のページに書いてあるので写す。 (define (accumulate op initial sequence) (if (null? sequence) initial (o…
この問題も大して難しくない。 そもそも「抽象化」し、とか難しそうに書いているけど、 前の問題のmap使ってる方の「*」ってなっているところを、 引数として取得した手続きを使えるようにすればいいだけだ。 実装 #!/usr/local/bin/gosh ;; -*- coding: utf…
この問題、問題は単純だけど句読点の場所とかを意識しないと問題がうまく読めない。 求める答えは以下の2つでいいと思う。 ・square-treeを直接に定義する。 ・square-treeをmapと再帰を使って定義する。 何を僕がとち狂っているのかというと、 直接バージョ…
こんな問題は簡単だ。(と思っていたら難しかった。) 受験勉強的には。 要は、穴埋め問題なんだけど、 (define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map rest))))) のって部分を埋めて、 (1 2 3) って集合か…
題意としては、 ・深いとこまでreverseしちゃう手続き、deep-reverseを定義 出力する値の例は問題に乗っているので割愛。 ちょっと本気で考えて、append使わない版もつくってみたよ。 んでは、実装 #!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- ;;2.18 (…
題意としては、 ・リストの中にリストがはいってたとしても、平坦にして出力しちゃうような手続きfringeを書く。たとえば、 ((1 2 3) (4 5) (6 (7 8)) 9)みたいなリストがあったときに (1 2 3 4 5 6 7 8 9)ってりすとが返ってくる手続きを作ればいい。 んで…
二進モービルの問題。ググってもこんなのしか出てこない。 http://d.hatena.ne.jp/nTeTs/20090716 ヒャッハーとか言ってるので、id:nTeTsにはトラックの免許を上げた方がいい。 もし俺が国王であったら、彼にのみトラックの免許をあたえて、 すっかすかの環…
絵を書く問題。ま、ま、ま。