繰り返し数字を計算する方法は？

StackOverflow https://stackoverflow.com/questions/249372

質問

2つの整数 a と b が与えられた場合、 a / b の繰り返し小数をどのように計算しますか？これはどの言語でも可能です。表現しやすいものは何でも。

役に立ちましたか？

解決

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

他のヒント

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

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

（この引数BTWは、繰り返し部分の長さが最大b-1桁であるという数学的な証明でもあります。たとえば、1/7 = 0。（142857）は、6桁の繰り返し部分と1/17 = 0.（0588235294117647）には16桁の繰り返し部分があります。実際の長さは常に divides 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)

辞書の代わりにサイズが b の配列（Pythonのリスト）を使用することもできます。辞書のほうがわずかに高速になります（漸近的ではなく、定数係数で）。

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

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

私は専門家ではありません。このソリューションは効率的ではないかもしれませんが、少なくとも簡単に実行できます。

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

コメントは受け入れられます

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top