太陽系の中で, 地球と火星は双子の惑星といわれる. 公転周期は地球が1年, 火星が2年. 公転半径は地球が1天文単位, 火星が1.6天文単位. (2年の方を知っていれば, Keplerの法則: 公転周期2/公転半径3=一定 から
(expt (expt 2 2) (/ 1 3)) => 1.5874010519681994)
だが, Bodeの法則を知っていれば距離は一発だ.)
この火星には火星人がいると思われていた. 運河らしいものが見えるからだ. 運河かどうかは分からないが, 火星の表面には多数の筋が見え, それが十字形で交差している. 一方, ガラスの割れ目など自然に出来る筋は, 新しい割れ目が既に割れている割れ目を横切らないから丁字形になる.
というわけで, 火星人襲来というSFはいくつかあるらしい. 私が小学生のころ愛読したのに, 海野十三の「火星兵団」がある. ある晩, 千葉県印旛沼の辺りに火星からのロケットが着陸. 火星人が地上に降り立つ.
H.G.Wellsによると, 火星人は, おむすびのような頭から, 糸のような足が生えている, 細い足を持つ蛸のようだと思われていた. 重力が小さいから細い足で支えられる. 食べ物は苔みたいだから, それをなめる口はおおきい. 空気が薄いので音声は伝わらず, 目が口のようにものを言うので, 目もおおきい. 耳は退化した.Wellsはそういう火星人を想像した.
私が小学生のころ, 上野の科学博物館で, こういう火星人を描いた絵はがきを売っていた.
「火星兵団」によると, 火星にくらべて空気の濃い地球では, 潜水服か宇宙服のような容器を着て, 地上で活躍した.
火星人は「ヒュウーヒュウープクプク」というような言葉を喋る. そのままでは日本人には理解出来ぬが, 彼らはすでに日火両語の音声翻訳機を持っていて, 一方から火星語を入れるともう一方から日本語が出る. 逆ももちろん可能.
まぁそういう話であった.
さて今回, NASAの火星探査機フェニックスが火星の北極近くに着地(着火?)したというニュースだ. 送られてきた火星の地上(火上?)の光景は, 運河は見えねど, 想像とあまり違わない. (いちいち「地」を「火」と言い直すのも面倒だねぇ.)
こう描きながら想像するのは, 火星人はフェニックスをみて, 「これが地球人か」と思ったかということだ. 「地球人襲来」というニュースが流れているかと夏の夢を楽しんでいる.
2008年4月24日木曜日
同一直線上の3点
久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした.
翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである.
短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ.
私がやっても多分こういうアプローチになるであろうという風に話は展開していく.
まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒.
次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見るもの. 勾配が無限大になるときはnilを返すようにすると, nil同士もeqで比べればtになるので便利なようだが, 気持は悪い.
3番目はBCの距離a, CAの距離b, ABの距離cを計算し, a,b,cを大きさの順にソートし, 最大の距離が残りの2つの距離の和になるかどうかを見る. この難点はPythagorasの定理で距離を求めるのに関数sqrtを使うことだ. 誤差は避けられない.
このようにして, 最後に辿り着いたのは, 3点で構成する三角形の面積を求め, それが0なら三角形はつぶれて3点は同一直線上にあることが分かるというもの.
たしかに高校生のとき, 三角形 ABC の面積は行列式
の1/2と習った. 面積が0かとうかを見るのだから, 1/2はいらない, 正負も問題にならないから, A,B,Cを反時計まわりにおくことにこだわることもない.
の計算だから誤差も何もない. これで決りだ.
今年の夏のプロシンのテーマは「プログラムの品格」のようなものだ. 本書もひとしきり話題になりそうな予感.
翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである.
短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ.
私がやっても多分こういうアプローチになるであろうという風に話は展開していく.
まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒.
次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見るもの. 勾配が無限大になるときはnilを返すようにすると, nil同士もeqで比べればtになるので便利なようだが, 気持は悪い.
3番目はBCの距離a, CAの距離b, ABの距離cを計算し, a,b,cを大きさの順にソートし, 最大の距離が残りの2つの距離の和になるかどうかを見る. この難点はPythagorasの定理で距離を求めるのに関数sqrtを使うことだ. 誤差は避けられない.
このようにして, 最後に辿り着いたのは, 3点で構成する三角形の面積を求め, それが0なら三角形はつぶれて3点は同一直線上にあることが分かるというもの.
たしかに高校生のとき, 三角形 ABC の面積は行列式
|Ax Ay 1|
|Bx By 1|
|Cx Cy 1|
の1/2と習った. 面積が0かとうかを見るのだから, 1/2はいらない, 正負も問題にならないから, A,B,Cを反時計まわりにおくことにこだわることもない.
(Ax*By+Bx*Cy+Cx*Ay)-(Ax*Cy+Bx*Ay+Cx*By)
の計算だから誤差も何もない. これで決りだ.
今年の夏のプロシンのテーマは「プログラムの品格」のようなものだ. 本書もひとしきり話題になりそうな予感.
2008年4月14日月曜日
dancing links
前回のdancing linksの続きである.
TAOCP 4巻分冊0が4月18日に発売になるとアマゾンからメイルが来た. その分冊0は7章の最初の部分で, そこにGraeco-Latin squareの話題が登場する.
Graeco-Latin squareの作り方は, 互いにorthogonalな2つのlatin squareを用意し, それを合わせればよいのだが, あるlatin square Lからそれとorthogonalなlatin square Mの作り方として, Lからtransversalという組を探す. これは直接orthogonalなlatin squareを作るより容易であると本文に書いてある.
その続きは次のようだ.
Once the transversals are known, we're left with an exact cover problem, of 10 stages, which is much simpler than the original 90 stage problem (6). All we need to do is cover the square with ten transversals that don't intersect --- because every such set of ten is equivalent to a latin square M that is orthogonal to L.
10とか90とかの数値は, ここでは10x10のsquareを求めているからである.
しかしこれだけの説明では, よく分からなかったので, 考えた結果がこのblogの趣旨である.
大きいsquareは面倒なので, 4x4を対象とする.
例えば Lとして
は各行 各列に0,1,2,3が1回ずつ現れるから, latin squareになっている. これとorthogonalなlatin squareを求めるべく, Lのtransversalを探す. transversalはLの各行から1個 各列から1個 各文字から1個をとる組で,
の8個が存在する.
このうちA,B,C,Dを重ねるとちょうどLになり, またE,F,G,Hを重ねてもちょうどLになる.
定義が後回しになったが, LとMがorthogonalというのは, LとMから対応する位置の要素をとって組にすると, 同じ値の組が複数回は出来ないということである.
したがって各transversalの0,1,2,3の位置には0,0,0,0のように同じ値をおけば, orthogonalなlatin squareが得られる. つまり
ができる (LM)の組を作ると M0とM1のそれぞれから
が得られorthogonalなことが分かる.
Lからdancing linksでtransversalを得る方法, transversalを使わず, 直接orthogonalなlatin square(Mateという)を得る方法はTAOCP ex7-17参照のこと.
TAOCP 4巻分冊0が4月18日に発売になるとアマゾンからメイルが来た. その分冊0は7章の最初の部分で, そこにGraeco-Latin squareの話題が登場する.
Graeco-Latin squareの作り方は, 互いにorthogonalな2つのlatin squareを用意し, それを合わせればよいのだが, あるlatin square Lからそれとorthogonalなlatin square Mの作り方として, Lからtransversalという組を探す. これは直接orthogonalなlatin squareを作るより容易であると本文に書いてある.
その続きは次のようだ.
Once the transversals are known, we're left with an exact cover problem, of 10 stages, which is much simpler than the original 90 stage problem (6). All we need to do is cover the square with ten transversals that don't intersect --- because every such set of ten is equivalent to a latin square M that is orthogonal to L.
10とか90とかの数値は, ここでは10x10のsquareを求めているからである.
しかしこれだけの説明では, よく分からなかったので, 考えた結果がこのblogの趣旨である.
大きいsquareは面倒なので, 4x4を対象とする.
例えば Lとして
L=((0 3 1 2)
(2 1 3 0)
(3 0 2 1)
(1 2 0 3))
は各行 各列に0,1,2,3が1回ずつ現れるから, latin squareになっている. これとorthogonalなlatin squareを求めるべく, Lのtransversalを探す. transversalはLの各行から1個 各列から1個 各文字から1個をとる組で,
A=((0 ) B=(( 3 ) C=(( 1 ) D=(( 2)
( 1 ) (2 ) ( 0) ( 3 )
( 2 ) ( 1) (3 ) ( 0 )
( 3)) ( 0 )) ( 2 )) (1 ))
E=((0 ) F=(( 1 ) G=(( 2) H=(( 3 )
( 3 ) (2 ) ( 1 ) ( 0)
( 1) ( 0 ) (3 ) ( 2 )
( 2 )) ( 3)) ( 0 )) (1 ))
の8個が存在する.
このうちA,B,C,Dを重ねるとちょうどLになり, またE,F,G,Hを重ねてもちょうどLになる.
定義が後回しになったが, LとMがorthogonalというのは, LとMから対応する位置の要素をとって組にすると, 同じ値の組が複数回は出来ないということである.
したがって各transversalの0,1,2,3の位置には0,0,0,0のように同じ値をおけば, orthogonalなlatin squareが得られる. つまり
A,B,C,Dから
M0=((0 1 2 3)
(1 0 3 2)
(2 3 0 1)
(3 2 1 0))
E,F,G,Hから
M1=((0 3 1 2)
(1 2 0 3)
(2 1 3 0)
(3 0 2 1))
ができる (LM)の組を作ると M0とM1のそれぞれから
((00 31 12 23) ((00 33 11 22)
(21 10 33 02) (21 12 30 03)
(32 03 20 11) (32 01 23 10)
(13 22 01 30)) (13 20 02 31))
が得られorthogonalなことが分かる.
Lからdancing linksでtransversalを得る方法, transversalを使わず, 直接orthogonalなlatin square(Mateという)を得る方法はTAOCP ex7-17参照のこと.
2008年4月9日水曜日
dancing links
KnuthのTAOCP, 7巻の分冊が出回り始めた. その最初の方にexact cover problemを解くのにdancing linksが適してると書いてある.
dancing linksについてはKnuthが楽しんで書いた論文があり, 講義のビデオも存在する. exact cover proble (日本語では「敷き詰め問題」か) は条件をならべた行列から解の候補を選び, それにより使えなくなった行や列を外し, またback trackするときは, 外した行や列をもとにもどす.
この行列はスパースなので, 上下左右に双方向リンクで実装すると, うまくいくというのがdancing linksの話の味噌である.
私としては面白そうなアルゴリズムを知ったら, さっそくコーディングして例題を走らせ, 体験によってアルゴリズムを理解, 記憶することが多い.
dancing linksについてもさっそくプログラムを書いた. googleで探すとjavaなんかで書いたプログラムも見つかるが, 自分で書くのが楽しいのでschemeで書くことにした.
Knuthの論文の最初の簡単な例題は, 直ぐにうまくいったが, 当然dancing linksを使えばうまく解けると書いてある他の例は, 結構てこずった.
8×8-2×2の60区画にペントミノのピースを置く問題である. ピースXを左上の(3,3)に置くというのに挑戦た. ぜんぜん解が出てこないのである. 当然プログラムがおかしいかといろいろ見てみたが, 合っているとしか思えない.
実は候補の列を選ぶのに, ブランチ数の少ないものを選ぶと書いてあったが, そうしなくても解が出るようにも読めたので, 残っている列の最左端から選んだのが失敗であった. あるとき思いついて, ブランチ数最小の列を選んでみたら, たちまち最初の解が出た. 超簡単な例では, 最左端でも問題なく解が得られたが, ペントミノ程度になると, ブランチ数を考慮する必要があった.
dancing linksの双方向リンクによる削除挿入は, 野下浩平君とその学生の一松宏君が8クイーン問題を解くのに考えたといわれている. しかし縦と横はすべてにクイーンを置くので, exact cover problemであるが, 斜め方向は半分くらいしか埋めないので, この辺の扱いは別になる. Knuthの例の論文をよく読むと, こういうのはgeneralized exact cover problemというので, 列にはprimaryとsecondaryを用意する. primaryの列名は双方向リンクで接続するが, secondaryの列名は自分自身で循環するリンクにすると書いてあった. そういう風にプログラムをなおすと, なるほどうまく行った.
数独にも適しているといわれるdancing linksである. 数独ではいくつかの解が与えられているので, 解を探し始める前に, 与えられた解について列や行を削除する(coverする)必要がある. 解に相当する行を探す手間が必要で, この辺はプログラムでかなり工夫が必要であった.
最後に, 上下左右に双方向リンクにしないでも, 実装できるのではないかとプログラムをしてみた. ノードはlispの対で, carに下へのリンク, cdrに右へのリンクを置き, 循環するようにリストを実装すると, たしかにこれでもうまく出来ることがわかった.
dancing linksについてはKnuthが楽しんで書いた論文があり, 講義のビデオも存在する. exact cover proble (日本語では「敷き詰め問題」か) は条件をならべた行列から解の候補を選び, それにより使えなくなった行や列を外し, またback trackするときは, 外した行や列をもとにもどす.
この行列はスパースなので, 上下左右に双方向リンクで実装すると, うまくいくというのがdancing linksの話の味噌である.
私としては面白そうなアルゴリズムを知ったら, さっそくコーディングして例題を走らせ, 体験によってアルゴリズムを理解, 記憶することが多い.
dancing linksについてもさっそくプログラムを書いた. googleで探すとjavaなんかで書いたプログラムも見つかるが, 自分で書くのが楽しいのでschemeで書くことにした.
Knuthの論文の最初の簡単な例題は, 直ぐにうまくいったが, 当然dancing linksを使えばうまく解けると書いてある他の例は, 結構てこずった.
8×8-2×2の60区画にペントミノのピースを置く問題である. ピースXを左上の(3,3)に置くというのに挑戦た. ぜんぜん解が出てこないのである. 当然プログラムがおかしいかといろいろ見てみたが, 合っているとしか思えない.
実は候補の列を選ぶのに, ブランチ数の少ないものを選ぶと書いてあったが, そうしなくても解が出るようにも読めたので, 残っている列の最左端から選んだのが失敗であった. あるとき思いついて, ブランチ数最小の列を選んでみたら, たちまち最初の解が出た. 超簡単な例では, 最左端でも問題なく解が得られたが, ペントミノ程度になると, ブランチ数を考慮する必要があった.
dancing linksの双方向リンクによる削除挿入は, 野下浩平君とその学生の一松宏君が8クイーン問題を解くのに考えたといわれている. しかし縦と横はすべてにクイーンを置くので, exact cover problemであるが, 斜め方向は半分くらいしか埋めないので, この辺の扱いは別になる. Knuthの例の論文をよく読むと, こういうのはgeneralized exact cover problemというので, 列にはprimaryとsecondaryを用意する. primaryの列名は双方向リンクで接続するが, secondaryの列名は自分自身で循環するリンクにすると書いてあった. そういう風にプログラムをなおすと, なるほどうまく行った.
数独にも適しているといわれるdancing linksである. 数独ではいくつかの解が与えられているので, 解を探し始める前に, 与えられた解について列や行を削除する(coverする)必要がある. 解に相当する行を探す手間が必要で, この辺はプログラムでかなり工夫が必要であった.
最後に, 上下左右に双方向リンクにしないでも, 実装できるのではないかとプログラムをしてみた. ノードはlispの対で, carに下へのリンク, cdrに右へのリンクを置き, 循環するようにリストを実装すると, たしかにこれでもうまく出来ることがわかった.
2008年3月23日日曜日
中山道
以前から少しずつ歩いていた中山道533Kmも遂に京都三条大橋へ辿り着いた. (詳しくいえば草津宿から大津宿を経て三条大橋までは旧東海道) 一緒に歩いてくれた多田君, 寺田君, 岩崎君に感謝したい. 実はまだ日本橋から本郷東大前を通り埼京線板橋駅まで8Kmが残っているが, これは車やバスで幾度も通り, 勝手知ったる道なので, もう済んだようなものでもある.
中山道は人気があり, 解説書やウェブページも多く, 歩こうと思えば問題は少ない. われわれは「ボクたちが歩く中山道」を手引きにした. また歩き出してから気づいたが, 道中処々に赤いシールが貼ってあり, 分岐点などで重要な道案内になっていた. 誰が貼ったのか知らないが有り難かった.
トラックがびゅんびゅん走る国道を歩くこともあったが, だいたいは静かな田舎道で, スローライフそのものである. それと引換えに山道では, 宿泊場所が左程ない; 食堂は国道を横切るときに探すしかない; という制約があることも判明した.
それにしても春秋のよい季節にのんびり歩けるのは最高であった. 昔の人は16日で歩き通したらしいから, 1日あたり33Km程度の速さである. これではのんびり歩く気分ではなかったを思われる. (中山道最大のイベント和宮東下でも25日) われわれは半日行程では10～15Km. 1日行程では20～25Kmであった.
昔と違うのは電車線と併走している場合, 草臥れると最寄駅から電車で宿泊地へ向かい, 翌日また電車で戻って歩き出せたことであった. 追分～下諏訪, 大井～太田のような山道区間を除けば行程はかなりフレキシブルであった.
自治体により中山道の周知は様々であった. 「歴史の道 中山道」の道標が立っているところもあれば, 全く無関心な町もあった. 中山道の保存にもっと尽力して欲しいものである. 中山道を歩く人がさらに増えるように.
中山道は人気があり, 解説書やウェブページも多く, 歩こうと思えば問題は少ない. われわれは「ボクたちが歩く中山道」を手引きにした. また歩き出してから気づいたが, 道中処々に赤いシールが貼ってあり, 分岐点などで重要な道案内になっていた. 誰が貼ったのか知らないが有り難かった.
トラックがびゅんびゅん走る国道を歩くこともあったが, だいたいは静かな田舎道で, スローライフそのものである. それと引換えに山道では, 宿泊場所が左程ない; 食堂は国道を横切るときに探すしかない; という制約があることも判明した.
それにしても春秋のよい季節にのんびり歩けるのは最高であった. 昔の人は16日で歩き通したらしいから, 1日あたり33Km程度の速さである. これではのんびり歩く気分ではなかったを思われる. (中山道最大のイベント和宮東下でも25日) われわれは半日行程では10～15Km. 1日行程では20～25Kmであった.
昔と違うのは電車線と併走している場合, 草臥れると最寄駅から電車で宿泊地へ向かい, 翌日また電車で戻って歩き出せたことであった. 追分～下諏訪, 大井～太田のような山道区間を除けば行程はかなりフレキシブルであった.
自治体により中山道の周知は様々であった. 「歴史の道 中山道」の道標が立っているところもあれば, 全く無関心な町もあった. 中山道の保存にもっと尽力して欲しいものである. 中山道を歩く人がさらに増えるように.
2008年3月12日水曜日
2008年3月8日土曜日
3シリンダ機関車
時間があったので鉄道博物館へいった. いつも何か発見があり楽しい.
国産の3シリンダ機関車C53の走り装置が置いてあった. 3シリンダ機関車は, 両側のシリンダは普通の蒸気機関車のとそっくりだが, 外から見えない台車の中央に3つめのシリンダーがある.
その中央のシリンダからはクランク軸になっている動輪に力を伝達する. 問題は中央の制御シャフトがどうなっているかであるが, 実に意外な構造であった. 両側の滑り弁を動かす制御シャフトが機関車の先頭の方へ突き抜け, それをリンクでつないで中央の制御シャフトを動かすのであった.
googleで探したら,
http://www.watercressline.co.uk/tw/pics/bitn2to1.jpg
にその図解があった.
こういう計算をしてみた. 一方の制御シャフトの動きをa, 他方のそれをb, 中央のそれをcとする.
a=sin x
b=sin (x+2π/3) = sin x cos 2π/3 + cos x sin 2π/3=-1/2 sinx + √3/2 cos x
c=sin (x+4π/3) = sin x cos 4π/3 + cos x sin 4π/3=-1/2 sinx - √3/2 cos x
これを眺めると a + b = -c とわかる.
たしかにベンツのマークのような, 120度ずつはなれたベクトルをa, b, cとすると, a+bはcと反対向きのベクトルになるから, 納得できる.
さて上の図解によると, 下のvalve spindle linkの動きをfulcrum pinを中心にして2 to 1 leverで上へ伝達する. その点を中心として, 上のvalve spindle linkの動きをequal leverで中央のvalve spindle linkへ伝えている.
従って, 下の動きをaとすると, 2 to 1 leverの上の動きは -1/2 aになる. 上の動きをb, 中央の動きを x とすると, bとxの平均が-1/2 aなのだから (x + b)/2 = -1/2 a. したがって x = - (a + b)となり, ちょうどcの動きとなっている.
すばらしい.
国産の3シリンダ機関車C53の走り装置が置いてあった. 3シリンダ機関車は, 両側のシリンダは普通の蒸気機関車のとそっくりだが, 外から見えない台車の中央に3つめのシリンダーがある.
その中央のシリンダからはクランク軸になっている動輪に力を伝達する. 問題は中央の制御シャフトがどうなっているかであるが, 実に意外な構造であった. 両側の滑り弁を動かす制御シャフトが機関車の先頭の方へ突き抜け, それをリンクでつないで中央の制御シャフトを動かすのであった.
googleで探したら,
http://www.watercressline.co.uk/tw/pics/bitn2to1.jpg
にその図解があった.
こういう計算をしてみた. 一方の制御シャフトの動きをa, 他方のそれをb, 中央のそれをcとする.
a=sin x
b=sin (x+2π/3) = sin x cos 2π/3 + cos x sin 2π/3=-1/2 sinx + √3/2 cos x
c=sin (x+4π/3) = sin x cos 4π/3 + cos x sin 4π/3=-1/2 sinx - √3/2 cos x
これを眺めると a + b = -c とわかる.
たしかにベンツのマークのような, 120度ずつはなれたベクトルをa, b, cとすると, a+bはcと反対向きのベクトルになるから, 納得できる.
さて上の図解によると, 下のvalve spindle linkの動きをfulcrum pinを中心にして2 to 1 leverで上へ伝達する. その点を中心として, 上のvalve spindle linkの動きをequal leverで中央のvalve spindle linkへ伝えている.
従って, 下の動きをaとすると, 2 to 1 leverの上の動きは -1/2 aになる. 上の動きをb, 中央の動きを x とすると, bとxの平均が-1/2 aなのだから (x + b)/2 = -1/2 a. したがって x = - (a + b)となり, ちょうどcの動きとなっている.
すばらしい.
登録:
投稿 (Atom)
