数学

問題：

円周率3.141592653589793…の中で、最初に「"月日時分秒"と見なせる数字列」が出てくるところは、小数点以下何桁目？

ただし「"月日時分秒"と見なせる数字列」は、月二桁(01～12)、日二桁(01～31)、時二桁(00～23)、分二桁(00～59)、秒二桁 (00～59)の合計十桁の数字列のこととします。大の月小の月も正しく考えます。2月は29日まであるとしてよいです。以下いくつか例。

○: 0314152759 → 3月14日15時27分59秒

○: 0229152759 → 2月29日15時27分59秒（閏年と判断）

×: 1314152759 → 13月はない。

×: 0431152759 → 4月31日はない。

×: 0314152760 → 60秒はない。

3.141592653589793…のうち、"1415926535"の場所は小数点以下「1桁目」とします。

3.141592653589793…のうち、"2653589793"の場所は小数点以下「6桁目」とします。

日付であるかどうかの判断は力任せでも出来るのだが、それだと面白くないので、こんな方法を取ってみた。

このような図は「有限オートマトン」と呼ばれる。日付であるか判断する有限オートマトンが上の図となる。

この図は以下のように読む。日付かどうか判断したい文字列（この場合は10文字の文字列）を1文字ずつ順に通していき、その文字に応じて開始状態から図中の丸を移動していく。そして最後の状態（ここでは「R」）に到達出来れば日付であると判断し、到達する前に移動が不可能になったら日付でないと判断する。

例えば次の有限オートマトンに文字列"0230123456"を与えたとする。このとき、

最初は0なので、状態Aから状態Bへ移動
次は2なので、状態Bから状態Dへ移動
次は3であるが、状態Dにおいて文字3では移動が出来ない。よって"0230123456"は日付を表していない。

と判断する。

この有限オートマトンをRubyで表現してみたのが次のコードである。「TRANS_TABLE[現在の状態][今見ている文字]」とすることで、次の状態が得られるようにしてある。

# TRANS_TABLEは、日付のみを受理する有限オートマトン(FA)の遷移図

def rule_accept_all(dest) # どんな数字でもdestへ遷移する場合
  ret = {}
  (0..9).each{ |i| ret[i] = dest }
  ret
end

def rule_accept_nonzero(dest) # 0以外だったらdestへ遷移する場合
  ret = {}
  (1..9).each{ |i| ret[i] = dest }
  ret
end

def rule_accept_under5(dest) # 5以下だったらdestへ遷移する場合
  ret = {}
  (0..5).each{ |i| ret[i] = dest }
  ret
end

TRANS_TABLE = {
  :A => {0=>:B, 1=>:C},
  :B => {2=>:D, 1=>:E, 3=>:E, 5=>:E, 7=>:E, 8=>:E,
         4=>:F, 6=>:F, 9=>:F},
  :C => {0=>:E, 2=>:E, 1=>:F},
  :D => {0=>:G, 1=>:H, 2=>:H},
  :E => {0=>:G, 1=>:H, 2=>:H, 3=>:I},
  :F => {0=>:G, 1=>:H, 2=>:H, 3=>:J},
  :G => rule_accept_nonzero(:K),
  :H => rule_accept_all(:K),
  :I => {0=>:K, 1=>:K},
  :J => {0=>:K},
  :K => {0=>:L, 1=>:L, 2=>:M},
  :L => rule_accept_all(:N),
  :M => {0=>:N, 1=>:N, 2=>:N, 3=>:N},
  :N => rule_accept_under5(:O),
  :O => rule_accept_all(:P),
  :P => rule_accept_under5(:Q),
  :Q => rule_accept_all(:R)}
INIT_STATE = :A # FAの開始状態
END_STATE = :R  # FAの終了状態

問題の計算を行うためのコード全体はこちら。
gist: 79310 - GitHub

結果は

from digit 287: 0726024914

となり、小数点第287位に「7月26日 2時49分14秒」が現れるというものだった。

タグ：: Ruby

maraigue at 13:58│コメント(0)│トラックバック(0)

2008年08月30日

ねたミシュラン ★っしゃー！解けたー！！を解いてみた。

虫食い算みたいな問題だが、かなり数学的な考え方を要求されるな、と感じた問題だった。

私の回答・解説はこちら。「足して2008」の問題
※コメントがありましたら、この記事のコメント欄をご利用下さい。

※18:57追加
この記事を書いたことをTwitterにpostしたら、@kei_an氏が非常にスマートな方法を教えて下さったので、追記として加えておいた。

タグ：: 数学

maraigue at 18:22│コメント(0)│トラックバック(0)

livedoor プロフィール

Maraigue風。

数学

2009年08月04日

Re: はてな民に確率の問題を出してみよう

2009年07月22日

[解いてみた] 円に挟まれた領域の面積

2009年04月24日

[数学] モンモールの問題

2009年03月15日

[Ruby]円周率クイズに挑戦してみた

2008年08月30日

[数学] パズル「"足して2008"の問題」

H. Hiro