第2章（後半） - ミームの死骸を待ちながら

Ruby翻訳計画〜。アルゴリズムを学ぶ上で自分的Goalは

数独解答プログラム
ライツアウト解答プログラム

を作ること。これらを自力で組み立てられたら力が付いたと判断。ライツアウトとは昔ハマったゲーム。Wikipedhiaに項目があってびびった
最近買ったので、これの必勝アルゴリズムを考えてみるのも楽しそう。その先は進化論マニアなので遺伝的アルゴリズムを学んでRubyに応用する。いつまでかかるやら

例2-9 1000までの素数を列挙する

インターンで似たのやった。てかRuby初日にしてこのレベルやらされたのかorz
まず2-9では、すべての数について、その数以下の数で割ってみて割れなかったものを素数としている。超効率悪いver。

def prime1(n)
  if n < 2
    print "2未満の数だめ"
  else
    counter = 0
    p_counter = 0
    for i in 2..n
      for j in 2..i
        counter += 1
        if i % j == 0; break; end
      end
      if i == j
        p_counter += 1
        puts i, "/"
      end
    end
    print "count = #{counter}\n"  
    print "number of pnum = #{p_counter}\n"
  end
end

prime1(1000)

168個、計算回数78190回。これを改良して行くようだ

例2-10 1000までの素数を列挙する（効率upその１

確定した素数を配列に格納し、その数だけで割る。

def prime2(n)
  if n < 2
    print "2未満の数だめ"
  elsif n == 2
    print "2のみ"
  else
    counter = 0
    p_counter = 1
    ary = [2]
    i = 3
    print "2/"
    while i <= n
      for j in ary
        counter += 1
        if i % j == 0
          break
        elsif j == ary.last
          p_counter += 1
          ary << i
          print i, "/"
        end
      end
      i += 2       #奇数だけ調べればよいので。
    end
  end
  print "\ncount = #{counter}\n"  
  print "number of pnum = #{p_counter}\n"
end

prime2(1000)

計算回数15288回。減ったね

例2-11 1000までの素数を列挙する（効率upその２

割る素数は、実は1000の√まででいい。何となれば、後半の素数は対象性により同じ計算をしているから。

def prime3(n)
  if n < 2
    print "2未満の数だめ"
  elsif n == 2
    print "2のみ"
  else
    counter = 0
    p_counter = 1
    ary = [2]
    i = 3
    print "2/"

    while i <= n
      flag = 0
      for j in ary
        counter += 1
        if j*j <= i
          counter += 1
          if (i%j).zero? #ちょっとRuby的に
            flag = 1
            break
          end
        end
      end  

      if flag.zero?
        p_counter += 1
        ary << i
        print i, "/"
      end

      i += 2
    end
  end
  print "\ncount = #{counter}\n"  
  print "number of pnum = #{p_counter}\n"
end

prime3(1000)

計算回数17423回…あれ？…増えたorz

例2-12、演習2-5 ある日付が年内で何日目か

うるう年と平年で別の日数配列使う方法、いいね。これならインターンでやった曜日を求めるプログラムも簡単にできそう

def dayofyear(y,m,d)
  
  #mdays[0]が平年、[1]がうるう年
  mdays = [[31,28,31,30,31,30,31,31,30,31,30,31],
    [31,29,31,30,31,30,31,31,30,31,30,31]]
  
  if (y%4).zero?
    use_mdays = mdays[1]
    if (y%100).zero?
      use_mdays = mdays[0]
      if (y%400).zero?
        use_mdays = mdays[1]
      end
    end
  else
    use_mdays = mdays[0]
  end
  
  days = d
  for i in 0...(m-1)  #..じゃなく...にするとラスト含まない
    days += use_mdays[i]
  end
  print y,"/", m, "/", d, "は\n"
  print y, "年の", days, "日目\n"

  ######################################
  #演習2-5「iとdaysを使わずおなじものを作れ。whileを使うこと」
  #→mとdを破壊的に処理してやればいい
  #while m-1 > 0
  #  d += use_mdays[m-2]
  #  m -= 1
  #end
  #print y, "年の", d, "日目\n"
  ######################################
  
end

dayofyear(2000,3,1)
dayofyear(2004,3,1)
dayofyear(2100,3,1)
dayofyear(2006,9,26)

if,if,ifのあたり&&や||使ってコンパクトにしたい…

例2-13、演習2-6 構造体の配列

Rubyから入った軟弱似非プログラマが思うに、Rubyには変数の型がないんで配列内にStringでもFixnumでも何でも入る。故に、C言語などで言う「構造体」という概念は無意味…なのかな。よくわからん。ArrayとHashで表現できるはず。

