2010年4月29日木曜日

Prolog始めたよ

Prologというプログラミング言語があります.Prologは論理型言語の一つで,一階述語論理に基づいて命題を与え,その命題が正しいかを再帰的手続きによって探索する言語である,とのことです.

処理系にはSWI-Prologを用いました.ダウンロードは↓から.
SWI-Prolog's home

入門はこちら.
M.Hiroi's Home Page / Prolog Programming

事実,規則:
fly(X) :- airplane(X).
airplane(jet_plane).
airplane(helicopter).

質問:
?- fly(jet_plane).
YES
?- fly(taro).
NO

こんな感じ.
時間がある時に適当に記事を書く予定です.

2010年4月25日日曜日

セルオートマトン #24 ルール22

ルール22
クラス3

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



Fig.1 rule22

2010年4月18日日曜日

セルオートマトン #23 ルール21

ルール21
クラス2

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



Fig.1 rule21

左にゆっくりと移動していますが,左程珍しくないです.

2010年4月17日土曜日

TopCoder 練習

RabbitNumbering(SRM463 DIV1 Easy)
AgeEncoding(SRM462 DIV1 Easy)

AgeEncodingは2分法で基本的には解けましたが,場合分けで若干苦戦しました.

プログラム・プロムナード 最大長方形の面積

下記の連載「プログラム・プロムナード」には,有益なアルゴリズムが色々と載っているので実装してみました.

プログラム・プロムナード
http://www.ipsj.or.jp/07editj/promenade/index.html

2002年4月号 最大長方形の面積(和田英一)

import java.util.*;
import java.awt.*;

public class Main{

// 単純なループによる実装 O(n^6)
private int count1(int[][] a){
int res=0;
int m=a[0].length;
int n=a.length;
for(int y1=0;y1<n;y1++){
for(int x1=0;x1<m;x1++){
// 始点-(x1, y1)
for(int y2=y1;y2<n;y2++){
for(int x2=x1;x2<m;x2++){
// 終点-(x2, y2)
int c=0;
// (x1, y1)-(x2, y2)から構成される長方形内の1の個数を数える
for(int j=y1;j<=y2;j++)
for(int i=x1;i<=x2;i++)
if(a[j][i]==1)
c++;
// 長方形内のマスが全て1であり
// 長方形の大きさ(=c)が今までの最大値より大きい場合は更新
if(c==(x2-x1+1)*(y2-y1+1))
if(c>res)
res=c;
}
}
}
}
return res;
}

// 動的計画法による実装
private int count2(int[][] a){
int m=a[0].length;
int n=a.length;
int max=0;
LinkedList<Point>[][] lists=(LinkedList<Point>[][])new LinkedList[n][m];;
LinkedList<Point> temp=new LinkedList<Point>();

for(int j=0;j<n;j++)
for(int i=0;i<m;i++)
lists[j][i]=new LinkedList<Point>();

for(int j=0;j<n;j++){
for(int i=0;i<m;i++){
if(a[j][i]==0)
continue;
int up, left;
for(up=0;j-up>=0&&a[j-up][i]==1;up++)
;
for(left=0;i-left>=0&&a[j][i-left]==1;left++)
;
// 上隣=0,左隣=0
if((i==0||a[j][i-1]==0)&&(j==0||a[j-1][i]==0)){
// (1, 1)
lists[j][i].add(new Point(1, 1));
}
// 上隣=0,左隣=1
else if(j==0||a[j-1][i]==0){
// (左方に続く1の個数, 1)
lists[j][i].add(new Point(left, 1));
}
// 上隣=0,左隣=1
else if(i==0||a[j][i-1]==0){
// (1, 上方に続く1の個数)
lists[j][i].add(new Point(1, up));
}
// 上隣=1,左隣=1
else{
for(Point p:lists[j][i-1])
lists[j][i].add(new Point(p.x+1, Math.min(p.y, up)));
for(Point p:lists[j-1][i])
lists[j][i].add(new Point(Math.min(p.x, left), p.y+1));
}

// 重複要素の削除
for(Point p:lists[j][i])
if(!temp.contains(p))
temp.add(p);
lists[j][i].clear();

// qより大きい長方形が存在したらqをリストに追加しない
for(Point q:temp){
for(Point p:temp){
if(q!=p&&q.x<=p.x&&q.y<=p.y){
q=null;
break;
}
}
if(q!=null)
lists[j][i].add(q);
}
temp.clear();

for(Point p:lists[j][i])
max=Math.max(max, p.x*p.y);
}
}
return max;
}

public static void main(String[] args){
int[][] a;
a=new int[50][50];
for(int j=0;j<a.length;j++)
for(int i=0;i<a[0].length;i++)
a[j][i]=(int)(Math.random()*2);
System.out.println("1:"+new Main().count1(a));
System.out.println("2:"+new Main().count2(a));
}
}


