計算機プログラムの構造と解釈（SICP）学習メモ
蒋　いつ峰 2008/08/07   |  プログラミング基礎
第一章　練習1.34〜1.39 2008/08/07  |  PK：SICP 練習 1.34〜1.39

プロシジャーを一般的なメソッドにする、fixed-point を探す。


問題

練習1.34：(define (f g) (g 2)) がある、(f f) は何でしょう？
練習1.35：Fixed-point を利用して、黄金率を求める。
練習1.36：改善されたFixed-point。平均緩和法。
練習1.37：連分数。
練習1.38：e を求める。
練習1.39：tan(x) を求める。


解答

練習1.34の解答

f(g) = g(2)だから、f(f) = f(2) = 2(2)、エラーとなります。


練習1.35の解答

 
  1. /** 
  2.  * 練習1.35。 
  3.  * Fixed-point を利用して、黄金率を求める。 
  4.  */  
  5. const float TOLERANCE = 0.00001;  
  6.   
  7. static float goldenRatio(float x) {  
  8.     return 1 + 1/x;  
  9. }  
  10.   
  11. float fixedPoint(float function(float) f, float firstGuess) {  
  12.     bool closeEnough(float v1, float v2) {  
  13.         return abs(v1 - v2) < TOLERANCE;  
  14.     }  
  15.   
  16.     float tryIt(float guess) {  
  17.         float next = f(guess);  
  18.         if (closeEnough(guess, next)) {  
  19.             return next;  
  20.         }  
  21.         return tryIt(next);  
  22.     }  
  23.   
  24.     return tryIt(firstGuess);  
  25. }
  26.  
  27. void main() {  
  28.     float ret;  
  29.   
  30.     // for 1.35  
  31.     Stdout("---- 1.35 ----").newline;  
  32.     ret = fixedPoint(&goldenRatio, 1.0);  
  33.     Stdout.formatln("goldenRatio = {:f16}", ret);  
  34. }  

 

実行結果。

---- 1.35 ----
goldenRatio = 1.6180328130722046



練習1.36の解答

 
  1. /** 
  2.  * 練習1.36。 
  3.  * 改善されたFixed-point。平均緩和法。 
  4.  */  
  5. int loop = 0;  
  6.   
  7. float fixedPoint2(float function(float) f, float firstGuess) {  
  8.     bool closeEnough(float v1, float v2) {  
  9.         return abs(v1 - v2) < TOLERANCE;  
  10.     }  
  11.   
  12.     float tryIt(float guess) {  
  13.         loop++;  
  14.         float next = f(guess);  
  15.         Stdout.format("{:f5}\t", next);  
  16.         if (closeEnough(guess, next)) {  
  17.             return next;  
  18.         }  
  19.         return tryIt(next);  
  20.     }  
  21.   
  22.     return tryIt(firstGuess);  
  23. }  
  24.   
  25. // 平均緩和法を使わない  
  26. static float fpNoDamping(float x) {  
  27.     return log(1000) / log(x);  
  28. }  
  29.   
  30. // 平均緩和法を使う  
  31. static float fpDamping(float x) {  
  32.     float total = x + (log(1000) / log(x));  
  33.     return total / 2;  
  34. }  

実行結果。

---- 1.36 ----
4.29203    4.74186    4.43820    4.63530    4.50398    4.58999    4.53301    4.57048    4.54572    4.562024.55126    4.55836    4.55368    4.55676    4.55473    4.55607    4.55518    4.55577    4.55538    4.555644.55547    4.55558    4.55551    4.55555    4.55552    4.55554    4.55553    4.55554   
[No average damping] Root = 4.55554, loop = 28

4.64601    4.57161    4.55829    4.55601    4.55562    4.55555    4.55554    4.55554   
[With average damping] Root = 4.55554, loop = 8

平均緩和法を利用することで、計算が遥に早くなりました。


練習1.37の解答

 
  1. /** 
  2.  * 練習1.37。 
  3.  * 連分数。 
  4.  */  
  5. static float n(int i) {  
  6.     return 1.0f;  
  7. }  
  8.   
  9. static float d(int i) {  
  10.     return 1.0f;  
  11. }  
  12.   
  13. // 再帰版  
  14. float contFrac(float function(int) n, float function(int) d, int k) {  
  15.     float iter(int m) {  
  16.         if (m == k) {  
  17.             return n(k) / d(k);  
  18.         }  
  19.         return n(m) / (d(m) + iter(m + 1));  
  20.     }  
  21.     return iter(1);  
  22. }  
  23.   
  24. // 反復版  
  25. float contFrac2(float function(int) n, float function(int) d, int k) {  
  26.     float iter(int m, float result) {  
  27.         if (m == 1) {  
  28.             // 0 まではだめ  
  29.             return result;  
  30.         }  
  31.         return iter(m - 1, n(m-1) / (d(m-1) + result));  
  32.     }  
  33.     return iter(k, n(k)/d(k));  
  34. }  

 

実行結果。

---- 1.37 ----
[再帰] contFrac(&n, &d, 11) = 0.6180555820465088
[反復] contFrac2(&n, &d, 11) = 0.6180555820465088

k >= 11 時、４位の精度が保証できます。


練習1.38の解答

 
  1. /** 
  2.  * 練習1.38。 
  3.  * e を求める。 
  4.  */  
  5. static float d2(int i) {  
  6.     int div = i / 3;  
  7.     int mod = i % 3;  
  8.     float ret;  
  9.     if (mod == 0 || mod == 1) {  
  10.         ret = 1;  
  11.     } else {  
  12.         ret = 2 * (div + 1);  
  13.     }  
  14.     return ret;  
  15. }  
  16.   
  17. float e(int k) {  
  18.     return contFrac2(&n, &d2, k) + 2;  
  19. }  

 

実行結果。

---- 1.38 ----
e(10) = 2.7182817459106445

 

練習1.39の解答

 

 
  1. /** 
  2.  * 練習1.39。 
  3.  * tan(x) を求める。 
  4.  */  
  5. static float n3(float x, int i) {  
  6.     if (i == 1) {  
  7.         return x;  
  8.     } else {  
  9.         return - x*x;  
  10.     }  
  11. }  
  12.   
  13. static float d3(int i) {  
  14.     return 2 * i - 1;  
  15. }  
  16.   
  17. float contFrac3(float function(float, int) n, float function(int) d, int k, float x) {  
  18.     float iter(int m, float result) {  
  19.         if (m == 1) {  
  20.             // 0 まではだめ  
  21.             return result;  
  22.         }  
  23.         return iter(m - 1, n(x, m-1) / (d(m-1) + result));  
  24.     }  
  25.     return iter(k, n(x, k)/d(k));  
  26. }  
  27.   
  28. float tanCf(float x, int k) {  
  29.     return contFrac3(&n3, &d3, k, x);  
  30. }  

 

実行結果。

tanCf(pi/4, 10) = 0.9999999403953552
tanCf(0, 10) = 0.0000000000000000
tanCf(1, 10) = 1.5574077367782593

閲覧  |  コメント  |  目次

 
ヘルプ  |  ご利用規約  |  相互リンク  |  問合せ
リンクはご自由に、問合せはお気軽に
©2007 Uprush