迭代在Python的斯特恩Brocot树的部分 [英] Iterating over parts of the Stern-Brocot tree in Python

问题描述

我的目标是要遍历对[A，B]一个互质B和A + B＆LT; = N。例如，如果n = 8，我要遍历[1,2]，[2，3]，[3,4]，[3,5]，[1,3]，[2,5]，[ 1，4]，[1,5]，[1,6]，[1,7]。
我首先想到的是用船尾Brocot树递归函数：

My goal is to iterate over the pairs [a,b] a coprime to b and a+b<=n. For example, if n=8, I want to iterate over [1, 2], [2, 3], [3, 4], [3, 5], [1, 3], [2, 5], [1, 4], [1, 5], [1, 6], [1, 7].
My first thought was a recursive function using the Stern-Brocot tree:

def Stern_Brocot(n,a=0,b=1,c=1,d=1):
if(a+b+c+d>n):
    return 0
x=Stern_Brocot(n,a+c,b+d,c,d)
y=Stern_Brocot(n,a,b,a+c,b+d)
if(x==0):
    if(y==0):
        return [a+c,b+d]
    else:
        return [a+c]+[b+d]+y
else:
    if(y==0):
        return [a+c]+[b+d]+x
    else:
        return [a+c]+[b+d]+x+y

正如预期的那样，

As expected,

>>> Stern_Brocot(8)
[1, 2, 2, 3, 3, 4, 3, 5, 1, 3, 2, 5, 1, 4, 1, 5, 1, 6, 1, 7]

和对于n＆LT; = 995，效果很好。但突然当n> = 996，它使这个错误：

And for n<=995, it works well. But suddenly at n>=996, it gives this error:

Traceback (most recent call last):
  File "<pyshell#17>", line 1, in <module>
    a=Stern_Brocot(996)
  File "C:\Users\Pim\Documents\C Programmeren en Numerieke Wisk\Python\PE\PE127.py", line 35, in Stern_Brocot
    y=Stern_Brocot(n,a,b,a+c,b+d)
...
  File "C:\Users\Pim\Documents\C Programmeren en Numerieke Wisk\Python\PE\PE127.py", line 35, in Stern_Brocot
    y=Stern_Brocot(n,a,b,a+c,b+d)
RuntimeError: maximum recursion depth exceeded in comparison

和，因为我想n至等于120000，这种做法是行不通的。 所以我的问题是：这将是一个很好的方法来遍历Stern_Brocot树的部分？ （如果有另一种方式来遍历互质，这会是一样好）。

And since I want n to equal 120000, this approach won't work. So my question is: what would be a good approach to iterate over parts of the Stern_Brocot tree? (if there's another way to iterate over coprime integers, that'd be good as well).

推荐答案

下面是一个非递归执行

def Stern_Brocot(n):
    states = [(0, 1, 1, 1)]
    result = []
    while len(states) != 0:
        a, b, c, d = states.pop()
        if a + b + c + d <= n:
            result.append((a+c, b+d))
            states.append((a, b, a+c, b+d))
            states.append((a+c, b+d, c, d))
    return result

这篇关于迭代在Python的斯特恩Brocot树的部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！