開発環境
- OS X Mavericks - Apple(OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- Scheme (プログラミング言語)
- Gauche (処理系)
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題 1.27.を解いてみる。
その他参考書籍
- Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
- プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
問題 1.27.
コード(BBEdit, Emacs)
sample.scm
#!/usr/bin/env gosh ;; -*- coding: utf-8 -*- (use srfi-27) ;; fermat-test手続きで使うrandom-integer手続きのため必要 ;; Fermatテスト (define (fermat-test n) (define (try-it a) (= (expmod a n n) a)) (try-it (+ 1 (random-integer (- n 1))))) (define (expmod 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 (prime? n) (= n (smallest-divisor n))) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0)) ;; (define (square x) (* x x)) (define (carmichael? n) (define (iter a) (cond ((= a n) true) ((= (remainder (expt a n) n) (remainder a n)) (iter (+ a 1))) (else false))) (and (iter 0) (not (prime? n)))) (define true #t) (define false #f) (for-each (lambda (x) (if (carmichael? x) (print x "はCarmichael数") (print x "はCarmichael数ではない"))) '(2 3 5 7 9 561 1105 1729 2465 2821 6601))
入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))
$ ./sample.scm 2はCarmichael数ではない 3はCarmichael数ではない 5はCarmichael数ではない 7はCarmichael数ではない 9はCarmichael数ではない 561はCarmichael数 1105はCarmichael数 1729はCarmichael数 2465はCarmichael数 2821はCarmichael数 6601はCarmichael数 $
0 コメント:
コメントを投稿