2009年11月27日金曜日

カオス #26 馬蹄写像

楽しい写像の御提供.

馬蹄写像

馬蹄写像は下のような2変数写像です.固定された数式では無いので,定義域,値域をそれぞれ図示しています.


Fig.1 馬蹄写像
2つの半円D1,D2と正方形Sが定義域です.図では赤のチェックの領域です(一部隠れています).
馬蹄写像を定義域全体に対して適用すると,定義域を折り曲げたような形になります.図では青のチェックの領域分です.この値域の形が馬蹄に似ているから馬蹄写像と呼ぶのです.

この写像を2回適用するとFig.2のようになります.


Fig.2

3回適用.


Fig.3

繰り返すと倍々に折り重なっていくのが分かります.また,D1,D2内に入った点は以後そこから出られなくなります(D1内の点はD1内へ,D2内の点はD2内へ写像するから).そして最終的にD1,D2内に入る点は到る所無数にあるので,初期値の極僅かな差によって最終的な挙動が全く変わります.ロジスティック写像の2次元版みたいな感じです.

疑似コードはこんな感じ.上にも書いた通り,固定された数式ではないので,別にこのような定義でなくともかまいません.


horseshoe(x, y)
if(-1/2≦x≦1/2 && -1/2≦y≦1/2) # Sに含まれる
if(-1/2≦x≦-1/8)
u=map(x, -1/2, -1/8, -5/8, 1/2)
v=map(y, -1/2, 1/2, 1/8, 3/8)
else if(1/8≦x≦1/2)
u=map(x, 1/8, 1/2, 1/2, -5/8)
v=map(y, -1/2, 1/2, -1/8, -3/8)
else # -1/8≦x≦1/8 Uの字に曲がる所
r=map(y, -1/2, 1/2, 1/8, 3/8)
d=map(x, -1/8, 1/8, π/2, -π/2)
u=r・cos(d)+1/2
v=r・sin(d)
return (u, v)
else if(dist(-1/2, 0, x, y)≦1/2) # D1に含まれる
u=map(x, -1, -1/2, -3/4, -5/8)
v=map(y, -1/2, 1/2, 1/8, 3/8)
return (u, v)
else if(dist(1/2, 0, x, y)≦1/2) # D2に含まれる
u=map(x, 1/2, 1, -5/8, -3/4)
v=map(y, -1/2, 1/2, -1/8, -3/8)
return (u, v)
else # 定義域外
return null

map(value, low1, high1, low2, high2)
return (value-low1)(high2-low2)/(high1-low1)+low2;

dist(x1, y1, x2, y2)
return sqrt(sq(x2-x1)+sq(y2-y1))



写像する様子を映像化するとこんな感じ(イメージです).

2009年11月18日水曜日

TopCoder イントロダクション

TopCoderの紹介.

■TopCoderって何ですか?
定期的にネット上で開催されるプログラミングコンテスト.世界中の人が集まりコーディングで競います.

TopCoder
http://www.topcoder.com/

沢山の大会がありますが,その中でも特に盛り上がるのがSRM(Single Round Match)です.以下,その詳細をご紹介.

■参加資格
特に無し.ただし,事前にメンバ登録しておく必要があります.詳細は略.

■使用可能言語
Java,C++,C#,VBの4つ.

■競技概要
・参加登録
大会開始3時間前から参加登録が始まります.開始5分前になると,参加者達は,ある程度レベルにばらつきが出るように20人程度のRoomに振り分けられます.
そしてコンテスト開始,以下のような流れで行われます.
・Coding Phase
制限時間75分間で3つの問題を解きます.この75分間でコードを書き,提出しなければなりません.速く提出した方が高得点となります.
・Intermission
5分間休憩.
・Challenge Phase
ここでは,Room内の相手のソースを読み,誤った出力が得られそうな(バグが出そうな)入力を与えてやります(Challenge).ここで見事撃墜(Challenge成功)すると,自分の得点が+50p,相手の得点は0p.逆にChallengeに失敗すると,自分の得点が-25p.
・System Test
提出されたプログラムが「本当に」正しいかを検証するために,主催者側が用意した入出力を用いた「テスト」を行います.このシステムテストに合格すると得点獲得,不合格(正しい出力が得られなかった)になると得点は0p.

大体このような感じです.ちなみに,これら一連の内容はArenaというJavaアプリケーション上で行われます.競技終了後,計算式に従って,各レーティングが更新されます(1p以上だったとしても,現在のレーティングから落ちる可能性がある).

また,現在の得点によって以下のように色が振り分けられます.
2200p以上の「RedCoder」になると崇められます.更に,3000p以上になると「Target」となり,赤丸の中に白丸が入ります.

