Scheme

SICPを読む(110) 3.3.5 制約の拡散

熱い。熱すぎる。もっと頭を熱くするにはSICPがいいよね。 今回は制約システム(プログラミング)を利用して方程式を解けるようにするらしい。 ところで制約システム(プログラミング)ってなんぞ? 制約プログラミング - Wikipedia ほうほう。Prologみたいなも…

束縛

ふとした疑問。 gosh> ((lambda (x x) x) 1 2) 1 へぇぇ。 MzSchemeはエラーだった。 ついでに。 Fierfox alert(function(x, x) {return x;}(1, 2)); // 2 へぇぇ。

Schemeをつくろう(22) - JavaScriptのメモ

JavaScriptでSchemeを作る為に必要なことをメモっとく。 字句解析 tokenize = function(src) { return src.match(/\(|\)|'|[^\s()']+/g); }; // tokenize("(hello Javascript and Scheme world !!)") // => #(( hello Javascript and Scheme world !! )) 配…

Biwa Schemeを読む(3) - コンパイラ〜インタプリタ

ここからが本題。CompilerとInterpreterは一緒に読んだ方がよさげ。Biwa Schemeの中間言語は[命令,値(複数),次の命令]という形になっていて再帰的な構造をしているようだ。 命令一覧 halt 終わり。 constant 値 レジスタに値を入れる。 argument レジスタの…

Biwa Schemeを読む(2) - パーサー

まずはパーサーを読む。2段階に分けてある様子。 トークンに分ける(tokenize) 一気にS式に変換するのではなく、文字列をトークンに分解している。 S式に変換(getObject) 型付けをしながらS式に変換。 正規表現があると楽チンらしい。 感想など ここまでは今…

Biwa Schemeを読む(1) - データ構造

stackbase.jsを読み進める。データ構造を理解していこう。 環境系 TopEnv トップクラスの環境。いわゆるグローバル変数とか、グローバル関数だとか。 CoreEnv 今のところ謎。 Symbols シンボルテーブル。Symbolクラスが入ってる。 データ構造 eof なんだろ。…

Biwa Schemeを読む(0) - 斜め読み

仮想マシン クロージャやら末尾再帰の最適化やら継続やらをなんとか理解できるようになってきた。しかし、中間コードを生成し, 仮想マシンで・・・と言われると何のことやらちんぷんかんぷんだ。 こんな感じ? 僕のイメージとしては、パーサーを通してS式に…

ヒープソート

チマチマアルゴリズムのお勉強中。今回はヒープソート。SICPにも二進木が出てきた気がするけど、ヒープも二進木の一種らしい。 ところでヒープってナンダ!! ヒープ領域とは全く関係ない。 親 > 子となってるツリー構造。親 ま、詳しいことは、こちらをヒー…

nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるか

与えられた木から・・・の回答例を巡ってたら、「nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかという問題」をScalaで解いてみた - Onion開発停滞日記 > Achiral に Scan とか Pairwise とか条件変化可能な TakeWhile …

与えられた木から、子→親への対応を作る

