スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Ruby…エ

今日は同窓会だったけど、レポート置き去りにしてたことに気づいてオワこんだった。
企画してくれたのに、すま~ん。




何の、レポートかというと、ハノイの塔のプログラム。
ハノイの塔って知ってます?知らないなら、ここでも見てくれい。
http://ja.wikipedia.org/wiki/ハノイの塔

大きさnのハノイの塔について、これを動かしていく様子が見れるような
プログラムをRubyで作ってくれいってのがレポートでした。

以下、プログラムの話なんで、つまんないです。



Wikipediaにも載ってるんだけど、コンピュータ的には再帰的な解き方が普通らしい。
まぁ、そこはいいんだけど、どうもプログラムを一から作るのがちょーだるかったので、
シケタイのものをそのままパクリ引用させてもらいました。

でまぁ、これが模範的なプログラムだと思われる。

def make1d(n) # Creates the sigle dimensional empty image.
image=Array.new(n)
for i in 0..n-1
image[i]=0
end
image
end

def make2d(w,h) # Creates the two dimensional empty image.
image=Array.new(h)
for i in 0..h-1
image[i]=make1d(w)
end
image
end


def first_hanoi(n) # Creates the image of the first stage.
img=make2d(6*n-3,n) # "n" stands for the size of the first hanoi.
for i in 1..n
for j in (n-i)..(n+i-2)
img[i-1][j]=1
end
end
img
end

def g(img,n,y) # Describes the hieght of the hanoi in the "y" row.
if img[0][(2*n-1)*y+n-1]==1
-1
else
g=n-1
while img[g][(2*n-1)*y+n-1]==1
g=g-1
end
g
end
end

def create(img,n,x,y) # Creates the "x" size disk in the "y" row.
g=g(img,n,y)
for i in ((2*n-1)*y+n-x)..((2*n-1)*y+n+x-2)
img[g][i]=1
end
end

def delete(img,n,x,y) # Deletes the "x" size disk in the "y" row.
g=g(img,n,y)+1
for i in ((2*n-1)*y+n-x)..((2*n-1)*y+n+x-2)
img[g][i]=0
end
end

def subhanoi(img,n,m,f,t,b) # Moves the m size hanoi tower from the f row to the t row.
if m==0 # "m" stands for the size of hanoi to move.
"done" # This value will be actually seen only in the end of the process.
else
subhanoi(img,n,m-1,f,b,t)
delete(img,n,m,f)
create(img,n,m,t)
show(img)
gets()
subhanoi(img,n,m-1,b,t,f)
end
end

def hanoi(n) # Shows the first image, and pressing Enter key, the second image and goes on to the further stages.
img=first_hanoi(n)
show(img)
gets()
subhanoi(img,n,n,0,2,1)
end



うん、さすがシケタイ。素人の僕の目から見ると、無駄がない気がする。
後半で、関数subhanoiってのが定義されているんだけど、これが本体で、
subhanoiの中に、subhanoiが入れ子になって入っているでしょ?
これが、再帰関数の特徴で、単純な試行になるまで、どんどん掘り下げていくってこと。





で、Wikipediaにもう一つの方法があって、これはもう答えを知ってることを前提としていて、
一番小さい円盤を動かして、次にその他の円盤を動かす、ってのを繰り返すっていう方法。

さすがに、パクリだけを提出するのが気が引けたので、素人の僕なりに頑張って、
こっちのアルゴリズムで作ってみました。

def make1d(n) # Creates the sigle dimensional empty image.
image=Array.new(n)
for i in 0..n-1
image[i]=0
end
image
end

def make2d(w,h) # Creates the two dimensional empty image.
image=Array.new(h)
for i in 0..h-1
image[i]=make1d(w)
end
image
end

def hanoi_first(n) # Creates the image of first stage.
a=make2d(6*n-3,n) # "n" stands for the size of the first hanoi.
for i in 1..n
for j in (n-i)..(n+i-2)
a[i-1][j]=1
end
end
a
end