レーティング
初参加
0~899
900~1199
1200~1499
1500~2199
2200~
3000~Target


是非,挑戦してみて下さい.

2009年11月17日火曜日

セルオートマトン #7 ルール5

ルール5
クラス2

時刻tでの状態■■■■■□■□■■□□□■■□■□□□■□□□
時刻t+1での状態


時刻0で白:両脇が白なら次は黒,両脇のどちらかが黒ならずっと白.
時刻0で黒:両脇が白ならずっと黒,両脇のどちらかが黒なら白-黒-白-黒-…


Fig.1 rule5

こんな感じ.時刻1以降は周期2.

2009年11月15日日曜日

TopCoder 練習

11/15
WidgetRepairs(SRM150 DIV2 Easy)
InterestingDigits(SRM150 DIV2 Medium)

8/2
TheEncryptionDivTwo(SRM445 DIV2 Easy)
TheNewHouseDivTwo(SRM445 DIV2 Easy)

8/3
FourBlocksEasy(SRM444 DIV2 Easy)
SoccerLeagues(SRM443 DIV2 Easy)
CirclesCountry(SRM443 DIV2 Medium)

2009年11月14日土曜日

TopCoder 練習

11/14
BinaryCode(SRM144 DIV1 Easy)
PrefixCode(SRM151 DIV2 Easy)

BinaryCodeは分からなかったのでProblem Archiveを見ながら.

TopCoderの詳細については後日.

2009年11月11日水曜日

ねこぢる草

たまにはアニメーションについてでも.

『ねこぢる草』

発売:2001年2月21日
原作:ねこぢる
監督:佐藤竜雄
脚本・演出:佐藤竜雄,湯浅政明
絵コンテ・作画監督:湯浅政明
時間:33分

あらすじ:
(ある日)にゃーこは,死神に魂を半分奪われてしまい元気が無くなってしまう.そんな姉(にゃーこ)を気遣い,にゃっ太はにゃーこを連れてサーカスへ.だが,2人はそこから不思議な世界に迷い込んでしまう.果たして2人は無事に帰って来れるのか…

原作者のねこぢるは,1990年に『ガロ』にて『ねこぢるうどん』でデビュー.作品の多くは猫を主人公とする形式でした.特に「にゃーこ」・「にゃっ太」の姉弟を主人公とする連作は人気が高く,一見可愛いキャラクターが繰り広げる不条理・残酷なストーリーは,一部でカルト的な人気を得ていました.彼女は1998年,自殺により31歳の若さで亡くなっています.
その後,作られたOVAが『ねこぢる草』です.

この作品ではオリジナルストーリー(あらすじ参照)を軸に『ねこぢるうどん』の各シチュエーションを織り込んであります.
夢を見ている,極端に言うと臨死体験にも似た展開は何度見ても飽きが来ません.また,短編ですので非常に密度が濃く,映像作品として完成度の高いものとなっています.ラストシーンは是非自分の目でご覧になって下さい.

ちなみにこの作品では湯浅政明の存在が大きく,彼の作品の特徴が強く表れていると思います.
詰まる所,劇場版『クレヨンしんちゃん』の作画のような,具体的には強烈なパースや特徴のある気持ちの良い動きです.







時間があれば,一度見てみることをお勧めします.

2009年11月8日日曜日

数学 #11 数値解析 #4 台形則

数値計算ネタ.

積分の近似計算です.今回も対象として,フレネル積分を用います.
しかし,計算方法が違います.今回は台形則という方法を使います.


参考までにフレネル積分(sin版).


台形則

式はこんな感じです.



式だけだと意味不明なので,図をFig.1に示します.


Fig.1 trapezoid

赤線:y=sin(x2)
青い台形一つの面積:h/2(f(xi)+f(xi+1)

台形のパラメタは以下の様に対応.Fig.1ではh=0.25です.
上底:f(xi)
下底:f(xi+1
高さ:h=x軸の刻み幅
ですので,青い台形の面積の総和をとる式を構成すると,始めに示した式が出来上がります.

また,h(刻み幅)が小さければ小さいほど,計算の精度が上がる事も分かると思います(台形がどんどん細くなり誤差が減っていく).例えば,h=1/16の時はFig.2のようになります.青の面積を全て足し合わせたものが近似値なので,精度が高くなる事が納得できると思います.


Fig.2

実際にFig.1のパラメタで計算したのがFig.3.


Fig.3
0≦x≦8
h=1/4
刻み幅が大きいので,かなりがたついています(ただ,前回の様に発散してはいません).

hを小さくすると(Fig.2と同じ)Fig.4のような感じ.


Fig.4
0≦x≦8
h=1/16

非常に滑らかになり,精度が大幅に向上しています.