via 自分には30分でも難しそうな希ガス > 与えられた木から、子→親への対応を作る 木構造が与えられる。たとえばこんなの: (define *tree* '(Root (Spine (Neck (Head)) (RClavicle (RUpperArm (RLowerArm (RHand)))) (LClavicle (LUpperArm (LLowerArm (LH…

Problem 72 - 既約分数の数

かなり重かった。 Problem 72 - PukiWiki1/dとして、d オイラーの関数で簡単に。と思ったけど、100万までの全ての数について素因数分解したのと変わらない訳。 100万 * √100万 = 10億。 多く見積もって10億回。少なく見積もっても1億回くらい。時間計り忘れ…

Problem 5の回答例を読む

ログインして問題を解かないと回答例がオープンしないのが残念だ。 Problem 5 - PukiWiki 2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。では、1 から 20 までの整数全てで割り切れる数字の中で最小…

Problem 73 - 1/2と1/3の間

微妙。疲れてきたかも。Problem 73 - PukiWiki1/2と1/3の間にある真既約分数を求める。 真既約分数を求めるのがちとめんどかったので、全部見てしまった。 だいたい範囲を絞っておいて、 gcdしてみる。 だいたいなので、キッチリ範囲チェック。 今は反省して…

Problem 49 - 等差数列に潜む素数

等差数列と素数の関係に関する問題。 Problem 49 - PukiWiki項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。 3つの項はそれぞれ素数である。 各桁は他の項の置換で表される。 もう一個4桁の中に同じ性質を持つものがあるらしい。 作戦と…

Problem 44 - 五角数

五角数に関する問題。 Problem 44 - PukiWiki2つの五角数の和と差を取って、五角数になるものを見つける。 五角数チェックは前に書いたのでコピッペで。2つの和と差は五角数キャッシュを持っておいて、キャッシュと比較してく事にする。 (define (problem44)…

Problem 47 - 異なる素因数

ガンガンいくよ。 Problem 47 - PukiWiki連続する3つの数がそれぞれ3つの異なる素因数を持つものは、こんなんで、 644 = 2^2 × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19 連続する4つの数がそれぞれ4つの異なる素因数を持つものを答える。 2^2と2は異なる…

Problem 43 - Pandigital数(2)

日本人50位になりました。数学なんてちんぷんかんぷんだった僕がここまで来れるとは思ってなかったっす。数学おもろいっす。後は英語・・・。 Problem 43 - PukiWikiまたまたPandigital数。こちらはちときつい。 0〜9までの順列出して全アタック。先頭のゼロ…

Problem 38 - Pandigital数

後で読み返してみたら、案外簡単だったり。Problem 38 - PukiWiki組合せ数が多いかと思ってたけど、そうでもなかった。1のだけの組合せは無い。と書いてあったのでほっと一安心。回答が9876...になっちゃうのでありえないか。 安心したところで範囲を考える…

Problem 32 - 積の組合せ

ぜぃぜい。やっと解けた。Problem 32 - PukiWiki39 × 186 = 7254のように1から9が一回づつ現われる積の組合せを見つける。 積の組合せは 1桁 * 4桁 = 4桁 2桁 * 3桁 = 4桁 しかない。ということで、 1〜9の中から、1桁or2桁の順列を求める。 差集合を取って…

Problem 46 - 奇合成数

オイラーと同時代の数学者Christian Goldbachに関する問題。 Problem 46 - PukiWiki奇合成数25は、25 = 7 + 2 * 3^2のように、素数 + 2 * 平方数で表せる。という予想を打ち破れ。という問題。 ゴールドバッハの予想 - Wikipediaとはちょっと違うみたい。 ま…

Problem 50 - 連続する素数の和

前に作った素数判定が火を噴きそうだ。 Problem 50 - PukiWiki100万未満の素数を連続する素数の和で表したときに最長になる素数を答える問題。 まずは篩。 (define (make-sieve-of-eratothenes n) (letrec ((sieve (make-vector (quotient (+ n 1) 2) #t)) (…

Problem 102 - 三角形の内外判定

はじめての非離散系? Problem 102 - PukiWiki2次元にマッピングされた三角形が原点を含むかどうか判定する。 原点,点A,点Bのz方向の外積を取ってみて、全て同じ方向を向いてたら、含んでる。 ベクトルの話なんか忘れちゃったよ。必死でフルスクラッチ本読ん…

Problem 85 - 長方形の組合せ

結構面白い。 Problem 85 - PukiWikix * yの枠があって、その中に入る長方形の組合せの数を求める。 1 * 1から順に組合せ数を求めてみると面白いルールが浮かび上がってくる。ルールは内緒。 で、そこからがちと面倒で、2,000,000に一番近い解をどうやって求…

Problem 65 - eの連分数

翻訳無いけどやってみる。Problem 65 - Project Euler √2の連分数は、√2 = [1;(2)]と表せて、eの連分数表記は、e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]こんなんらしい。100項目の分子の数値の和を求める。 問題は長いけど、やることはシンプル。 …

Problem 62 - 立方数

なかなかうまく解けた。 Problem 62 - PukiWiki立方数の数字を入れ替えると、また立方数になっちゃう数を見つける。 41063625 (345^3)に対して、数字を入れ替えて探すと膨大な組合せが必要になってしまうので、ここは考え方を変えて、数字の占める数を保存し…

素数判定の高速化

素数判定を使うことが多いProject Eulerなので、Problem 6,Problem 10の回答例を見ながら試し割りの高速化を図ります。 試し割り編 今までのアルゴリズムは、2以外の素数は奇数。というルールに基づき、3から3,5,7,9,11,13...と偶数で割ってみて√2まで割り切…

Problem 57 - 連分数で√2

連分数に関する問題。Problem 57 - PukiWiki連分数で√2を求めた時、分子と分母の桁数が違う時の数を数える。 連分数だけじゃ面白くないから、ちょっと変わった感じにしてるみたい。 分数の計算ではまった。 1回目 1 + 1/2 2回目 1 + 1/(2 + 1/2) = 1 + 2/5 3…

Problem 79 - 和の組合せ

メモ化の威力に感動した。 Problem 76 - PukiWiki 100の和の組合せを求める。両替問題のヤバいバージョン。 ナイーブにやってみたら50で破綻した。 1だけの組合せになったら1種類と特殊化することで40秒で完了できるようになった。 同じ計算を何度もやってる…

Problem 69 - オイラーの関数

久しぶりにキマッた。 Problem 69 - Project Euler翻訳無かったけど、オイラーの関数に関する問題。 オイラーの関数φ(n)は、nと互いに素な整数の個数を表す。例えば、φ(6) = {1,5} = 2 φ(10) = {1,3,7,9} = 4n/φ(n)とすれば、nのなかに互いに素な整数の割合…

Problem 71 - 3/7よりちょっと小さい分数

もうちょいいこう。Problem 71 - PukiWiki100万以下の真既約分数を小さい順に並べて、3/7の左側に来る分数の分子を答える。 素直に並べたら、100万の2乗回はかかるのでムリっぽい。んじゃ、と思って3/7以下に絞ってみたけど、1000分割位で破綻。100万 * 40万…