落ち着いて範囲を考える。 Problem 63 - PukiWiki n乗してn桁になる数はいくつあるか。 ふむふむ。適当に計算してみる。 まず終端。10^1は2桁,10^2は3桁,10^3は4桁・・・となるので、10^nはn乗するとn+1桁。絶対に追いつかない。10以上は除外できる。 小さい…

回文数絡み。 Problem 55 - PukiWiki 349を反転させて足していくと349 + 943 = 1292,1292 + 2921 = 4213,4213 + 3124 = 7337回文数になるらしい。不思議だ。回文数にならないものをLychrel数と言うらしい。50回回しても回文数が見つからなければ、Lychrel数…

うほ。簡単。と思って取り組んでみたら罠が・・・。 Problem 99 - PukiWiki 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 しかし, 632382^518061 > 519432^525806 を確認することは非常に…

きました。最短経路。Problem 81 - PukiWiki 下記の5次の正方行列で、左上のセルから開始し右下のセルで終わる道を探索する。 ただし下方向と右方向にのみ移動できるものとする。一番小さなパスは下で赤で示されたものである。 このときの合計は2427になる。…

案外ムズイかと思って放置してた問題。Problem 40 - PukiWiki 正の整数を順に連結して得られる以下の10進の無理数を考える:0.123456789101112131415161718192021...小数点第12位は1である.dnで小数点第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d1…

50問達成。Problem 41 - PukiWiki n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である.n桁のPandigitalな素数の中で最大の数を答えよ. ハイ。組合せ。しかも、スゲー大量の…

Problem 79(2) - グラフ理論へ - ボクノス の続きです。自分が作ったアルゴリズムがトポロジカルソートだと言う名前に気づいてなかったので・・・。 ところでトポロジカルソートって何者！？ 昨日、新宿でラーメン食った。 腹いっぱいになったので、渋谷のス…

マッチ箱の脳が面白そうだったので、マッチ箱で作るNNを作ってみた。 紹介されてるニューラルネットワークは、凄く単純な仕組みで、 判断が間違ってたら怒る。 情報を修正(学習)する。 繰り返せば正しい判断をするようになる。というもの。 ふむふむ。実装し…

楽しいMIL記号の時間です。 加算器 - Wikipediaみたいなシミュレータを作っていきます。 問題 3.28 オアゲートを作れ。という問題。 (define (logical-or a b) (cond ((or (and (= a 1) (= b 1)) (and (= a 0) (= b 1)) (and (= a 1) (= b 0))) 1) ((and (= …

はじめての暗号解読に挑んでみる。 Problem 59 - PukiWiki (訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIで…

メモ化が無いと辛そうかなと思ってたけど、メモ化しても辛かった。Problem 92 - PukiWiki 各桁の数を2乗して足し合わせて新たな数を作ることによって、作られる数字の列を考える。例えば 44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 →…

いよいよメモ化 問題 3.27 以下が何をやってるのか説明せよという問題。普段でも使えるように改造版にしてみた。 (define (memoize f) (let ((table '())) (lambda x (let ((prev-result (assoc x table))) (if prev-result (cdr prev-result) (let ((result…

SICPも大変だ。 問題 3.24,3.25 equal?以外にも対応し、多次元のキーに対応せよ。という問題。 手続きの連鎖にしてみた。keyとvaluesの位置を変えて引数を可変長にしてみたけど、applyがいっぱい必要になってしまった。ちと失敗。getとsetのAPIはそのまま使…

あぁ、assocして、set-cdr!すれば、alistが更新できるのか。すると、リストの中のシンボルの数を数えたくなったら、こう書ける。 (define (collect l) (let ((collects '())) (for-each (lambda (key) (let ((record (assoc key collects))) (if record (set…

メモ化ユーティリティが欲しくなってきたので、メモ化までSICP読み。 問題 3.23 デキューを作れ。という問題。末尾のdeleteをする為には、キューを双方向化する必要がある。 前 <- 今 -> 後こうしておかないと、最後をdeleteするのにO(1)を達成できない。ち…

50問を目前に解ける問題が少なくなってきた。全然解けそうな感じの問題が無い。Problem 58 - PukiWiki 1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.(図)面白いことに, 奇平方数が右下の対角線上に出現する. …

久しぶりに素数問題。Problem 37 - PukiWiki 3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).右から切…

解けたよぉ（涙Problem 33 - PukiWiki 49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.我々は 30/50 = 3/5 のようなタイプは自明な例だ…

そういえば、googleって数の大きさだったっけ。 Google (10^100)は非常に大きな数である: 1の後に0が100個続く. 100^100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である.a, b 自然数a^bを考える. 桁の和の最大を答え…

オイラーといえば、フェルマーの最終定理に挑んだ数学者のひとり。フェルマーの最終定理といえば、a^n + b^n = c^n。というわけで、Problem 39 - PukiWiki 辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え, その周囲の長さをpとする. p = 120のときに…

グラフ理論で使うデータ構造にリストを使うと検索コストが高いので、ハッシュを使いたい。SRFI 69: Basic hash tablesを眺めてみたら、ハッシュの実装例が載ってたので、簡単に写経してみた。 SRFI-69の実装例では、ベクタ + alistの二次元構造。alistをハッ…

名前空間周りでエラーがあってマクロがうまく使えなかった(モジュールで囲むとうまくいく)ので、全くマクロはつかってなかったのですが、Vimのドキュメントを見ると、何やら名前空間をゴニョゴニョやってるみたいなので、解読中。 Vimのeval時にvim-global-n…

Ruby1.9に搭載されたtapが便利そうなので、Schemeに移植してみた。 ところでtapって何よ 副作用専門メソッド。 入力 -> tap -> 出力 V 副作用要するに、Linuxコマンドで言う所のtee。デバッグに便利かも。 Schemeに移植 簡単。 (define (tap f x) (f x) x) …

Problem 79 - セキュリティキーを解読せよ - ボクノスの続きです。ちょっと考え方を変えて、グラフ理論で解いていこうかと。 最初の4つのデータで考えてみます。 319 680 180 690キー情報を、経路問題と捕らえることにして、問題を解いていけばいいんじゃな…

ANSI Common Lisp読み。 練習問題が変態過ぎ。 長年にわたる議論の末、ある政府委員会が次のように決定した。リストは第一要素を示すために、cdrを使い、その残りを示すためにcarを用いなければならない。この方針にしたがって、以下の関数を定義せよ。cons,…

僕はSchemerなので、演算子の優先順位とかよくわかりません。だから、悪の中置記法を前置に変えてしまえばハッピーになると思うんだよ。 と思ったけど、これが結構むじぃ。 まずは定義。 式 ::= 項 ([+-] 項)* 項 ::= 因子 ([*-] 因子)* 因子 ::= 数 | '(' …

遅延評価のお勉強に、SchemeでHaskellライクなインタプリタを作ってみる。足し算とifしかない。 (define (skell src) (define (forever) (forever)) (define (reader src) (fold (lambda (m cont) (cont (cond ((integer? m) (lambda (x) m)) ((pair? m) (la…

これは面白かった。Problem 79 - Project Euler A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th…

同じような問題があった気がする。Problem 45 - Project Euler Triangle, pentagonal, and hexagonal numbers are generated by the following formulae: Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ... Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ... Hexagon…

40問達成！！Problem 53 - Project Euler There are exactly ten ways of selecting three from five, 12345:123, 124, 125, 134, 135, 145, 234, 235, 245, and 345In combinatorics, we use the notation, 5C3 = 10.In general,nCr = n!/r!(n−r)!,where r …