2011年12月18日

【F#】循環小数

ちょっと1/7みたいな有理数を0.{142857}みたいな形で、
繰り返し部分が分かる形で表示したいなぁとか
こういうのって無限小数なんだから、指定した桁だけ欲しいなぁ(正直あんまり欲しくないけど)とか思ったので、
ちょっと作ってみた。
有理数は、(分子, 分母)みたいなタプルで表現する。
実行例
> rdToString(1,7);;
val it : string = "0.{142857}"
> rdToString(1234,555);;
val it : string = "2.2{234}"
> rdToString(1,3);;
val it : string = "0.{3}"
> rdToString(1,8);;
val it : string = "0.125"
> rdToString(12,8);;
val it : string = "1.5"
> rdToString(-1,7);;
val it : string = "-0.{142857}"
> fractionToString (1,7) 32;;
val it : string = "0.1428571428571428571428571428571"
rdは、repeating decimal の意 rdrToSeq は、下請け関数で他に使い道もないから、fsi ファイルで隠した方がいいね。
逆に文字列から戻す例
> strTord "0.{3}";;
val it : int * int = (1, 3)
> strTord "-1.{3}";;
val it : int * int = (-4, 3)
> strTord "0.5{0}";;
val it : int * int = (1, 2)
> strTord "0.4{9}";;
val it : int * int = (1, 2)
> strTord "2.2{234}";;
val it : int * int = (1234, 555)
> strTord "0.{142857}";;
val it : int * int = (1, 7)
0.5などは、この記事で扱う循環小数の書式に合わないのでできないが、 0.5{0}は、有効。
0.4{9}も同じ意味。(無限小数の循環小数ならではですね)
こういう循環小数のような無限数列を与えられた時に、循環する部分を見つけ出す効率的なアルゴリズムってあるのかな?
正規表現で、(\d*)*みたいなものだからもしあったとしてもとても重い処理になりそうですね。
限られたシーケンスの中で循環する部分を見つけ出すのはともかく、
実際長さが不定(理論上無限)の数列から循環部分を見つけ出すのは不可能ですね。
この循環小数の場合は、同じ余りになる場合が循環の証拠になるので、可能ですが、そういう情報が無い場合無理ですよね?

いかにもな命令型プログラムw
(比較してみるとこの場合whileを使った方が簡潔に書けている)
以下ソース
let rdrToSeq(numerator, denominator) = seq {
    let n = abs numerator
    let d = abs denominator
    let q = n / d
    let r = n % d
    let signMark = if sign numerator * sign denominator = -1 then "-" else ""
    let update ((q, r),r)=
      if r = 0 then None
      else
        let nr = r * 10
        Some ((q, r), ((nr / d, nr % d), r))
    let conv (n1, n2) = (string n1, n2)
    yield (sprintf "%s%d." signMark (n / d), r)
    if r = 0 then
      yield ("0",  0)
    else
      yield! Seq.unfold update ((q, r), r) |> Seq.skip 1 |> Seq.map conv
  }

(*
let rdrToSeq(numerator, denominator) = seq {
    let n = ref (if numerator   < 0 then -numerator   else numerator)
    let d = ref (if denominator < 0 then -denominator else denominator)
    let r = ref (!n % !d)
    let sign = if (numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0) then "-" else ""
    let isEnd = ref true
    yield (sprintf "%s%d." sign (!n / !d), !r)
    if !r = 0 then
      yield ("0", !r)
      isEnd := false
    while !isEnd do
      n := !r * 10
      r := !n % !d
      yield (string (!n / !d), !r)
      if !r = 0 then isEnd := false
  }
*)
let rdToSeq(numerator, denominator) = rdrToSeq(numerator, denominator) |> Seq.map fst
let fractionToString (n, d) len = rdToSeq(n,d) |> Seq.take len |> String.concat ""

open System.Collections.Generic
let rdToString (n, d) =
  let dic = new Dictionary<string*int,int>()
  let list = new List<string>()
  let en = rdrToSeq(n,d).GetEnumerator()
  let isEnd = ref true
  let startPos = ref -1
  let i = ref 0
  while !isEnd do
    if en.MoveNext() then
      let (n,r) as v = en.Current
      if dic.ContainsKey(v) then
        startPos := dic.[v]
        isEnd := false
      else
        list.Add(n)
        dic.Add(v, !i)
    else
      isEnd := false
    incr i
  if !startPos >= 0 then
    list.Insert(!startPos, "{")
    list.Add("}")
  String.concat "" list

let gcd x y =
  let mutable wk = 1
  let mutable x = abs x
  let mutable y = abs y
  while y <> 0 do
    wk <- x % y
    x <- y
    y <- wk
  x

let strTord (s:string) =
  let dotPos = s.IndexOf('.')
  let startPos = s.IndexOf('{')
  let endPos = s.IndexOf('}')
  let nonRepertPart = s.Substring(0, startPos)
  let repeatPart = s.Substring(startPos + 1, endPos - startPos - 1)
  let denominator = ((pown 10 (repeatPart.Length))- 1)*(pown 10 (startPos - dotPos - 1))
  let numerator = int ((abs <| float nonRepertPart)*(float denominator)) + int repeatPart
  let gcm = gcd numerator denominator
  let minus = if s.[0] = '-' then -1 else 1
  (minus * numerator / gcm, denominator / gcm)

Posted by BLUEPIXY at 00:29│Comments(0)TrackBack(1)F# |

トラックバック一覧

  1. 1. F# 雑記 循環小数

    • [F#入門と妄想英単語]
    • 2011年12月19日 09:20
    •  BLUEPIXYさんのブログ(循環小数)がおもしろそうだったので、自分でもやってみました。 (5か月ぐらいコードを書いていないのでリハビリです。) 問題は分数を循環小数表示するというもので...

pre表示(Firefox)

コメントする

名前
URL
 
  絵文字