マージしないでも動作するかな?と思って,マージの実装を外して検証してみましたが,リストに保存する長方形が爆発的に増えた為,メモリが足りませんでした.

2010年4月11日日曜日

セルオートマトン #22 ルール20

ルール20
クラス2

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



Fig.1 rule20

見たまんまです.■が右に連なっていきます.

2010年4月7日水曜日

数学 #16 ミルズの定理

ミルズの定理という過激な定理があったので御紹介.

Mills' Theorem -- from Wolfram MathWorld
httphttp://mathworld.wolfram.com/MillsTheorem.html

Mills' Constant -- from Wolfram MathWorld
http://mathworld.wolfram.com/MillsConstant.html

ミルズの定理(Mills' theorem)

すべての自然数nについて
3n]
の値が素数になるようなθが存在する.

例えば,
θ=1.30637788386308069046861449260260571291678458515671364436805375996643405376682659882150140370119739570729+

実際には,θの精度を無限大にしなければ素数を得ることはできません.が,試しに上のθでどこまで素数が出るかやってみました.

θ31=2.229494772491595
θ32=11.082031369896242
θ33=1361.0000010797248
θ34=2.5210088869999886E9
θ35=1.6022236204009632E28
θ36=4.113101149214954E84
θ37=6.958380437695496E253
θ38=Infinity
やはりバカでかい値になります,n=1~4までの値を切り下げると,

31]=2
32]=11
33]=1361
34]=2521008886
n=4の場合が素数じゃないですが,実際の値は2521008887です.

色々と無理があったので,オンライン整数列大辞典(On-Line Encyclopedia of Integer Sequences)にて調べました.

On-Line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/

31]=2
32]=11
33]=1361
34]=2521008887
35]=16022236204009818131831320183
36]=4113101149215104800030529537915953170486139623539759933135949994882770404074832568499

2010年4月6日火曜日

TopCoder 練習

ColorfulStrings(SRM465 DIV1 Easy)

TopCoder SRM 466

SRM466(4/4 1:00~3:00)

・LotteryCheating(DIV1 Easy)
約数が奇数個⇔平方数には気付いたのですが,ちょっと実装が粗かった為System Testで落ちました.後で見ましたが,Petr先生が提出したソースの美しいこと….
Result:Failed System Test(0p)

・LotteryPyaterochka(DIV1 Normal)
組合せの問題ですが,組合せには鈍く,式が立てられませんでした.
Result:Opend(0p)

・DrawingBlackCrosses(DIV1 Hard)
\(^o^)/
Result:Opened(0p)

・Challenges
0p

・Rating
1344->1292
1200台に落ちてしまいました.今後はDiv1の問題を出来るだけ多く解いて練習しておこうかと.
Yellow(1500以上)への道は遠い….

2010年4月4日日曜日

Project Euler

problem 24

TopCoder 練習

TurretPlacement(Member SRM465 DIV1 Easy)
LotteryCheating(SRM466 DIV1 Easy)

セルオートマトン #21 ルール19

ルール19
クラス2

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



Fig.1 rule19

白黒繰り返しの状態に落ち着いてしまいました.