challenge 分数を小数に展開

整数a, bを受け取り,分数a/bを小数に展開した文字列を返す関数/メソッドを作成してください。結果が循環小数になる場合は,循環部を{}でくくってください。例:
a=3, b=8 → 0.375
a=3, b=14 → 0.2{142857}

与えられる整数a, bは次の条件を満たすものと仮定して構いません。 1 ≦ a < b ≦ 2147483647。なお2147483647は2^31-1です。

このお題はtnkさんの投稿を元に作成しました。ご投稿ありがとうございます。

Posted feedbacks - Nested

Flatten Hidden
君はやれば出来るんだから、ちゃんと宿題やってきなさい!ってよく言われたなぁ...(意味不明)
 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
fun! Frac(a, b)
  let a = a:a
  let b = a:b
  let i = 0
  let col = range(1, b*b)
  let col[0] = 0
  let col[b] = 0
  let s = (a / b) . "."
  while 1
    let i = i + 1
    let a = a % b
    let col[b+i] = a
    let j = col[a]
    if j >= 0 && j < i && col[b+j] == a
      break
    endif
    let col[a] = i
    let a = a * 10
    let s .= (a / b)
  endwhile
  if a == 0
    return s
  endif
  if col[a] == (i-1)
    let i = 1
  endif
  let s = strpart(s, 0, col[a]+1) . "{" . strpart(s, col[a]+1, i) . "}"
  return s
endfun
素直に書いたらこんなのになりました・・・
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def modulo(numerator, denominator):
    while numerator:
        div, numerator = numerator // denominator, numerator % denominator
        yield div, numerator
        numerator *= 10

def recurring_decimal(numerator, denominator):
    result = []
    reminds = {}
    for u, r in enumerate(modulo(numerator, denominator)):
        result.append(str(r[0]))
        if r[1] in reminds:
            # 循環有り
            idx = reminds[r[1]]+1
            return '%s.%s{%s}' % (result[0], ''.join(result[1:idx]), ''.join(result[idx:]))
        reminds[r[1]] = u
    # 循環無し
    if len(result)==1:
        return result[0]
    else:
        return '%s.%s' % (result[0], ''.join(result[1:]))
基本的な流れは同じですが、いらないと思うところを削るとこうなりました。
・問題条件でa < bなので整数部は0に決まっている
・単にwhileでループするだけなのでジェネレータ使うまでもない?
・組み込み関数にdivmodがある
・文字列化を後でやればremindsはいらない
という感じでしょうか。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def fraction_to_decimal(numerator, denominator):
    result = []
    num = numerator * 10
    den = denominator
    while num:
        div, num = divmod(num, den)
        if div in result:
            # repeating
            idx = result.index(div)
            return "0.%s{%s}" % (
                "".join(str(x) for x in result[:idx]),
                "".join(str(x) for x in result[idx:]))

        result.append(div)
        num *= 10

    return "0." + "".join(str(x) for x in result)
あー、denominatorが使われるのは1回だけだから
名前を付け替える必要はなかったか…。
divmod なんてあるんすねぇ。 divじゃなくて、numの2回目で跳ねないと 1 / 191とかで間違えますぜ
>>> fraction_to_decimal(3,14) '0.{214}' となってしまうので、remindsは必要だと思います。
ああっ、確かにそうですね。
うっかりしてました。
どこかおかしいですよ。

Python 2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> def fraction_to_decimal(numerator, denominator):
...     result = []
...     num = numerator * 10
...     den = denominator
...     while num:
...         div, num = divmod(num, den)
...         if div in result:
...             # repeating
...             idx = result.index(div)
...             return "0.%s{%s}" % (
...                 "".join(str(x) for x in result[:idx]),
...                 "".join(str(x) for x in result[idx:]))
...         result.append(div)
...         num *= 10
...     return "0." + "".join(str(x) for x in result)
...
>>> fraction_to_decimal(3,8)
'0.375'
>>> fraction_to_decimal(3,14)
'0.{214}'
schemeですけど、gaucheでしか動かないと思います。エレガントではないので申し訳ないです。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
(use text.tree)

