Python 使用分数时出现内存错误

Question

我正在使用 stern-brocot 序列生成分数。这些分数已附加到列表中。现在我需要修改这个分数列表，因为问题要求我满足列表中存在的分数的 2 个条件。

1) 对于列表中存在的每个简化分数 a/b，b/2a 也必须存在。

2) 每 2 个简化分数 a/b 和 c/d, (a+b)/(c+d) 也应该在场。

我已经编写了以下代码来做到这一点。

# Python program to print 
# Brocot Sequence
from fractions import Fraction

import math

class MyFraction:  # This class has been defined to return unsimplified fractions as they are as the'd get simplified using the fractions module
    def __init__(self, numerator=1, denominator=1):
        self.numerator = numerator
        self.denominator = denominator

    def get_fraction(self):
        return Fraction(numerator=self.numerator, denominator=self.denominator)

    def __repr__(self):
        return '{}/{}'.format(self.numerator, self.denominator)


def SternSequenceFunc(BrocotSequence, n):

    # loop to create sequence
    for i in range(1, n):

        considered_element = BrocotSequence[i]
        precedent = BrocotSequence[i-1]

        # adding sum of considered
        # element and it's precedent
        BrocotSequence.append(considered_element + precedent)

        # adding next considered element
        BrocotSequence.append(considered_element)


    # printing sequence..
     for i in range(0, n):
        print(BrocotSequence[i] , end=" ")

     print("\n")

# Function to determine if a fraction is simplified or not

def is_simplified(frac):

    if frac == Fraction(frac.numerator, frac.denominator):

        return True

    else:

        return False

# Function to modify the set to satisfy the given conditions

def modify_set(list_fractions):

    # To satisfy the 1st condition
    for fraction in list_fractions:
        numerator = fraction.numerator
        denominator = fraction.denominator
        list_fractions.append(MyFraction(denominator, 2*numerator))

    # To satisfy the 2nd condition
    for fraction in list_fractions:
        if is_simplified(fraction):
            for frac in list_fractions:
                if frac != fraction:
                    if is_simplified(frac):
                        f = MyFraction((fraction.numerator+frac.numerator), (fraction.denominator+frac.denominator))
                        list_S.append(f)

while True: 

    list_S = []

    count = 0
    # Driver code
    n = int(input("Enter value of n : "))
    BrocotSequence = []

    # adding first two element
    # in the sequence
    BrocotSequence.append(1)
    BrocotSequence.append(1)

    SternSequenceFunc(BrocotSequence, n)

    for i in range(1, n):
        list_S.append(Fraction(BrocotSequence[i], BrocotSequence[i-1])) # Appending the list with fractions generated from stern-brocot sequence

    modify_set(list_S)

    print("\n Printing all fractions : \n")
    for fraction in list_S:
        count = count + 1
        print("\n", fraction)

    print("Number of fractions: {}".format(count))

在运行这段代码之后，我得到了一个 Memory Error 而运行的 modify_set 函数。我不明白为什么。谁能帮我理解为什么以及如何解决这个问题？

提前致谢。

Answer 1

您在此处迭代时添加到 list：

for fraction in list_fractions:
    numerator = fraction.numerator
    denominator = fraction.denominator
    list_fractions.append(MyFraction(denominator, 2*numerator))

每次从list_fractions中拉取一个元素，然后添加一个新元素（最终将依次迭代）。所以这个循环永远不会结束，并且 list 永远增长（或者直到 MemoryError 无论如何）。

类似地，在该函数的下一个循环中（不是说您会到达它），您在 list_fractions 上有一个嵌套循环，虽然它在这里不太明显，但它也是无限，因为每次迭代都会附加到 list_S（这是一个全局变量），它作为 list_fractions 参数传递，所以它们都是同一个 list 的别名（Python 函数调用不会复制其参数的内容，只会复制引用本身，因此除了将 list_fractions 重新绑定到新对象之外，任何其他操作都会修改 list_S。

我不知道你想要的逻辑，但如果目标是只为现有条目添加新条目（而不是处理添加的条目），一个解决方案是迭代 list，例如：

# list_fractions[:] returns a new list with references to the same values as
# the original list, but unaffected by subsequent additions and removals
for fraction in list_fractions[:]:
    numerator = fraction.numerator
    denominator = fraction.denominator
    list_fractions.append(MyFraction(denominator, 2*numerator))

你的嵌套循环会更复杂（取决于内循环是否应该处理 list_fractions 的更新副本）；我将让您确定正确的行动方案。

Python 使用分数时出现内存错误

Memory error in Python while using fractions

python

fractions

python-3.x