Problem 8 - Project Euler連続する 5 つの数字の積のなかから最大のモノを見つける問題です。 (define digit1000 (map digit->integer (string->list "731671765313306249192...."))) (define (p8 digit1000) (apply max (map * digit1000 (cdr digit1000) …

Problem 3 - Project Euler600851475143 の最大の素因数を求める問題。素数ストリームで地道にループ。 (use util.stream) (define divisible? (lambda (n d) (= (modulo n d) 0))) (define square (lambda (x) (* x x))) (define (integers-starting-from n…

stream の勉強を中断して project euler にもどってみました。Problem 10 - Project Euler200 万以下の素数の和を求める問題。ほとんど SICP からのコピペです。 そもそもは stream の勉強で SICP を読んでたのですが、 結局素数ストリームそのものずばりが…

Excercie 3.65 Exercise 3.65.まずは pi-stream を参考にして ln2-stream を作成。 (define (ln2-summands n) (stream-cons (/ 1.0 n) (stream-map - (ln2-summands (+ n 1))))) (define ln2-stream (partial-sums (ln2-summands 1))) まんまです。 次にスト…

Excercie 3.63 Exercise 3.63.問題に書かれているものだと stream-map に渡す (sqrt-stream x) を都度計算する必要があるが、 テキスト本文中に書かれている stream-map に guesses を渡す方法はローカル変数 guesses を参照し続けるだけでいいから、都度計…

Excercie 3.61 Exercise 3.61.べき級数ストリームの逆数を表すストリームを求める問題。これは本に出てくる数式をそのまま scheme に直せばおｋ。 (define (invert-unit-series s) (stream-cons 1 (scale-streams (mul-series (stream-cdr s) (invert-unit-s…

Exercise 3.60.べき級数ストリームの乗算を行う mul-series を考える問題。 まずは 書いて考えてみる。 (a0+a1*x1+a2*x2+a3*x3+...)*(b0+b1*x1+b2*x2+b3*x3+...) = {a0+(a1*x1+a2*x2+a3*x3+...)}*{b0+(b1*x1+b2*x2+b3*x3+...)} ---(1)ここで、 A1 = a1*x1+a2…

Exercise 3.59.sin, cos の無限級数展開の各項を要素として持つストリームを求める問題です。 a) まずは無限多項式 における係数のストリーム a0 a1 a2 ... を引数にとり、多項式を積分したときの係数を返す関数 integrate-series を考える問題です。ストリ…

Exercise 3.56 Exercise 3.56. (define S (cons-stream 1 (merge (merge (scale-stream S 2) (scale-stream S 3)) (scale-stream S 5)))) で良いはずなんだけど手元の gosh 0.8.11 では merge がうまく動いてくれなくて無限ループになった。 Exercise 3.57 E…

3.5.2 節は無限ストリーム。素数のストリームが出てきましたが、project euler にもどるのは stream を読み終えてからにしよう。「無限ストリーム」って名前が格好いい。 Exercise 3.53. Exercise 3.53. (define s (cons-stream 1 (add-streams s s))) が何…

Exercise 3.52. (define sum 0) (define (accum x) (set! sum (+ x sum)) sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) (define y (stream-filter even? seq)) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq…

Exercise 3.51. (define (show x) (display-line x) x) (define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7) が、どういう出力になるかという問題。 (cons-stream a b) だと a は即座に評価される。 というこ…

Exercise 3.50.map の stream 版である stream-map を作るという穴埋め問題。 (define (stream-map proc . argstreams) (if (stream-null? (car argstreams)) the-empty-stream (cons-stream (apply proc (map car argstreams)) (apply stream-map (cons pro…

project euler からちょっと離れて SICP でストリームの勉強をしてみます。 バックグラウンド gauche のドキュメントを見て stream が遅延評価を利用した無限長のリストを扱うものであるということは分かっているます。 遅延評価の事は少し前に Haskell に入…

Problem 29 - Project Euler 2 ≤ a ≤ 100 かつ 2 ≤ b ≤ 100 を満たす a,b から作られる a^b はいくつあるかという問題。 2 から 100 までの 2 つの集合を用意し、 その 2 つの集合の直積を求め、 その直積に対する a^b の写像を作り、 重複を削除し、 リスト…

Problem 19 - Project Euler20 世紀中に一日が日曜日である月が何回あるかという問題です。 日付を扱うモジュールがあるからそれを使って瞬殺でしたが、モジュールを使うの禁止といわれたら今の自分には無理な問題でした。 (use srfi-19) ;; y 年 m 月 d 日…

Problem 18 - Project Euler Problem 67 - Project Euler与えられた三角状に並べられた数字を頂上から底辺まで辿ってできる経路の数の和の最大を求めると言う問題です。問題 67 は与えられる三角の大きさが大きいだけで問題自体は問題 18 と同じです。解き方…

Problem 17 - Project Eulerproject euler 問題 17 は 1 から 1000 までを英語表記したときの文字数を求める問題です。たとえば 982 だと nine hundred and eighty two で 23 文字といった具合です。 ;; n を英語で表したときの文字数を返す。 (define (get-…

Problem 21 - Project Eulerproject euler 問題 21 は 10000 以下の友愛数の和を求める問題です。友愛数というのは 2 つの自然数の自分自身以外の約数の和が互いに他方と等しくなるような 2 つの自然数のことです。6 のように約数の和が下の数と等しくなるよ…

Problem 25 - Project Euler間を抜かしすぎですが、簡単なものから解いていこうと思っています。 project euler 問題 25 です。問題 25 はフィボナッチ数列が初めて 1000 桁になるのは第何項かという問題です。桁数を文字列の長さと考えて以下のようにしまし…

project euler 問題 5 です。1 から 20 の全ての数で割りきれる最少の数を求める問題。アルゴリズム自体は難しくないのですが、考えたロジックを scheme で表現するのに骨が折れました。素因数分解のロジックは先の問題でも使えるでしょうか。素因数分解の結…

問題 16 と似たものが 問題 20 です。100! の数字の和を求める問題です。2^1000 が 100! に変わっただけです。 (define (fact n) (let loop ((i n) (m 1)) (if (= i 1) m (loop (- i 1) (* m i))))) (define (p20) (fold (lambda (x n) (+ (digit->integer x…

project euler 問題 16 です。（関係ないけど何でこの段落だけ字下げ幅が大きいのだろう？なんでなん？）2^1000 の全ての数字の和を求める問題。 (use srfi-1) (define (p16) (fold (lambda (x n) (+ (digit->integer x) n)) 0 (string->list (number->strin…

project euler 問題 15 です。 20×20 のマス目を左上から右下まで引き返さずに辿る方法は何通りあるかという問題。ありがちな二項定理を使う数学の問題です。マス目の交点へたどり着く方法を左上から順番に求めていくという方法で解いてみました。 (use gauc…

問題14です。 (define table (make-hash-table)) (define (count ini) (define (next n) (if (= (modulo n 2) 0) (/ n 2) (+ (* n 3) 1))) (define (count-iter n i) (if (= n 1) (begin (hash-table-put! table ini i) i) (let1 memo (hash-table-get table…

与えられた 50 桁の数 100 個の和の上位 10 桁を求める問題。Gauche は多倍長の整数を扱えるので難しいところはありませんでした。 (print (substring (number->string (fold + 0 num-list)) 0 10))

20*20 のサイズの行列について、縦横斜めに連続する 4 つの数字の積の中から最大のモノを見つけるという問題。 (use srfi-1) (use srfi-43) (use gauche.sequence) (define matrix (vector (vector 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 9…