def g(a,n,y) # Describes the hieght of the hanoi in the "y" row.
if a[0][(2*n-1)*y+n-1]==1
-1
else
g=n-1
while a[g][(2*n-1)*y+n-1]==1
g=g-1
end
g
end
end

def enban(a,n,x,y) # Creates the "x" size disk in the "y" row.
g=g(a,n,y)
for i in ((2*n-1)*y+n-x)..((2*n-1)*y+n+x-2)
a[g][i]=1
end
end

def zero(a,n,x,y) # Deletes the "x" size disk in the "y" row.
g=g(a,n,y)+1
for i in ((2*n-1)*y+n-x)..((2*n-1)*y+n+x-2)
a[g][i]=0
end
end

def hanoix(n)
a=hanoi_first(n)
show(a)
gets()
zero(a,n,1,0)
enban(a,n,1,n%2+1)
show(a)
gets()
while !biggest_top_one(a,n)
ss=second_size(a,n)
tor=the_other_row(a,n)
zero(a,n,ss,second_row(a,n))
enban(a,n,ss,tor)
show(a)
gets()
onr=one_row(a,n)
if n%2==0
if onr!=2
onrt=onr+1
else
onrt=0
end
else
if onr!=0
onrt=onr-1
else
onrt=2
end
end
zero(a,n,1,onr)
enban(a,n,1,onrt)
show(a)
gets()
end
end

def topsize(a,n,y)
g=g(a,n,y)+1
size=0
if g==n
0
else
for i in ((2*n-1)*y)..((2*n-1)*y+n-1)
size=size+a[g][i]
end
size
end
end

def biggest_top_one(a,n)
x=topsize(a,n,0)
y=topsize(a,n,1)
z=topsize(a,n,2)
if x+y+z==1
true
else
false
end
end

def one_row(a,n)
x=topsize(a,n,0)
y=topsize(a,n,1)
z=topsize(a,n,2)
if x==1
0
else
if y==1
1
else
2
end
end
end

def second_size(a,n)
x=topsize(a,n,0)
y=topsize(a,n,1)
z=topsize(a,n,2)
if x==0
if y==1
z
else
y
end
else
if y==0
if x==1
z
else
x
end
else
if z==0
if x==1
y
else
x
end
else
if x>y
if x>z
if y>z
y
else
z
end
else
x
end
else
if y>z
if x>z
x
else
z
end
else
y
end
end
end
end
end
end

def second_row(a,n)
x=topsize(a,n,0)
y=topsize(a,n,1)
z=topsize(a,n,2)
if x==second_size(a,n)
0
else
if y==second_size(a,n)
1
else
2
end
end
end

def the_other_row(a,n)
if 0!=one_row(a,n)&&0!=second_row(a,n)
0
else
if 1!=one_row(a,n)&&1!=second_row(a,n)
1
else
2
end
end
end



前半は、さっきのパクリと同じで、関数hanoix以下の関数が、自前で作ったやつです。
うーん、ゴミみたいに長いね。second_sizeとか何回if else使ってるのって感じだね。もっと、簡素にできるやろ。

まぁ、スリムにするのも頭使うけど、プログラミングって、どこか一つでも記述間違いがあったら、
ちゃんと動いてくれないから、これがすごく疲れた。何度もトライ&エラーを繰り返して、その度に
どの行が間違えているのか考えて修正していったわ・・・。

こんなのまだ雑魚レベルだろうけど、デバッグの大変さを思い知りました(笑)

明日から学校です。期末嫌だー(笑)
スポンサーサイト
プロフィール

SHUN

Author:SHUN

アクセス数
最近の記事とコメント
カレンダー
12 | 2012/01 | 02
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -
月別アーカイブ
カテゴリ
Vocaloid Ranking Watcher
全記事表示リンク

全ての記事を表示する

Evangelion
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

個人的 神曲
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。