(define (div a b)
  (tree->string `("0." ,(div2 (* a 10) b (make-hash-table 'eqv?)))))

(define (div2 a b h)
  (cond ((hash-table-get h a #f)
         => (lambda (x)
              (set-car! x `("{" ,(car x)))
              `("}")))
        (else
          (call-with-values
            (cut quotient&remainder a b)
            (lambda (q r)
              (if (zero? r) `(,q)
                  (let1 p (cons q #f)
                    (hash-table-put! h a p)
                    (set-cdr! p (div2 (* r 10) b h))
                    p)))))))

(print (div 3 8))
(print (div 3 14))
2147483645 / 2147483647 でOut of Memoryが出ちゃいました。 スタックの事もあるし、考え直します。
副作用無し版。gaucheです。 検索が遅いので、桁が多いと遅くなります。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
(use text.tree)
(use srfi-1)
(use srfi-11)
(use gauche.sequence)

(define (div3 a b)
  (tree->string (cons "0."
    (let loop ((a (* 10 a)) (b b) (r ()) (l ()))
      (cond ((find-index (pa$ = a) l) =>
             (lambda (m)
               (reverse
                 (call-with-values (cut split-at r (+ m 1))
                                   (cut append '("}") <> '("{") <>)))))
            ((< a b) (loop (* a 10) b (cons 0 r) (cons a l)))
            (else (let-values (((quo rem) (quotient&remainder a b)))
                    (if (zero? rem)
                      (reverse (cons quo r))
                      (loop (* rem 10) b (cons quo r) (cons a l))))))))))
未検証
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
require 'rational'

def func(a, b)
  c = a / b
  dst = ["#{c}."]
  d = [0, Rational(a, b) - c]
  h = []
  1.upto(10) {|i|
    d = d[1].divmod(Rational(1, 10 ** i))
    k = [d[0], d[1].numerator, d[1].denominator / 10 ** i]
    if k == [0, 0, 0]
      return dst.to_s
    end
    if n = h.index(k)
      return (dst[0..n] + ["{"] + dst[n + 1..dst.size] + ["}"]).to_s
    end
    h << k
    dst << d[0]
  }
  dst.to_s + "..."
end
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def flac_to_decimal(a,b)
  r = '0.'
  m = []
  while a != 0
    m << a
    a *= 10
    r += "#{a/b}"
    if i = m.index(a%=b)
      r[i+2,0] = '{'
      r += '}'
      break
    end
  end
  r
end
ほぼ同じなんですが、Hashを使ったほうが効率良いですよね。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def frac_to_decimal(a,b)
  r = '0.'
  m = {}
  i = 1
  while a > 0
    m[a] = (i+=1)
    a *= 10
    r += (a/b).to_s
    if m.key?(a%=b)
      r.insert(m[a], '{') << '}'
      break
    end
  end
  r
end

ストレートフォワードかつきれいなコードなので、Perlにも移植させていただきました。何をやっているかを解りやすくするため、変数名をもう少しdescriptiveにし、10より大きな整数の場合にもきちんと動くようにしてあります。

Dan the Math Monger

 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
#!/usr/local/bin/perl
use strict;
use warnings;

# cf. http://ja.doukaku.org/comment/202/

sub rat2dec {
    my ( $num, $den ) = @_;
    my $result = int( $num / $den );
    my $offset = length $result;
    $result .= '.';
    $num %= $den;
    my %repeat;
    my $i = 1;
    while ( $num > 0 ) {
        $repeat{$num} = $i++;
        $num *= 10;
        $result .= int( $num / $den );
        next unless $repeat{ $num %= $den };
        substr( $result, $repeat{$num} + $offset, 0, '{' );
        $result .= '}';
        last;
    }
    $result;
}

