반복 숫자를 계산하는 방법은 무엇입니까?

Question

두 개의 정수가 주어졌습니다 a 그리고 b, 반복되는 소수점을 계산하는 방법 a / b? 이것은 모든 언어로 될 수 있습니다. 당신이 그것을 표현하는 것이 가장 쉬운 것은 무엇이든.

Answer 1

당신은 긴 분열로 그것을 할 수 있습니다. 한 번에 단일 숫자를 계산하고 나머지를 얻으려면 빼기 위해 다음 단계의 분자를 얻기 위해 10을 곱하십시오. 이 새로운 분자가 이전 분자 중 하나와 일치 할 때, 당신은 그 시점에서 반복 할 것임을 알고 있습니다. 이전 배설기의 스택을 유지하고 각 반복마다 검색하면됩니다.

Answer 2

소수점 표현을 계산할 수 있습니다 a / b Mark Ransom이 말한 것처럼 학교에서 배운 장거리 알고리즘을 사용합니다. 각 연속 숫자를 계산하려면 현재 배당 (분자 또는 나머지)을 b, 나머지에는 10을 곱한 다음 배당금을 찾으십시오 ( "0"). 나머지가 이전의 나머지와 동일하면, 그 당시의 숫자도 반복 될 것이므로이 사실에 주목하고 중지 할 수 있습니다.

여기서 최적화 가능성에 유의하십시오. B로 나눌 때 얻을 수있는 나머지는 0에서 B-1 범위에 있으므로 뚜렷한 0이 아닌 나머지는 유지하므로 이전 나머지 목록을 검색 할 필요가 없습니다. 무언가가 반복된다면. 따라서 알고리즘은 디비전 단계 당 일정한 시간을 소비하고 O(b) 공간이 충분합니다. 나머지 각각이 처음 발생한 숫자 위치를 추적하십시오.

(이 주장, BTW는 또한 반복되는 부분이 최대 B-1 자리 일 수 있다는 수학적 증거입니다. (0588235294117647) 16 자리의 반복 부분이 있습니다. 항상 길이는 항상 분열 실제로 B-1.)

이 작업을 수행하기위한 파이썬 코드는 다음과 같습니다. 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 사전 대신에 약간 더 빠릅니다 (점근 적 측면이 아니라 일정한 요인).

Answer 3

나는 이것이 당신이 찾고있는 것 같아 ..

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

Answer 4

저는 전문가가 아니며이 솔루션이 효율적이지 않을 수 있다고 생각하지만 적어도 쉽게 수행 할 수 있습니다.

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

의견이 잘 받아 들여집니다