【追記・2011/01/22】最初に書いた内容に大幅に誤りがあったので, 再度編集しています. おっちょこちょいですみません.【追記・2011/02/03】修正完了. ソースコードを色々変えました.昨日、一昨日の記事には数式に間違いがあったので訂正したまとめ記事を書…

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。 昨日の記事の続きです。昨日は計算式までは出したのですが、実際に計算せずにはいられなかったのでやってみました。Numpy とかあるのは知ってるのですが、標準の Python だけでどこま…

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。 今日は 1 つネタをもらったので, ガチな数学をやろうと思います. お題は「点線で楕円を描く」です.円の場合は, 等角度ごとに区切って点線を書いていけば良いので簡単です. たいていの…

さて前回 mro のトポロジカルソートを使った実装までできたのですが, mro の失敗が検知できない不十分なアルゴリズムで実装してしまいました.今回はその不十分なところを修正するために, 今まで 2 つ (「未探索」と「探索済」) しかなかったノードの状態を 3…

さて今回は C3 アルゴリズムをトポロジカルソートで書けることを示してみましょう. 戦略 さて C3 アルゴリズムの肝は何だったかと言うと, それぞれの親クラスにとっての祖先クラスの順序と, 親クラスどうしの順序が食い違わないように, 祖先クラスを並べるこ…

今日は Perl や Python のクラスの多重継承で使われているアルゴリズム C3 を紹介します.多重継承でメソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません. そしてその順序も決めて…