print rat2dec(@ARGV), "\n";
んー、いまいち。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
<?php
function decimal($numerator, $denominator){
	$remainders = array();
	$fraction = array();
	$remainder = $numerator % $denominator;
	while(!(in_array($remainder, $remainders) || $remainder == 0)){
		$numerator = $remainder * 10;
		$quotient = floor($numerator / $denominator);
		$remainders[] = $remainder;
		$fraction[]= $quotient;
		$remainder = $numerator % $denominator;
	}
	if(!(floor($remainder * 10 / $denominator) == 0 && $remainder == 0)){
		$loop_start = array_search($remainder, $remainders);
		$fraction[$loop_start] = '{'.$fraction[$loop_start];
		$fraction[] = '}';
	}
	return '0.'.join('',$fraction);
}
echo(decimal(3, 14));
?>
無駄を省いてみた。
$remainders の使い方を変えてみた。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<?php
function decimal($numerator, $denominator)
{
	$remainders = array();
	$fraction = array();
	$remainder = $numerator;
	for(;;)
	{	$remainder *= 10;
		$fraction[] = floor($remainder / $denominator);
		$remainder %= $denominator;
		if(!$remainder)
			break;
		if(isset($remainders[$remainder]))
		{	$loop_start = $remainders[$remainder];
			$fraction[$loop_start] = '{'.$fraction[$loop_start];
			$fraction[] = '}';
			break;
		}
		$remainders[$remainder] = count($fraction);
	}
	return '0.'.join('',$fraction);
}
echo decimal(3, 14),"\n";
?>
う、早速バグ発見。修正
 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
<?php
function decimal($numerator, $denominator)
{
	$remainders = array();
	$fraction = array();
	$remainder = $numerator;
	for(;;)
	{	$remainders[$remainder] = count($fraction);
		$remainder *= 10;
		$fraction[] = floor($remainder / $denominator);
		$remainder %= $denominator;
		if(!$remainder)
			break;
		if(isset($remainders[$remainder]))
		{	$loop_start = $remainders[$remainder];
			$fraction[$loop_start] = '{'.$fraction[$loop_start];
			$fraction[] = '}';
			break;
		}
	}
	return '0.'.join('',$fraction);
}
echo decimal(3, 14),"\n";
echo decimal(10, 17),"\n";
?>
CL-USER> (rational->decimal 3/14)
"0.2{142857}"
CL-USER> (rational->decimal 1/4)
"0.25"
CL-USER> (rational->decimal 17/14)
"1.2{142857}"
 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
