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(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.5(ストリーム)、3.53(ストリームパラダイムの開発)、対の無限のストリーム、問題 3.66を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 3.66

1. (1, 1)
2. (1, 2)
3. (2, 2)
4. (1, 3)
5. (2, 3)
6. (1, 4)
7. (3, 3)
8. (1, 5)
9. (2, 4)
10. (1, 6)
11. (3, 4)
12. (1, 7)
13. (2, 5)
14. (1, 8)
15. (4, 4)
16. (1, 9)
17. (2, 6)
18. (1, 10)
19. (3, 5)
20. (1, 11)
21. (2, 7)
22. (1, 12)
23. (4, 5)
24. (1, 13)
25. (2, 8)
26. (1, 14)
27. (3, 6)
28. (1, 15)
29. (2, 9)
30. (1, 16)
31. (5, 5)

定性的な答え。

i = 1の場合、1, 2, 4, 6, 8, 10, … , 2 * (j - 1) (j >= 2)番目。(j = 1, 2, …)

i = 2の場合、3, 5, 9, 13, 17, … 番目。(j = 2, 3, …)

i = 3の場合、7, 11, 19, 27, … 番目。(j = 3, 4, …)

i = 4の場合、15, 23, … 番目。(j = 4, 5, …)

i = 5の場合、31, … 番目。(j = 5, 6, …)

j = iの場合、1, 3, 7, 15, 31, … , 2 * 2^(i - 1) - 1。

j = i + 1の場合、2, 5, 11, 23, … , 3 * 2^(i - 1) - 1。

j = i + 2の場合、4, 9, 19, … , 5 * 2^(i - 1) - 1。

j = i + 3の場合、6, 13, 27, … , 7 * 2^(i - 1)) - 1。

対(1, 100)の場合、前に近似的に来る対の個数は、(2 * 100 - 1) - 1 = 197個。

対(99, 100)の場合、前に近似的に来る対の個数は、(3 * 2^99 - 1) - 1個。

対(100, 100)の場合、前に近似的に来るついの個数は、(2 * 2^99 - 1) - 1個。