さて今日は目標の1つであったトポロジカルソートのプログラムを見てみましょう. 基本的な構造は昨日の深さ優先探索 (DFS) と同じです. 今日トポロジカルソートを行う DAG (輪っか無しの矢印グラフ) はこれです. 0 -> 1 -> 3 | `-> 4 | V `-> 2 -> 5 `-> 6昨…

ちょっと今日は趣向を変えて, プログラムで語ってみます.昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます. ソースコード こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG にな…

さて, 今日からは探索やソートの話をしていきます.探索やソートについては以前も触れましたが, ここで簡単におさらいをしておきます. ソート (sort) とは ソートは日本語に訳すと「並びかえ」になります. 文字通りなんらかの順序でものを並べかえる作業のこ…

さて今日は「順序をグラフで書こう」の話の 3 回目.今まで全順序, 半順序と扱ってきましたが, それぞれ順序のルールがかなり縛りのきついものだったので, グラフの形も分かりやすいものでした. 覚えていますか? 全順序は一直線のグラフになりましたし, 半順…

高木貞治プロジェクトとは 2011年1月1日をもって高木貞治先生の著作権が切れ, 著作物の内容を様々な形で利用できるようになりました. そこで著作物の内容を Web 上で公開していくプロジェクトが開始されました.ここがプロジェクト・ホームになると思います. …

だんだん連載記事を書く時刻が遅くなっている cocoatomo です。はてダの日付変更線が3:00くらいらしいので助かってます。追記: 今日は書かずに寝てしまったので、次の日の朝に更新してます。さて今日は昨日持ち越した、半順序をグラフで表現してみようという…

これまで順序の話として全順序, 半順序, 前順序について書いてきました.今日はその順序をグラフで書くとどうなるか? という話をします. 全順序をグラフで では簡単な全順序を用意してそのグラフを見てみましょう.3つの点に A, B, C と名前を付けて, A ≦ B C …

昨日は休講にしてしまいましたが、今日はやります。 さて、一昨日「グラフとはどんなものか?」という話をしました。次にグラフの点の順序付けの話をするのですが、話の展開をどういったペースで書けばいいのかまだ感触が掴めないので、まずは簡単な例から話…

今日は昨日までと話題を変えてグラフの話をします. でも順序の話とつながっている話なのです. どうつながっているかは追々. グラフとは? グラフと聞くと y = f(x) を xy 平面に書いたものを思い浮かべる人がいるかもしれませんが, ここで言うグラフはそのグ…

今日扱うのは「前順序」(preorder) です. (しつこいようですが「全順序」の typo ではないです.) 私の事情で今日は短めにします. 細かいところは端折りますが内容は漏らさずに書くので, 質問などあればコメントや Twitter ( http://twitter.com/cocoatomo ) …

さて今日は「半順序」の話をします. 昨日の全順序 (total order) に比べやや足りないところがあるので,「半順序」(partial order) と言います. どこが足りないかをこれから見ていきましょう. 半順序の定義 さて, まずは定義から行きましょう. 全順序のときと…

古来より日本のプログラマの間には、「正月はフラクタル」という風習があります。 http://d.hatena.ne.jp/ku-ma-me/20110101/p1 ほぉ〜寡聞にして知らなんだ。じゃあ、俺は「正月は数学」という風習を始めてみようと思います。よしっ、今年のテーマは「順序 …

を真の約数( の約数のうち より真に小さいもの)の合計と定義する. もし かつ であり の場合, と を友愛数と呼ぶ.例えば, 220 の真の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので . 284 の真の約数は 1, 2, 4, 71, 142 なので .10000 未満の全ての…

以下のような情報があります. また, 各自で調査しても良いでしょう. 1900年1月1日は月曜日. 小の月は9月, 4月, 6月, 11月. 残りは2月を除いて大の月. 2月は通常は28日だが, 閏年では29日. 閏年は, 4年に1度あり, 100年に1度は閏年でなくなり, さらに400年に1…

数字の1から5までを単語で書くと one, two, three, four, five となり, 全部で3+3+5+4+4=19文字使っています. では, 1から1000(one thousand)までを単語で書くと何文字使うでしょうか?メモ: ハイフンや空白は数に数えません. 例えば, 342 (three hundred and…

正の整数の数列が以下の反復規則で定められている. . 上記のルールを使って13から始めると, 次の数列が得られる. . この数列には(13から1まで)10個の数字が含まれている. これはまだ未解決問題(Collatz 問題)なのだが, どの数字から始めても1に辿り着くと考…

5桁の数 は5乗数でもある. 同様に, 9桁の数 も9乗数である.桁の数でもあり, 乗数でもある正の整数はいくつあるか? http://projecteuler.net/index.php?section=problems&id=63 これは数学で考察を進めるだけで解けました. より, を計算して, 終了.

である. の下10桁を求めよ. http://projecteuler.net/index.php?section=problems&id=48 実装自体は簡単だと高を括って powMod 関数を作ってみたが, 桁あふれに上手く対処できず, 結局 gmp さんの力を借りることにしました. #include <stdio.h> #include <stdlib.h> #include "p</stdlib.h></stdio.h>…

下図の三角形に並べられた数字の一番上からスタートして, 1つ下の行の隣接する数字に移動していったとき, 通った数の合計の最大値は23. つまり, . (訳注. 実は, というルートでも良い.)では, 次の三角形に並べられた数字の一番上から一番下までの合計の最大…

三角数からなる数列は, 自然数を次々と足していくことで得られる. 7番目の三角数は になる. 数列の最初の10項は, となる.三角数の最初の7項について約数を列挙すると, となる. これから, 28 が約数の数が5を越える最小の三角数だと分かる.では, 約数の数が 5…

145 は興味深い数字である. なぜなら, となるからである. 各桁の数字の階乗の合計が自身と等しくなる数の合計を求めよ. ただし, と は含まない. http://projecteuler.net/index.php?section=problems&id=34 「問題30と同じじゃん. プログラムがそのまま使え…

驚くべきことに, 各桁の数字を4乗して合計すると元の数字になる数字は次の3つだけである. ただし, は含まない. それらの数の合計は, .では, 各桁の数字を5乗して合計すると元の数字になる数字の合計を求めよ. http://projecteuler.net/index.php?section=pro…

Fibonacci 数列は再帰的な関係式によって定義されている. . 従って, 最初の12個は, となる. 12番目の が初めて3桁になる数字である.では, 初めて1000桁になるのは何番目か? http://projecteuler.net/index.php?section=problems&id=25 以前の問題 (問題2改 -…

順列は順序が付いた物の並べ替えのことである. 例えば, 3124 というのは 1, 2, 3, 4 という数字の順列の一つである. 全ての順列が数字順もしくはアルファベット順に並んでいるとき, それを「辞書順(lexicographic order)」と呼ぶ. 0, 1, 2 の順列を辞書順に…