分数を小数に展開 DouKaku?

整数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さんの投稿を元に作成しました。ご投稿ありがとうございます。

君はやれば出来るんだから、ちゃんと宿題やってきなさい！ってよく言われたなぁ...(意味不明)

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

素直に書いたらこんなのになりました･･･

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:]))

schemeですけど、gaucheでしか動かないと思います。エレガントではないので申し訳ないです。

(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))

基本的な流れは同じですが、いらないと思うところを削るとこうなりました。
・問題条件でa < bなので整数部は0に決まっている
・単にwhileでループするだけなのでジェネレータ使うまでもない？
・組み込み関数にdivmodがある
・文字列化を後でやればremindsはいらない
という感じでしょうか。

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回だけだから
名前を付け替える必要はなかったか…。

未検証

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

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

divmod なんてあるんすねぇ。 divじゃなくて、numの2回目で跳ねないと 1 / 191とかで間違えますぜ

>>> fraction_to_decimal(3,14) '0.{214}' となってしまうので、remindsは必要だと思います。

ああっ、確かにそうですね。
うっかりしてました。

んー、いまいち。

<?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));
?>

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}"

(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 なら…
…故に?長くなっててすみません(汗

/**
 * 
 * @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();
}

#  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}"

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 しないといけないのを書き忘れました。

バグ混在…a=10,b=17を与えたときに
"0.{14084507042253521126760563380281690}"となるべきところが
"0{.1408450704225352112676056338028169}"に…

整数部から循環?してる場合に再現…といっても他の例がないので何とも言えないけど、とりあえず応急措置を…

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();
}

どこかおかしいですよ。

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}'

ほぼ同じなんですが、Hashを使ったほうが効率良いですよね。

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

こんなところでしょうか

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();
	}
	
}

無駄を省いてみた。
$remainders の使い方を変えてみた。

<?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";
?>

う、早速バグ発見。修正

<?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";
?>

出題者が回答していいのかな・・・。
Java 1.5以降です。Auto Boxingって楽だなあ。

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でがんばってみたあんなに短くなるほかの言語がうらやましい。
もっと効率のいい書き方ないかなぁ。
循環小数の判定がむずかしい。。。

#include <stdio.h>
#include <string.h>
#include <assert.h>

int cal(char *ans, size_t bufsize, int a, int b)
{
    const char * const head   = ans;
    char       *jyunkan_start = NULL;  // 循環の始点
    const char *match_start   = NULL; // 
    size_t      match_count   = 0;

    memset(ans, '\0', bufsize);

    a = (a % b) * 10; 
    for( size_t n=1; n<bufsize; n ++, ans ++ )
    {
        // 計算
        *ans = '0' + a / b;
        a = (a % b) * 10;
        if( a == 0 ) break;

        /**********************/
        /* 循環小数のチェック */
        /**********************/
        if( match_start == NULL )
        {
            if( jyunkan_start == NULL )
            {
                jyunkan_start = ans;
                continue;
            }
            if( *jyunkan_start == *ans )
            {
                // 循環の開始位置かもしれない
                match_start = ans;
                match_count ++;
            }
        }
        else
        {
            // 循環の可能性あり
            if( *(jyunkan_start+match_count) == *ans )
            {
                if( (size_t)(match_start-jyunkan_start)==match_count)
                {
                    // ロジック上開始位置がずれるので巻き戻し
                    while( head != jyunkan_start )
                    {
                        if( *(jyunkan_start-1) == *(ans-1))
                        {
                            jyunkan_start --;
                            ans --;
                        }
                        else 
                        {
                            break;
                        }
                    }
                    // 循環部分を {}
                    memmove(jyunkan_start+1, jyunkan_start, match_count);
                    jyunkan_start[0] = '{';
                    jyunkan_start[match_count+1] = '}';
                    jyunkan_start[match_count+2] = '\0';
                    break;
                }
                match_count ++;
            }
            else
            {
                // はずれ
                jyunkan_start ++;
                match_start = NULL;
                match_count = 0;
            }
        }
    }

    return 0;
}

int main(int argc, char *argv[])
{
    char   ans[64]; // 循環する小数部の倍以上必要
    struct {
        int a, b;
        char ans[64];
    } 
    test[] = 
    {
        {  1,  2, "5" },
        {  1,  3, "{3}" },
        {  1,  7, "{142857}" },
        {  3, 14, "2{142857}" },
        { 50, 51, "{9803921568627450}" },
        { 13, 191,"068062827225130890052356020942408376963350785340314136125654450" }
    };

    for( size_t n=0; n<sizeof(test)/sizeof(*test); n++)
    {
        cal(ans, sizeof(ans), test[n].a, test[n].b); 
        printf("ans=0.%s\n", ans);
        assert( strcmp(ans, test[n].ans) == 0 );
    }
    return 0;
}

2147483645 / 2147483647 でOut of Memoryが出ちゃいました。スタックの事もあるし、考え直します。

とりあえず書いてみた。

#include <stdio.h>
#include <string.h>

char* flac2decimals(int a,int b,char* ans){
	char point[256];	//小数点以下
	int num[256];		//循環チェック
	int pos;
	int i;
	
	sprintf(ans,"%d",a/b);
	
	if(a%=b){
		strcat(ans,".");
		pos=0;
		do{
			a*=10;
			num[pos]=a;
			//循環チェック
			for(i=0;i<pos;i++){
				//循環していたら
				if(num[i]==a){
					//循環部以前の処理
					if(i) strncat(ans,point,i);
					//循環部の処理
					strcat(ans,"{");
					strcat(ans,point+i);
					strcat(ans,"}");
					return ans;
				}
			}
			point[pos]=a/b+'0';
			point[pos+1]='\0';
			pos++;
		}while(a%=b);
		strcat(ans,point);
	}
	return a

DouKaku?

分数を小数に展開

Posted feedbacks - Flatten