Scheme - 手続きとその生成するプロセス(増加の程度)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.3(増加の程度)の問題1.14を解いてみる。

問題 1.14.

バランスよくは書けてないけど、木構造完成。(Google ドキュメントの図形描画で作成してフォーマットはsvgでダウンロード、そして埋め込んでみたけど線がずれた。。試しにjpegもダウンロードしてみたけど同様にずれた。(図形中のテキストの影響なのかな。)なので、スクリーンショットを埋め込むことに。)

使用する硬貨を10セント、5セント、1セントの3種類、最初の種類の硬貨は順に10セント、5セント、1セントで考えながら作成。

ちゃんと4通りになった(赤でチェックした部分)ので、構造は正しく書けたみたい。

このプロセスが使うスペース数の増加の程度はΘ(n)。

このプロセスが使うステップ数の増加の程度はΘ(n^コインの種類)。