scheme
Problem 36 - Project Euler1,000,000 以下の数で 10 進数、2 進数どちらで表しても、回文になる数(ex. 585 = 1001001001) の和を求める問題。 (use srfi-1) (use srfi-13) (define (palindromic? num radix) (let1 str (number->string num radix) (string=…
Problem 40 - Project Euler1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 ... のように正の整数の順番に並べた数列の n 番目の数を d_n としたときにd_1 * d_10 * d_100 * ... * d_1000000を求める問題。 (use srfi-1) ; 123 -> '(1 2 3) (define (number->list num) (let…
Problem 48 - Project Euler先の問題を眺めていたらラッキー問題を見つけました。1 (use srfi-1) (define (p48) (let1 n (iota 1000 1) (modulo ;(fold (lambda (x y) (+ y (expt x x))) 0 n) ;(apply + (map (lambda (x) (expt x x)) n)) (apply + (map exp…
Problem 22 - Project Eulerファイルに書かれた名前を数値に変換したものの重み付け総和を求める問題です。ファイル入力は初めてでしたが調べたらすぐ分かりました。他の言語と変わりません。ファイルハンドラ、ファイルポインタではなくてポートと呼ばれる…
解き貯めしていたものがなくなってきたので、過去に解いたものを振り返って改良してみました。 d:id:mtsuyugu:20080528:1211984870 d:id:mtsuyugu:20080705:1215227594 総和を求めるのに fold でもループでもなく apply を使ってみました。
Problem 34 - Project Euler各桁の数字の階乗の和ともとの数が等しい数の総和を求める問題。 (define (fact n) (define ht (make-hash-table)) (if (hash-table-exists? ht n) (hash-table-get ht n) (let loop ((i n) (m 1)) (if (= i 0) (begin (hash-tabl…
Problem 24 - Project Euler0 から 9 までの数字の順列を辞書順に並べたとき、1000000 番目の数字は何か？という問題。確率統計にありがちな問題です。 pen and paper で 考えてたら紙と鉛筆で解いてしまった。以下その時のメモ： permutation-table: 9! = 3…
Problem 30 - Project Euler各桁の数字を5乗したものの和がもとの数と等しくなる数の合計を求めるという問題です。ループを使わずに fold, map, filter などの高階関数のみで解いてみました。 (list 1 10 100 1000 10000 100000 1000000) で済むところを (ma…
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…
