Scheme - 超言語的抽象(Schemeの変形 - 非決定性計算(ambと探索(駆動ループ(効率よくPythagoras三角形を生成する手続き))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.3(Schemeの変形 - 非決定性計算)、4.3.1(ambと探索)、駆動ループ、問題 4.37.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 4.37.

lowを3、highを5としたときに、調べなければならない可能性の数を調べてみる。

問題4.35のPythagorass三角形の生成方法の場合。

(i, j, k)とする。

1. (3, 3, 3) 失敗
2. (3, 3, 4) 失敗
3. (3, 3, 5) 失敗
4. (3, 4, 4) 失敗
5. (3, 4, 5) Pythagorasの三角形
6. (3, 5, 5) 失敗
7. (4, 4, 4) 失敗
8. (4, 4, 5) 失敗
9. (4, 5, 5) 失敗
10. (5, 5, 5) 失敗

Ben BitdiddleのPythagorass三角形の生成方法の場合。

1. (3, 3, 3√2)失敗
2. (3, 4, 5) Pythagorasの三角形
3. (3, 5, ) 失敗
4. (4, 4, ) 失敗
5. (4, 5, ) 失敗
6. (5, 5, ) 失敗

よってBen BitdiddleのPythagoras三角形を生成する方法の法が問題4.35のものよりずっと効率が良い。