(defun %rational->decimal-calc (rat)
  (let ((a (numerator rat))
        (b (denominator rat))
        ret mods)
    (loop
       do
         (setf a (* 10 a))
         (push (floor (/ a b)) ret)
         (setf a (mod a b))
       until
         (or (zerop a) (member a mods))
       do
         (push a mods)
       finally
         (setf ret (nreverse ret)))
    (if (zerop a)
        ret
        (nconc (insert ret (position (floor (/ (* 10 a) b)) ret :from-end t) "{") '("}")))))

(defun insert (list n newelt)
  `(,@(butlast list (- (length list) n)) ,newelt ,@(nthcdr n list)))

(defun rational->decimal (rat)
  (multiple-value-bind (int frac) (truncate rat)
    (format nil "~a.~{~a~}" int (%rational->decimal-calc frac))))
Java1.6(1.5+?)です。
1<=a<b<2^32-1って条件は無視しちゃいました、a=int & b=int & b!=0 なら…
…故に?長くなっててすみません(汗
 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 
 * @param dividend (a) 被除数
 * @param divisor (b) 除数
 * @return 商
 */
public static String getResult(final int dividend, final int divisor) {
    return generateResultString(getDigits(dividend, divisor));
}

private static List<Integer> getDigits(final int dividend, final int divisor) {

    final List<Integer> dividends = new LinkedList<Integer>();
    final List<Integer> digits = new LinkedList<Integer>();

    getDigits(dividend, divisor, digits, dividends);
    return digits;
}

private static void getDigits(final int dividend, final int divisor,
        final List<Integer> digits, final List<Integer> dividends) {

    final int containedIndex = dividends.indexOf(Integer.valueOf(dividend));
    if (containedIndex >= 0) {
        digits.add(Integer.valueOf(containedIndex - digits.size()));
        return;
    }

    digits.add(Integer.valueOf(dividend / divisor));

    final int remainder = dividend % divisor;
    if (remainder != 0) {
        dividends.add(Integer.valueOf(dividend));
        getDigits(remainder * 10, divisor, digits, dividends);

    }
}

private static String generateResultString(final List<Integer> digits) {
    
    final StringBuilder sb = new StringBuilder();
    assert digits.size() > 0;
    sb.append(digits.get(0));
    
    if (digits.size() > 1) {
        sb.append(".");
        for (final Iterator<Integer> itr = digits.listIterator(1); itr.hasNext();) {
            final int digit = itr.next().intValue();
            if (digit >= 0) {
                sb.append(digit);
            } else {
                sb.insert(sb.length() + digit, "{");
                sb.append("}");
            }
        }
    }
    return sb.toString();
}
バグ混在…a=10,b=17を与えたときに
"0.{14084507042253521126760563380281690}"となるべきところが
"0{.1408450704225352112676056338028169}"に…

整数部から循環?してる場合に再現…といっても他の例がないので何とも言えないけど、とりあえず応急措置を…
 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
private static String generateResultString(final List<Integer> digits) {

    final StringBuilder sb = new StringBuilder();
    assert digits.size() > 0;
    sb.append(digits.get(0));

    if (digits.size() > 1) {
        sb.append('.');
        for (final Iterator<Integer> itr = digits.listIterator(1); itr.hasNext();) {
            final int digit = itr.next().intValue();
            if (digit >= 0) {
                sb.append(digit);
            } else {
                int insertPoint = sb.length() + digit;
                if ('.' == sb.charAt(insertPoint)) {
                    insertPoint += 1;
                    sb.append(0);
                }
                sb.insert(insertPoint, '{');
                sb.append('}');
            }
        }
    }
    return sb.toString();
}
#  pretty_fmt (decimal_of_frac 3 8);;
- : string = "0.375"
#  pretty_fmt (decimal_of_frac 3 14);;
- : string = "0.2{142857}"
# pretty_fmt (decimal_of_frac 355 113);;
- : string =
"3.{1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168}"
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
let find_index_of e l =
  try
    let (i, _) = List.findi (fun i' e' -> e = e') l in Some i
  with Not_found -> None

let decimal_of_frac a b = 
  let rec decimal_of_frac' a quots rems =
    let quot = a / b and rem = a mod b in
    match find_index_of (a mod b) rems with
    | Some i -> (quot::quots, i)
    | None   -> decimal_of_frac' (rem * 10) (quot::quots) (rem::rems)
  in
  decimal_of_frac' a [] []

let pretty_fmt (numbers, i) =
  let loop = List.rev (List.take (i + 1) numbers) in
  let d::ds = List.rev (List.drop (i + 1) numbers) in
  let string_of_nums ns = String.concat "" (List.map string_of_int ns) in
  (string_of_int d) ^ "." ^ (string_of_nums ds) ^ 
    if loop = [0] then "" else "{" ^ (string_of_nums loop) ^ "}"
コメント崩れちゃった。失礼しました。 あと List.findi を使うのに ExtLib を読んで open ExtList しないといけないのを書き忘れました。
コメント崩れを修正しました。
こんなところでしょうか
 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
32
33
34
35
36
37
import java.util.Map;
import java.util.HashMap;

public class Fraction {
	
	public static String toRepeatingDecimal(int numerator, int denominator) {
		Map<Integer, Integer> remainders = new HashMap<Integer, Integer>();
		long d, q, r;
		int i = 0;
		StringBuffer sb = new StringBuffer();
		d = denominator;
		r = numerator;
		q = r / d;
		r = r % d;
		remainders.put((int)r, i++);
		r *= 10;
		sb.append(q);
		if (r > 0) {
			sb.append('.');
			do {
				q = r / d;
				r = r % d;
				sb.append(q);
				Integer index = remainders.get((int)r);
				if (index != null) {
					sb.insert(sb.length() - i + index, '{');
					sb.append('}');
					break;
				}
				remainders.put((int)r, i++);
				r *= 10;
			} while (r > 0);
		}
		return sb.toString();
	}
	
}
出題者が回答していいのかな・・・。
Java 1.5以降です。Auto Boxingって楽だなあ。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public static String getDecimal(long a, long b) {
    java.util.Vector<Long> nums = new java.util.Vector<Long>();
    StringBuffer res = new StringBuffer("0.");
    while (true) {
        nums.add(a);
        a *= 10;
        res.append(a/b);
        a %= b;
        if (a == 0) {
            return res.toString();
        }
        if (nums.contains(a)) {
            int off = nums.indexOf(a) + 2;
            return res.substring(0,off) + "{" + res.substring(off) + "}";
        }
    }
}
Cでがんばってみたあんなに短くなるほかの言語がうらやましい。
もっと効率のいい書き方ないかなぁ。
循環小数の判定がむずかしい。。。
  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
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <stdio.h>
#include <string.h>
#include <assert.h>

int cal(char *ans, size_t<