分数を小数に展開
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< |




にしお
#3365()
Rating0/0=0.00
a=3, b=8 → 0.375 a=3, b=14 → 0.2{142857}与えられる整数a, bは次の条件を満たすものと仮定して構いません。 1 ≦ a < b ≦ 2147483647。なお2147483647は2^31-1です。
このお題はtnkさんの投稿を元に作成しました。ご投稿ありがとうございます。
[ reply ]