SICP学习笔记06 vvipi 发表于2018年11月17日,阅读:2529 ### 练习1.27 证明脚注47中列出的Carmichael数确实能骗过费马检查。即写一个过程,它以整数n为参数,对每个a<n 检测$$a^n$$是否与a模n同余。用这个过程检查前面给出的Carmichael数。 ### 解答 ``` (define (expmod base exp m) ; 求base的exp次方除以m的余数 (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (square x) (* x x)) (define (prime? n) ; 判断是否能通过素数检测 (define (iterprime a n) (cond ((= a n) #t) ((samemod? a n) (iterprime (+ a 1) n)) (else #f))) (iterprime 1 n)) (define (samemod? a n) ; 判断a和a的n次幂是否模n同余 (= (expmod a n n) (remainder a n))) (define (report n) ; 报告一个整数是否能通过素数检测 (if (prime? n) (begin (display n) (display " is a prime")) (begin (display n) (display " is not a prime")))) (report 561) (newline) (report 1105) (newline) (report 1729) (newline) (report 2465) (newline) (report 2821) (newline) (report 6601) (newline) (report 6602) (exit) ``` 看答案似乎不难,自己写总是拼凑半天,各种语法错误,对于这些数学问题缺少经验,scheme的语法也还是磕磕绊绊。 ### 练习1.28 ``` (define (expmod base exp m) ; 求base的exp次方除以m的余数 (cond ((= exp 0) 1) ((nontrivial-square-root? base m) 0) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (nontrivial-square-root? a n) ; 判断a是否是n的非平凡平方根 (and (not (= a 1)) (not (= a (- n 1))) (= (remainder (square a) n) 1))) (define (square x) (* x x)) (define (prime? n) ; 判断是否能通过素数检测 (let ((times (ceiling (/ n 2)))) (iterprime times n))) (define (iterprime times n) (cond ((= times 0) #t) ((= (expmod (none-zero-random n) (- n 1) n) 1) (iterprime (- times 1) n)) (else #f))) (define (none-zero-random n) ; 返回一个非零随机数 (let ((r (random n))) (if (not (= r 0)) r (none-zero-random n)))) (define (report n) ; 报告一个整数是否能通过素数检测 (if (prime? n) (begin (display n) (display " is a prime")) (begin (display n) (display " is not a prime")))) (report 561) (newline) (report 1105) (newline) (report 1729) (newline) (report 2465) (newline) (report 2821) (newline) (report 6601) (newline) (report 7) (exit) ``` 最初认为expmod函数中base和m参数在计算过程中不会变化,应该对exp进行判断是否是1取模n的非平凡平方根。后来才想明白,base在每次随机时传入的是不同的值,应该是对base进行判断才对。