« 2012年2月 | トップページ | 2012年7月 »

2012年4月

2012年4月16日 (月)

素数日を求める

最近、自発的にコードを書くことがないなぁ…。

ということで今回も人様のブログのネタからです。何やら「素数日」を求めるらしい。
詳しい説明はこちらを見ていただくことにして…。

 

今回は「Date クラス」を使って実際の日付を出し、それを「yyyymmdd」の形の整数に変換した後に、その数が素数かどうかを調べました。

# -*- coding: utf-8 -*-
#
# 素数日を求める
#

require 'date'


class Integer
  def prime?
    return true  if self == 2 || self == 3
    return false if self.even? || self % 3 == 0 || self <= 1

    limit = (self ** 0.5).to_i
    i = 5
    add = 2
    while limit >= i
      return false if self % i == 0
      i = i + add
      add = 6 - add
    end
    return true
  end
end

d1 = Date.new(2012,  1,  1)     # 開始日
d2 = Date.new(2020, 12, 31)     # 終了日

arr = []
d1.upto(d2) do |d|
  n = d.year * 10000 + d.month * 100 + d.day
  arr.push(d) if n.prime?
end

puts arr.map{|d| d.to_s}
# puts arr.size

このコードは Ruby のみで書かれていますが、「intel Core i5, 2.4GHz」の環境で「2012年1月1日〜2020年12月31日」の期間に存在する素数日を、約0.03秒ですべて求めることができました。

 

 

追記 (2012/04/17) :Ruby1.9 の標準添付ライブラリである「Prime」と Range#select メソッ ドを使ったコードも書いてみました。
こっちの方がすっきりしてていいのかな?

# -*- coding: utf-8 -*-
#
# 素数日を求める
#

require 'date'
require 'prime'

d1 = Date.new(2012,  1,  1)     # 開始日
d2 = Date.new(2020, 12, 31)     # 終了日

arr = (d1 .. d2).select{|d| (d.year * 10000 + d.month * 100 + d.day).prime?}
puts arr.map{|d| d.to_s}
# puts arr.size

HTML generated by org-mode 6.33x in emacs 23

2012年4月 5日 (木)

オートマトン

ネットをウロウロしてたら、こちらのブログを発見しました。

「オートマトン」って、詳しくは知らないけど何だか面白そうです。 参考に挙げてあったPDFファイルを見ながら、自分なりにコードを書いてみました。

{-
   << DFA(決定性有限オートマトン) >>

   参考:
   http://d.hatena.ne.jp/cranebird/20120327/1332857936
   http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/07/automaton/k2.pdf
-}

type Q     = String
type Delta = ((Q, Char), Q)

-- isAccept 遷移表 受理状態の集合 状態 文字列 => 真偽
isAccept :: [Delta] -> [Q] -> Q -> String -> Bool
isAccept qs f st []        = elem st f
isAccept qs f st (c : cs)  = isAccept qs f st' cs
  where Just st' = lookup (st, c) qs -- 遷移表に抜けがないことが前提

-- makeDfa 遷移表 受理状態の集合 初期状態 => dfa
makeDfa :: [Delta] -> [Q] -> Q -> String -> String
makeDfa qs f q0 cs = if (isAccept qs f q0 cs)
                     then "Accept"
                     else "Not Accept"


{-
   例 1
   Σ = {a}, 奇数個の 'a' からなる文字列を受理する
-}
dfa1 :: String -> String
dfa1 = makeDfa qs f "Even"
  where
    qs = [(("Even", 'a'), "Odd"), (("Odd", 'a'), "Even")]
    f  = ["Odd"]

{-
   例 2
   Σ = {a, b}, 奇数個の 'a' からなる文字列を受理する
-}
dfa2 :: String -> String
dfa2 = makeDfa qs f "Even"
  where
    qs = [(("Even", 'a'), "Odd"), (("Even", 'b'), "Even"),
          (("Odd", 'a'), "Even"), (("Odd", 'b'), "Odd")]
    f  = ["Odd"]

{-
   例 3
   Σ = {a, b}, 奇数個の a と偶数個の b からなる文字列を受理する
   (0 は偶数とする)
-}
dfa3 :: String -> String
dfa3 = makeDfa qs f "00"
  where
    qs = [(("00", 'a'), "10"), (("00", 'b'), "01"),
          (("10", 'a'), "00"), (("10", 'b'), "11"),
          (("01", 'a'), "11"), (("01", 'b'), "00"),
          (("11", 'a'), "01"), (("11", 'b'), "10")]
    f  = ["10"]

{-
   問 4
   Σ = {a, b, c}, 奇数個の a と偶数個の b からなる文字列を受理する
   (0 は偶数とする)
-}
dfa4 :: String -> String
dfa4 = makeDfa qs f "00"
  where
    qs = [(("00", 'a'), "10"), (("00", 'b'), "01"), (("00", 'c'), "00"),
          (("10", 'a'), "00"), (("10", 'b'), "11"), (("10", 'c'), "10"),
          (("01", 'a'), "11"), (("01", 'b'), "00"), (("01", 'c'), "01"),
          (("11", 'a'), "01"), (("11", 'b'), "10"), (("11", 'c'), "11")]
    f  = ["10"]

 

とりあえず PDFファイル に書いてあった「例 1」〜「例 3」と「問 4」に対応する dfa を定義してみました。
ghci 上で確認してみたら、思ったように動いてくれているようです。

*Main> dfa1 "aaa"
"Accept"
*Main> dfa1 "aaaa"
"Not Accept"
*Main> dfa2 "ababa"
"Accept"
*Main> dfa2 "abababa"
"Not Accept"
*Main> dfa3 "ababa"
"Accept"
*Main> dfa3 "abababa"
"Not Accept"
*Main> dfa4 "abcacba"
"Accept"
*Main> dfa4 "abcacbacba"
"Not Accept"

 

でも PDFファイル の最後に書いてある「問 5」が未だにわからないんですよね。
御本家に聞いてみようかな?

 

 

HTML generated by org-mode 6.33x in emacs 23

« 2012年2月 | トップページ | 2012年7月 »

2016年7月
          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            
フォト

最近のトラックバック

無料ブログはココログ