• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            CG@CPPBLOG

            /*=========================================*/
            隨筆 - 76, 文章 - 39, 評論 - 137, 引用 - 0
            數據加載中……

            我的SICP習題答案(1.21~1.23)

            1.21

            > (smallest-divisor 199)
            199
            > (smallest-divisor 
            1999)
            1999
            > (smallest-divisor 
            19999)
            7
            >

            1.22
            在 DrScheme 中沒有對應的 runtime 過程,我們用內建的 current-milliseconds 來代替,這個過程返回的是系統的 ms 數。
            同時,在 Windows 下無法精確表示 16ms 以下的精度(可能時間片的大小是 16ms ),所以這里用比較大的數來測試。
            代碼如下

            (define (even? x) (= (remainder x 20))

            (define (runtime) (current-milliseconds))

            (define (start-prime-test n start-time)
              (and (prime? n)
                   (report-prime (- (runtime) start-time))))

            (define (report-prime elapsed-time)
              (display 
            " *** ")
              (display elapsed-time))

            (define (search-iter cur-num index start-time)
              (newline)
              (display cur-num)
              (if (not (
            = index 0))
                  (if (start-prime-test cur-num start-time)
                      (search-iter (+ cur-num 
            2) (- index 1) start-time)
                      (search-iter (+ cur-num 
            2) index start-time))))

            (define (search-for-primes start-number)
              (if (even? start-number)
                  (search-iter (+ start-number 
            13 (runtime))
                  (search-iter start-number 
            3 (runtime))))

            這里用到了 prime? 謂詞,代碼不再復述。
                                        
            |------+--------+--------+-------|
            |10^9  | 10^10  | 10^11  | 10^12 | => start-number
            |------+--------+--------+-------|
            |31    | 250    | 609    | 1953  | (ms)
            |47    | 406    | 1203   | 3844  |
            |78    | 625    | 1859   | 5719  |
            |------+--------+--------+-------|

            從上表可以看出,除了前兩列之間,后列的數字都是前列數字的 3 倍左右,近似于 √10 ≈ 3.16。實際上,隨著 n 的不斷增大,這個數會逐漸逼近 √10。

            1.23

            (define (next n)
              (if (
            = n 23 (+ n 2)))

            (define (find-divisor n test-divisor)
              (cond ((> (square test-divisor) n) n)
                    ((divides? test-divisor n) test-divisor)
                    (else (find-divisor n (next test-divisor)))))

            計算結果如下:
            |--------+--------+-------|
            | 10^10  | 10^11  | 10^12 | => start-number
            |--------+--------+-------|
            | 141    | 297    | 1078  | (ms)
            | 219    | 609    | 2093  |
            | 313    | 984    | 3140  |
            |--------+--------+-------|

            可以看出這個比值大約在 1.8(1/0.55) 左右,可能原因是其它的計算需要時間,但當 n 不斷增大,其它計算是常數階,這個比值會不斷接近2。


            posted on 2008-03-28 23:44 cuigang 閱讀(793) 評論(2)  編輯 收藏 引用 所屬分類: Lisp/Scheme我的SICP答案

            評論

            # re: 我的SICP習題答案(1.21~1.23)  回復  更多評論   

            (current-milliseconds)這個貌似在解釋器里定義的
            2010-05-11 20:04 | luthur

            # re: 我的SICP習題答案(1.21~1.23)  回復  更多評論   

            說錯了,這個沒有在解釋器里定義,我用不了
            2010-05-11 20:25 | luthur
            久久亚洲精品国产精品婷婷| 色88久久久久高潮综合影院| 久久有码中文字幕| 久久精品三级视频| 99久久国产综合精品女同图片| …久久精品99久久香蕉国产| 久久影视综合亚洲| 国内精品伊人久久久久av一坑| 国产高清美女一级a毛片久久w | 久久精品视频网| 青青久久精品国产免费看| 久久无码人妻一区二区三区| 久久国产精品免费| 久久精品免费观看| 无码国内精品久久人妻蜜桃 | 久久久久久久久久久久久久 | 波多野结衣久久| 色综合久久综精品| 久久久久人妻精品一区二区三区 | 综合久久给合久久狠狠狠97色| 97精品伊人久久大香线蕉app| 欧美日韩久久中文字幕| 国产叼嘿久久精品久久| 久久精品欧美日韩精品| 亚洲精品乱码久久久久久蜜桃图片| 国产精品成人无码久久久久久 | 久久发布国产伦子伦精品| 亚洲AⅤ优女AV综合久久久| 亚洲国产精品久久久久| 国产精品久久自在自线观看| 亚洲国产精品无码久久一区二区 | 久久本道伊人久久| 久久夜色精品国产噜噜噜亚洲AV| 国内精品伊人久久久久777| 欧美日韩久久中文字幕| 偷偷做久久久久网站| 区久久AAA片69亚洲| 亚洲精品蜜桃久久久久久| 人妻无码αv中文字幕久久| 99久久精品午夜一区二区| 精品国产一区二区三区久久久狼|