#! ruby -Ks

nameary = ["AKANE kouichi", "TOKUTOMI shyuji", "NISHIDA taro",
           "TSUJINO jiro", "MATSUO kenji", "OHYAMA kazuhiro",
           "KITAYAMA takuya", "TANAKA rina"]
heightary = [170, 173, 170, 175, 167, 168, 179, 158]
eyeary = [2.0, 1.5, 0.5, 0.4, 0.6, 0.2, 0.6, 0.9]

n = nameary.size - 1
#データが追加されても対応

h = Hash["name", nameary, "height", heightary, "eye", eyeary]

puts "身体検査一覧表"
puts "氏名　　　　　    身長 視力"
puts "---------------------------"
for i in 0..n
printf("%-16s %4d %5.1f", h["name"][i], h["height"][i], h["eye"][i])
print "\n"
end
print "\n\n"

sum = 0
for i in 0..n
  sum += h["height"][i]
end

print "平均身長 "
printf("%.1f", sum.to_f / (n + 1))
print " cm\n\n"

print "視力の分布\n"

for i in 1..21
num = 0
  #各領域の人数をnumに格納

num = h["eye"].find_all{|x| (x >= (i.to_f/10) - 0.1) && x < (i.to_f/10) }.size
printf("%.1f%s%3d%s", (i.to_f/10) - 0.1, "〜：", num, "人\n")

#printf("%.1f%s%-10s%s", (i.to_f/10) - 0.1, "〜：", ("*" * num), "\n")
#↑演習2-6．人数分だけ「*」を表示して視覚化
end

Hashにする必要はあまりなかった
条件に合うものをfind_allで集め、配列にして返す。最初collect使おうとして苦しんでた。collectは各要素に処理をするだけなので、trueとfalseの配列が出てしまう。
sizeで数えるんじゃなく、条件に合う要素数返すメソッドあれば幸せだが…

演習2-7 ある日付からn日後/前の日付を求める

#引数は4つ。（第一）年/（第二）月/（第三）日 から数えて（第四）日後/前を出力

@h = Hash["y", ARGV[0].to_i, "m", ARGV[1].to_i, "d", ARGV[2].to_i]
@mdays = [[31,28,31,30,31,30,31,31,30,31,30,31],
  [31,29,31,30,31,30,31,31,30,31,30,31]]

#うるう年メソッド独立さす

def leap_year(y)
  if (y%4).zero?
    @use_mdays = @mdays[1]
    if (y%100).zero?
      @use_mdays = @mdays[0]
      if (y%400).zero?
        @use_mdays = @mdays[1]
      end
    end
  else
    @use_mdays = @mdays[0]
  end
end

def after(n)
  y = @h["y"]
  m = @h["m"]
  d = @h["d"] + n
# d = @h["d"] - n        # before関数の場合、日付を減らす
   
  leap_year(y)
  
  #ここでdが月の日数以下になるよう回して、引いていく
  #さらに内部でmが13以上になったらy増やしてうるう年の判定をもう一度
  
  while d > @use_mdays[m-1] 
    d -= @use_mdays[m-1]
    m += 1
    if m > 12
      y += 1
      m = 1
      leap_year(y)
    end
  end
  
=begin  
    while d < 1     #n日前の日付を返すbefore関数の場合ここを封印解除
      d += @use_mdays[m-1]
      m -= 1
      if m < 1
        y -= 1
        m = 12
        leap_year(y)
      end
    end
=end
  printf("%4d/%02d/%02d", @h["y"], @h["m"], @h["d"])
  print " の", ARGV[3], "日後は\n"
#  print " の", ARGV[3], "日前は\n"
  printf("%4d/%02d/%02d", y, m, d)
  
end
n = ARGV[3].to_i
after(n)

というか果てしなくHashにした意味はなかった

[◆課題◆]素数プログラム改良

平方根の方法でなんで増えたのか
◆済◆エラトステネスのふるいを使った方法

「エラトステネスのふるい」ver

def prime4(n)
  primeary = [2]
  searched = (3..n).to_a.reject!{|i| i % 2 == 0}
  counter = 0
  
  while primeary.last**2 < searched.last
    counter += 2 #二乗の判定と倍数のreject
    f = searched.shift
    primeary << f
    searched.reject!{|i| i % f == 0}
  end
  counter += 1  #判定して中に入らなかった
  p (primeary + searched)
  p counter
end

prime4(1000)

計算わずか23回！これはすごい。