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))

运行完这段代码后，我在运行modify_set函数时得到了一个Memory Error。我不明白为什么。有人能帮我理解为什么以及如何解决这个问题吗？你知道吗

提前谢谢。你知道吗

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的更新副本）；我将让您确定正确的操作过程。你知道吗