while の展開を行う処理を考えてみる。 束縛変数のない名前付き let でループさせれば等価になるはずなので、 (define (while-predicate exp) (cadr exp)) (define (while-body exp) (cddr exp)) (define (while->let exp) (let->combination (make-named-le…

let 式を等価の lambda 式に変形する問題。 (define (let->combination exp) (let ((body (let-body exp)) (bind (let-bind exp))) (cons (cons 'lambda (cons (let-parameters bind) body)) (let-arguments bind)))) (define (let-parameters exp) (map car…

今度は名前付き let を lambda に展開する問題。一瞬どうするの？と戸惑ったけど、具体例を書いてみると (let foo ((a 1) (b 2)) (print "abc") (+ 1 a b)) を (lambda (a b) (define foo (lambda (a b) (print "abc") (+ 1 a b))) (foo 1 2)) に変換すると…

(cond (test => recipient)) ↓ 普通の cond に変換する (cond (test (recipient test))) ↓ if に展開する。 (if test (recipient test)) と変形できるので、cond の処理は次のようになる。 (define (cond-arrow-caluse? clause) (eq? (cadr clause) '=>)) (d…

今度は let* 式を等価の let 式に変形する問題 (define (make-let bind body) (cons 'let (cons bind body))) (define (let-parameters exp) (map car (car exp))) (define (let-arguments exp) (map cadr (car exp))) (define (let-bind exp) (cadr exp)) (…

a=10; b=20; c=a+b; のように書くのがマルチステートメントです。1行に複数の命令を記述する、とても気持ち悪い記述方法です。 でも昔はちゃんと意味がありました。まだコンピューターが貧弱だった時代、マルチステートメントで記述することで、 ちょっとだ…

higepon さんの d:id:higepon:20080925:1222326246 をやってみました。こういう問題です。 整列済みの number のリストがある。 '(1 3 4 5 6 12 13 15) このようなリストで数が連続している部分は '(1 2 3) -> '(1 . 3) のように両端のみを書くような記法を…

Problem 37 - Project Eulerd:id:mtsuyugu:20080815:1218805119 の prime.scm を利用しています。結構時間がかかりました。 (use srfi-1) (load "./prime.scm") (define (keta n) (let loop ((n n) (i 0)) (if (= n 0) i (loop (quotient n 10) (+ i 1))))) …

Problem 12 - Project Euler約数が 500 以上ある最少の数を求める問題です。d:id:mtsuyugu:20080815:1218805119 の prime.scm を利用しています。 (load "./prime.scm") (define (tri n) (/ (* n (+ n 1)) 2)) (define (p12) (let loop ((i 2)) (let* ((tri …

素数関連の問題は次の関数群を使うことにしました。prime.scm とでもしておきます。 (use util.stream) (define divisible? (lambda (n d) (= (modulo n d) 0))) (define square (lambda (x) (* x x))) ; n 以上の整数ストリーム (define (integers-starting…

Problem 32 - Project Euler39*186 = 7254 のように被乗数、乗数、積をつなげた 9 桁の数がパンデジタル数になる、積の和を求める問題。総当たりで解きました。9 桁のパンデジタル数に 2 カ所切り込みを入れて 3 つの数を作り、初めの 2 つの数の積が 3 つめ…

三角形の周辺長が p(cartesian-product を使って総当たりでチェックしているために時間はかかりますが答えは求まります。 (use srfi-1) (use util.combinations) (define (square x) (* x x)) (define (right-angle? t) (= (+ (square (car t)) (square (cad…

Problem 67 - Project Eulerx^n が n 桁の数になるような x はいくつあるかという問題。 10^n は n+1 桁の数だから n がどんな値であれ x が 10 未満は明らかです。あとは 9^n ですら n-1 桁になるような n が見つかるまで n をひとつずつ増やして題意を満た…

Problem 79 - Project Euler問題の本質は、集合の要素間の部分的な順序関係が複数与えられたときに要素全体の順序を見つける問題です。これを解くのはトポロジカルソートです。とはいっても、この問題を解くまでトポロジカルソートについては名前と何をする…

Problem 31 - Project Euler金額が 1, 2, 5, 10, 20, 50, 100, 200 のコインがあるときに 200 の作り方は何通りあるかという問題です。 (use srfi-1) (define kinds (list 200 100 50 20 10 5 2 1)) ; k 以下のコインを使って n を作る方法は何通りあるか（ …

Problem 59 - Project Eulerキーと平文との xor を取ることで作成された暗号をブルートフォースで解く問題です。キーは小文字のアルファベット 3 文字を平文の長さだけ繰り返したものです。 (use srfi-1) (use util.combinations) (define encrypted (list 7…

Problem 33 - Project Euler49/98 は 1/2 ですが、49/98 の 9 を消しても 4/8 = 1/2 になるという面白い性質を持っています。問題 33 は二桁の分母分子からなる 1 未満の分数で先の例のような分数をすべてかけたときの分母の値はいくつか？ というものです。…

Problem 81 - Project Euler80*80 の行列の左上から右下まで要素を辿っていったときの経路となった要素の和が最少になるときの値はいくつかを求める問題です。各要素の値を、ひとつ上とひとつ右の要素の値を比べて小さい方の値と自分自身の値の和に置き換え…

Problem 99 - Project Euler1000 個ある 基数とべき数のペア（ファイルの各行にコンマ区切りで列挙されている）からべき乗数のうち、最大になるものは何番目かという問題です。基数、べき数ともに大きな数なので、べき乗数で比較せずに対数で比較します。比…

Problem 57 - Project Euler2 の平方根を連分数で近似するとき、 1000 段までの近似値のなかで、分子の桁数が分母の桁数より多いものはいくつあるかという問題です。初めは桁数を求めるために (floor (+ 1 (/ (log n) (log 10))) としてましたが、n = 1000 …

Problem 53 - Project EulernCr ( 1 ≤ n ≥ 100, 1 ≤ r ≤ n ) で 1,000,000 を超えるものはいくつあるかという問題。n と r で 2 重ループにして足していけば良いだけです。こういう問題を loop を使わずに解けるようになりました。 (use srfi-1) ; permutati…

Problem 52 - Project Eulerx, 2x, 3x, 4x, 5x, 6x が全て同じ数字の組み合わせになる正数 x を求める問題です。 (use srfi-1) (use util.stream) (define integer (stream-cons 1 (stream-map (pa$ + 1) integer))) ; 14235 -> '(1 2 3 4 5) (define (digit…

Problem 26 - Project Euler循環小数 1/d (1

Problem 56 - Project Eulera 100^100 が普通に計算できるので簡単です。 ; 1234 -> 10 (define (sum-digits num) (let loop ((r 0) (n num)) (if (= n 0) r (loop (+ r (modulo n 10)) (quotient n 10))))) (define (p56) (let loop ((a 1) (b 1) (r 0)) (i…

Problem 55 - Project Eulerまた、簡単そうな問題を見つけました。10000未満の数で、回文数と元の数を足すことを50回繰り返しても回文数があらわれないような元の数はいくつあるかという問題。問題の詳細は日本語訳 [http:z.sakura.ne.jp/projecteuler/index…

Problem 28 - Project Euler 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13こういう風に正の整数を螺旋状に 1001×1001 のサイズまで並べていったとき対角線上にある数の合計を求める問題。まず n (n>1) 週目の数字の並びを考えてみる…

Problem 42 - Project Euler[id:mtsuyugu:20080707:1215444841] で過去に解いた problem 22 とよく似た問題です。 アルファベットに A = 1, B = 2 ... と数を割り当てたものの合計が "SKY" = 19 + 11 + 25 = 55 のように三角数になる単語が与えられたファイ…

Problem 35 - Project Euler1,000,000 以下の素数の中で桁を回転させてできる数字がすべて素数(ex. 197, 719, 971) である数はいくつあるかという問題です。primes.txt にはリストの形で 1,000,000 以下の素数が列挙しています。添え字が素数の要素は値が 1 …

Problem 97 - Project Euler一気に飛んで problem 97。2,357,207 桁からなるメルセンヌ数でない素数 28433*2^7830457+1 の下 10 桁を求める問題。(expt 2 7839457) とするのではなくて、10桁を超えないように常に下10桁に対して 2 を掛けるようにはしている…

Problem 7 - Project Euler10001 番目の素数を求める問題です。SICP でストリームを勉強してから project euler に戻ってきたときに解いていたのですが、まだ書いていませんでした。 (use util.stream) (define divisible? (lambda (n d) (= (modulo n d) 0)…