11/15 第6回アルゴリズムと計算量

前回までの補足

講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．
irbの中で，ファイル"test.rb"を読み込むには，loadコマンドよりは，
```
source "test.rb"
```
の方が良いようだ．

10/25の課題について

締切は，11/22. 11/15 14:00 時点で提出者は5名．コメントを付けておいたので今後の参考にするように．

コメント欄に書ききれなかった質問に対して回答する．

Q.

駅の番号を誤入力されたときに、質問をし続ける関数を作ろうと思ったが、変数のスコープが関数の外までは有効でないらしく、

print "¥n", "出発駅の番号は？"
start = gets.to_i
while abs((start-1)/19)>0
print "番号が正しくありません。上のリストから選んでください。", "¥n", "出発駅の番号は？"
start = gets.to_i
end
print "到着駅の番号は？"
goal = gets.to_i
while abs((goal-1)/19)>0
print "番号が正しくありません。上のリストから選んでください。", "¥n", "到着駅の番号は？"
goal = gets.to_i
end

のように出発駅と到着駅について同じ操作を必要としてしまった．

A.

def getStation type
  while true
    print "\n", type,"の番号は？"
    station = gets.to_i
    if 1<=station && station<=ginza.size()
      return station
    end
    print "番号が正しくありません。上のリストから選んでください。\n"
  end
end

のようなメソッドを作って，

start=getStation "出発駅"
goal=getStation "到着駅"

と呼び出すのが良いでしょうね．

Q.

他のクラスからインスタンス変数にアクセスするには，

class Station
  def initialize(a,b,c,d)
    @name=a
    @line1=b
    @line2=c
    @line3=d
  end
  def name() @name end
  def line1() @line1 end
  def line2() @line2 end
  def line3() @line3 end
end

のようにメソッドを定義する必要があるのでしょうか?

A.

「データと計算(1)」の回のスライド「クラス」に書かれていますが， Ruby言語では，attr_accessorというキーワードで変数を指定すると，アクセスするためのメソッドが自動的に作られます．上の例では，

class Station
  attr_accessor :name, :line1, :line2, :line3
  def initialize(a,b,c,d)
    @name=a
    @line1=b
    @line2=c
    @line3=d
  end
end

と書くだけで良いはずです．

スライドの補足

オートマトンの動作を理解するには，シミュレータで実行してみるのが早道だろう．前期の「情報」で使ったオートマトンのシミュレータの使用法を書いたページオートマトンシミュレータの使い方にしたがって，スライドのプログラムを試してみると良い．

スライドに使われたプログラム

桁落ち誤差の例

def f(x)
  return Math.log(x);   # f(x)=ln(x)
end

x=1.0;
15.times { |i|
  h =0.1**i #h=0.1, 0.01, ..., 1e-15
  df=(f(x+h)-f(x))/h
  err=(df-1.0).abs;
  print "h=",h,"\t f'(",x,")=",df," err=",err,"\n"
}

情報落ち誤差の例

7.times{ |m| 
   n=10**m                    # n=1,10,100, ..., 1000000
   sum=0.0
   d=1.0/n
   n.times{ sum+=d }
   print "n=",n,"\t d=",d,"\t sum=",sum,"\n"
}

Runge-Kutta方の例(続き)

h=0.1    #時間変数ｔの差分
t=0       # 時間変数の初期値
u=[1,0,0,1] # 配列uで4変数u0,u1,u2,u3を定義（初期条件を代入）                  

100.times{  #計算のステップを１００回繰り返す
  u=rk(t,u,h,&func)  #Runge-Kutta法の計算を1ステップ分行う
  t+=h  #時間変数をhだけ増加させる
  print "t= ", t0, " u[0]= ",u[0]," u[1]= ",u[1]," u[2]= ",u[2]," u[3]= ",u[3]," \n"
}

func=lambda {|t,u|
  new_u=[0,0,0,0]
  r=(u[0]**2+u[1]**2)**1.5
  new_u[0]=u[2];
  new_u[1]=u[3];
  new_u[2]=-u[0]/r;
  new_u[3]=-u[1]/r;
  return new_u
}
def rk(t,u,h,&f)
  k1=muladd([[f.call(t,u),h]])
  k2=muladd([[f.call(t+h/2.0,muladd([[u,1.0],[k1,1.0/2.0]])),h]])
  k3=muladd([[f.call(t+h/2.0,muladd([[u,1],[k2,1.0/2.0]])),h]])
  k4=muladd([[f.call(t+h,muladd([[u,1.0],[k3,1.0]])),h]])
  new_u=muladd([[u,1],[k1,1.0/6.0],[k2,1.0/3.0],[k3,1.0/3.0],[k4,1.0/6.0]])
  return new_u
end

def muladd(pairs)
  r=Array.new(pairs.first.first)
  r.fill(0)
  pairs.each{|a,k| r.size.times{|i| r[i]+=k*a[i]}}
  return r
end

11/15 第6回 アルゴリズムと計算量