8

2 つの整数aとが与えられbた場合、 の繰り返し小数を計算するにはどうすればよいでしょうa / bか? これはどの言語でもかまいません。あなたがそれを表現しやすいものなら何でも。

4

4 に答える 4

10

a / bMark Ransom が言ったように、学校で学んだ長除算アルゴリズムを使用しての 10 進数表現を計算できます。連続する各桁を計算するには、現在の被除数 (分子または剰余) を で割り、b剰余に 10 を掛けて次の被除数を見つけます (「0 を下げる」)。余りが前の余りと同じ場合は、それ以降の桁も同じように繰り返されることを意味するので、この事実に注意して停止できます。

ここで最適化の可能性に注意してください: b で割ったときに得られる剰余は 0 から b-1 の範囲にあるため、明確な非ゼロの剰余のみを保持するため、以前の剰余のリストを検索して確認する必要はありません。何かが繰り返される場合。したがって、除算ステップごとに一定の時間がかかるようにアルゴリズムを作成でき、O(b)スペースは十分です。各剰余が最初に発生した桁位置を追跡するだけです。

(ところで、この引数は、反復部分が最大で b-1 桁の長さであるという数学的な証明でもあります。たとえば、1/7=0.(142857) には 6 桁の反復部分があり、1/17 = 0 です。 (0588235294117647) には 16 桁の繰り返し部分があります。実際には、長さは常に b-1 で割ります。)

これを行うための Python コードを次に示します。これはO(b)時間内に実行されます。

def divide(a, b):
  '''Returns the decimal representation of the fraction a / b in three parts:
  integer part, non-recurring fractional part, and recurring part.'''
  assert b > 0
  integer = a // b
  remainder = a % b
  seen = {remainder: 0}  # Holds position where each remainder was first seen.
  digits = []
  while(True):  # Loop executed at most b times (as remainders must be distinct)
    remainder *= 10
    digits.append(remainder // b)
    remainder = remainder % b
    if remainder in seen:  # Digits have begun to recur.
      where = seen[remainder]
      return (integer, digits[:where], digits[where:])
    else:
      seen[remainder] = len(digits)

# Some examples.
for a, b in [(5,4), (1,6), (17,7), (22,11), (100,17)]:
  (i, f, r) = divide(a, b)
  print "%d/%d = %d.%s(%s)" % (a, b, i, ''.join(map(str, f)),''.join(map(str,r)))
# Output:
# 5/4 = 1.25(0)
# 1/6 = 0.1(6)
# 17/7 = 2.(428571)
# 22/11 = 2.(0)
# 100/17 = 5.(8823529411764705)

ディクショナリの代わりにサイズの配列 (Python のリスト) を使用することもできますb。これは、わずかに高速になります (漸近的な点ではなく、定数係数の点で)。

于 2008-10-30T20:17:10.913 に答える
7

あなたは長い分割でそれを行うことができます。一度に 1 桁ずつ計算し、減算して余りを取得します。これに 10 を掛けて、次のステップの分子を取得します。この新しい分子が前の分子の 1 つと一致すると、その時点から繰り返すことがわかります。前の分子のスタックを保持し、各反復でそれを検索するだけです。

于 2008-10-30T05:54:42.370 に答える
1

これはあなたが探しているものだと思います..

public static String divide(int a,int b,boolean decimalDone,boolean isMultiplied,String result){
           if(a<b){
                a=a*10;

                if(!decimalDone ) {result+=".";decimalDone=true;}
                else if(isMultiplied) result+="0";
                isMultiplied=true;
                divide(a,b,decimalDone,isMultiplied,result);

           }
           else{
               result+=a/b;
               a=a%b;
               isMultiplied=false;
               divide(a,b,decimalDone,isMultiplied,result);
           }

           return result;
    }
于 2013-03-05T18:00:21.067 に答える
0

私は専門家ではありません。この解決策は効率的ではないかもしれませんが、少なくとも簡単に実行できます。

#you want to get a/b
from fractions import Fraction:
print float(Fraction(a,b))

コメント大歓迎です

于 2015-06-23T12:11:48.433 に答える