将分数转换为带有重复小数位的字符串（用括号表示）

Question

我想写一个Python 3函数，将以分子和分母给出的分数转换为其十进制数字的字符串表示形式，但是带有括号中的重复小数位。

举个例子：

- `convert(1, 4)` 应输出 `"0.25"` - `convert(1, 3)` 应输出 `"0.(3)"` 而不是 `"0.3333333333"` - `convert(7, 11)` 应输出 `"0.(63)"` 而不是 `"0.6363636364"` - `convert(29. 12)` 应输出 `"2.41(6)"` 而不是 `"2.4166666667"`

我的当前代码在问题的末尾，但如果有非重复和重复小数位置，它将失败。以下是包括调试输出（注释的`print`调用）的示例运行：

----> 29 / 12
5
appended 4
2
appended 1
8
index 2 ['29', 2, 8] result ['2.', '4', '(', '1']
repeating 8
['2.', '4', '(', '1', ')']

这里我做错了什么？

---

我的代码：

def convert(numerator, denominator):
    #print("---->", numerator, "/", denominator)
    result = [str(numerator//denominator) + "."]
    subresults = [str(numerator)]
    numerator %= denominator
    while numerator != 0:
        #print(numerator)
        numerator *= 10
        result_digit, numerator = divmod(numerator, denominator)
        if numerator not in subresults:
            subresults.append(numerator)
            result.append(str(result_digit))
            #print("appended", result_digit)
        else:
            result.insert(subresults.index(numerator), "(")
            #print("index", subresults.index(numerator), subresults, "result", result)
            result.append(")")
            #print("repeating", numerator)
            break
    #print(result)
    return "".join(result)

- Byte Commander

Answer 1

您的代码只需要进行一些小修改（请见下面的注释）：

def convert(numerator, denominator):
    #print("---->", numerator, "/", denominator)
    result = [str(numerator//denominator) + "."]
    subresults = [numerator % denominator]          ### changed ###
    numerator %= denominator
    while numerator != 0:
        #print(numerator)
        numerator *= 10
        result_digit, numerator = divmod(numerator, denominator)
        result.append(str(result_digit))             ### moved before if-statement

        if numerator not in subresults:
            subresults.append(numerator)
            #print("appended", result_digit)

        else:
            result.insert(subresults.index(numerator) + 1, "(")   ### added '+ 1'
            #print("index", subresults.index(numerator), subresults, "result", result)
            result.append(")")
            #print("repeating", numerator)
            break
    #print(result)
    return "".join(result)

- RootTwo

Answer 2

我认为有问题的是您只需要检查先前看到的小数位数是否与循环长度相同，并且它刚刚在此长度之前被看到。

我认为最好的方法是使用一些好的数学方法。

让我们试着想出一种找到分数的小数表示以及如何知道何时会有重复小数的方法。

了解分数是否终止（或重复）的最好方法是查看分母的因数分解（难题）。

有许多找到因数分解的方法，但我们真正想知道的是，这个数字是否有除2或5之外的质因数。为什么？因为十进制展开只是一些数字a / 10 * b。也许1/2 = .5 = 5/10. 1/20 = .05 = 5/100。等等。

因此，10的因数是2和5，因此我们要找出它是否具有除2和5之外的其他因数。完美，那很容易，只需不断地除以2，直到它不再可被2整除，然后再用5做同样的操作。或者反过来。

在开始认真工作之前，我们可能需要先确定它是否可被2或5整除。

def div_by_a_or_b( a, b, number):
    return not ( number % a ) or not ( number % b )

然后我们先除以所有的5，再除以所有的2，然后检查这个数字是否为1。

def powers_of_only_2_or_5(number):
    numbers_to_check = [ 2, 5 ]
    for n in numbers_to_check:
        while not number % n: # while it is still divisible by n
            number = number // n # divide it by n
    return number == 1 # if it is 1 then it was only divisble by the numbers in numbers_to_check

我将其多态化，这样您就可以根据需要更改基础内容。(您只需要该基础的因子，例如在14进制中，您检查2和7而不是2和5)

现在我们要做的就是找出在非终止/重复分数的情况下我们应该怎么做。

现在这里充满了超级数论，所以我会给你留下算法，让你决定是否想在mathforum.org或wolfram alpha上了解更多信息。

现在我们可以轻松地告诉一个分数是否会终止，如果不会，它的重复数字的循环长度是多少。现在我们要做的就是找到循环或开始的数字有多少位。

在寻找高效算法的过程中，我在https://softwareengineering.stackexchange.com/上发现了这篇文章，应该会有所帮助。

一些伟大的见解 - 当一个有理数 m/n，其中 (m,n)=1 被展开时，周期在 s 项之后开始，并且长度为 t，其中 s 和 t 是满足

10^s=10^(s+t) (mod n) 的最小数字。

所以我们需要做的就是找到 s 和 t：

def length_of_cycle(denominator):
    mods = {}
    for i in range(denominator):
        key = 10**i % denominator
        if key in mods:
            return [ mods[key], i ]
        else:
            mods[ key ] = i

让我们生成扩展的数字

def expasionGenerator( numerator, denominator ):
    while numerator:
        yield numerator // denominator
        numerator = ( numerator % denominator ) * 10

现在要小心使用它，因为它会在重复的扩展中创建一个无限循环（正如它应该的那样）。

现在我认为我们已经准备好编写我们的函数了：

def the_expansion( numerator, denominator ):   
# will return a list of two elements, the first is the expansion 
# the second is the repeating digits afterwards
# the first element's first 
    integer_part = [ numerator // denominator ]
    numerator %= denominator
    if div_by_a_or_b( 2, 5, denominator ) and powers_of_only_2_or_5( denominator ):
        return [ integer_part, [ n for n in expasionGenerator( numerator, denominator ) ][1:], [0] ]
    # if it is not, then it is repeating
    from itertools import islice
    length_of_cycle = cycleLength( denominator )
    generator = expasionGenerator( numerator*10, denominator ) 
    # multiply by 10 since we want to skip the parts before the decimal place
    list_of_expansion = [ n for n in islice(generator, length_of_cycle[0]) ] 
    list_of_repeating = [ n for n in islice(generator, length_of_cycle[1]) ]
    return [ integer_part, list_of_expansion, list_of_repeating ] 

现在只需要打印它，这不应该太难。我将先构建一个函数，将数字列表转换为字符串：

def listOfNumbersToString(the_list):
    string = ""
    for n in the_list:
        string += str(n)
    return string

然后创建转换函数：

def convert(numerator, denominator):
    expansion = the_expansion(numerator,denominator)
    expansion = [ listOfNumbersToString(ex) for ex in expansion ]
    return expansion[0] + "." + expansion[1] + "(" + expansion[2] + ")"

在http://thestarman.pcministry.com/上有关于编程话题的有趣阅读材料，类似的问题还可以参考stackoverflow。

- Kenneth Goodman

Answer 3

这并不回答你实际的问题（"为什么我的代码不起作用？"），但也许对你有用。几个月前，我写了一些代码来完成你现在尝试做的事情。这是它。

import itertools

#finds the first number in the sequence (9, 99, 999, 9999, ...) that is divisible by x.
def first_divisible_repunit(x):
    assert x%2 != 0 and x%5 != 0
    for i in itertools.count(1):
        repunit = int("9"*i)
        if repunit % x == 0:
            return repunit

#return information about the decimal representation of a rational number.
def form(numerator, denominator):    
    shift = 0
    for x in (10,2,5):
        while denominator % x == 0:
            denominator //= x
            numerator *= (10//x)
            shift += 1
    base = numerator // denominator
    numerator = numerator % denominator
    repunit = first_divisible_repunit(denominator)
    repeat_part = numerator * (repunit // denominator)
    repeat_size = len(str(repunit))
    decimal_part = base % (10**shift)
    integer_part = base // (10**shift)
    return integer_part, decimal_part, shift, repeat_part, repeat_size

def printable_form(n,d):
    integer_part, decimal_part, shift, repeat_part, repeat_size = form(n,d)
    s = str(integer_part)
    if not (decimal_part or repeat_part):
        return s
    s = s + "."
    if decimal_part or shift:
        s = s + "{:0{}}".format(decimal_part, shift)
    if repeat_part:
        s = s + "({:0{}})".format(repeat_part, repeat_size)
    return s

test_cases = [
    (1,4),
    (1,3),
    (7,11),
    (29, 12),
    (1, 9),
    (2, 3),
    (9, 11),
    (7, 12),
    (1, 81),
    (22, 7),
    (11, 23),
    (1,97),
    (5,6),
]

for n,d in test_cases:
    print("{} / {} == {}".format(n, d, printable_form(n,d)))

结果：

1 / 4 == 0.25
1 / 3 == 0.(3)
7 / 11 == 0.(63)
29 / 12 == 2.41(6)
1 / 9 == 0.(1)
2 / 3 == 0.(6)
9 / 11 == 0.(81)
7 / 12 == 0.58(3)
1 / 81 == 0.(012345679)
22 / 7 == 3.(142857)
11 / 23 == 0.(4782608695652173913043)
1 / 97 == 0.(0103092783505154639175257
73195876288659793814432989690721649484
536082474226804123711340206185567)
5 / 6 == 0.8(3)

我忘记了具体的工作原理......我想我是在试图逆向工程找到一个数字的分数形式，给定其循环小数，这比另一种方式要容易得多。例如：

x = 3.(142857)
1000000*x = 3142857.(142857)
999999*x = 1000000*x - x 
999999*x = 3142857.(142857) - 3.(142857)
999999*x = 3142854
x = 3142854 / 999999
x = 22 / 7

理论上，您可以使用相同的方法从分数转换为小数。主要障碍在于将任意分数转换为形式为“(某个数字)/(若干个9)” 的形式并非完全简单。如果原始分母可被2或5整除，则无法均匀地将其分成任何一个9-repunit。因此，很多“form”的工作是关于消除会使除以999...9变得不可能的因子。

- Kevin

---

请检查您的程序是否包含 test_cases = [(3,12)]。 - Piotr Wasilewicz

让我们看看... 当我在Python 2.7中运行它时，它会像预期的那样给出 0.25。在3.X中，我得到了 0.0.25.0。这是一个问题。我将尝试制定一个版本无关的方法。 - Kevin

你只需要在第16行和第17行中将 / 改为 // 即可 :) - Piotr Wasilewicz

是的，同意。我在其他地方使用//这一事实表明我一开始就尝试使其与Python 3兼容。奇怪的是我没有在所有地方应用它。 - Kevin

Answer 4

主要想法是找出小数点的位置。换句话说，要在哪里放置小数'.'

当一个数字被2或5除尽时，就没有循环小数。1/2 = 0.5，1/5 = 0.2。只有那些不是2或5的数字存在循环小数，如3、7、11。那6呢？事实上，6是2x3，由于3的因素导致了循环小数。1/6 = 1/2 - 1/3 = 非循环部分 + 循环部分。

拿另一个例子来说，1/56。 56 = 8x7 = 2^3x7。请注意，1/56 = 1/7 - 1/8 = 1/7 - 1/2^3。有两个部分。前面的部分是1/7，它是循环的0.（142857），而后面的部分1/2^3 = 0.125不是循环的。然而，1/56 = 0.017（857142）。1/7在'.'之后就开始循环了。1/56的循环部分比1/7晚3位小数。这是因为0.125有3位小数，直到3位小数后才变成循环的。当我们知道循环部分从哪里开始时，使用长除法找出循环的最后一位并不难。

对于5也是类似的情况。任何分数都可以写成a/2^m + b/5^n + 循环部分的形式。循环部分被a/2^m或b/5^n向右推移。很容易发现哪些更难推动循环部分。然后我们就知道循环部分从哪里开始了。

为了找到循环小数，我们使用长除法。由于长除法会得到余数，所以将余数乘以10，然后作为新的分子再次进行除法运算。这个过程一直持续下去。如果数字再次出现，则这就是循环的结尾。

- zerozero nine