我想做一些事情來更好地了解 yield 和 yield from。目標是按順序生成馬爾可夫序列，第一個元素為索引 0。 https://en.wikipedia.org/wiki/Markov_number
我想出了以下代碼。
def chain(iter1, iter2):
while True:
yield next(iter1)
yield next(iter2)
def isMarkov(x,y,z):
if x**2 y**2 z**2 == 3 * x * y * z:
return True
else:
return False
def gen_markov(seed):
x1 = seed[0]
y1 = seed[2]
z1 = y1 1
while not isMarkov(x1,y1,z1):
z1 = 1
yield (x1,y1,z1)
x2 = seed[1]
y2 = seed[2]
z2 = y2 1
while not isMarkov(x2,y2,z2):
z2 = 1
yield (x2,y2,z2)
yield from chain(gen_markov((x1,y1,z1)), gen_markov((x2,y2,z2)))
def markov(n):
g = gen_markov((1,2,5))
markov_nums = set([1,2,5])
while len(markov_nums) <= n:
triple = next(g)
for x in triple:
markov_nums.add(x)
markov_nums = list(markov_nums)
markov_nums.sort()
print(markov_nums[n])
n = int(input('Enter n: '))
markov(n)
這可以在樹狀結構中生成馬爾可夫三元組。
這是由 gen_markov 函式生成的前 35 個馬爾可夫三元組。
(1, 5, 13)
(2, 5, 29)
(1, 13, 34)
(2, 29, 169)
(5, 13, 194)
(5, 29, 433)
(1, 34, 89)
(2, 169, 985)
(5, 194, 2897)
(5, 433, 6466)
(13, 34, 1325)
(29, 169, 14701)
(13, 194, 7561)
(29, 433, 37666)
(1, 89, 233)
(2, 985, 5741)
(5, 2897, 43261)
(5, 6466, 96557)
(13, 1325, 51641)
(29, 14701, 1278818)
(13, 7561, 294685)
(29, 37666, 3276509)
(34, 89, 9077)
(169, 985, 499393)
(194, 2897, 1686049)
(433, 6466, 8399329)
(34, 1325, 135137)
(169, 14701, 7453378)
(194, 7561, 4400489)
(433, 37666, 48928105)
(1, 233, 610)
(2, 5741, 33461)
(5, 43261, 646018)
(5, 96557, 1441889)
(13, 51641, 2012674)
我的問題是我希望能夠按順序生成序列。數字 610 是序列中的第 11 個元素，但遠大于 610 的數字生成的更早。例如，如果您運行 n=11，該函式回傳 2897。有關如何按順序生成序列的任何建議？
uj5u.com熱心網友回復：
這是我對這個問題的貢獻（不是答案），我完全重新編輯了我的第一次嘗試，我不會再進一步??了。為什么？這個問題沒有明確定義：
- 你建議作為參考的維基百科文章很糟糕（另見我的評論）
- 你沒有指定排序規則和馬爾可夫數的定義[我記錄了自己，也有技術/研究論文，但沒有找到任何東西（甚至沒有馬爾可夫數的正確定義！！）]
因此，只要您不改進問題以致每個人都可以訪問它，我就會認為它很接近。
建議
- 向數學堆疊交換社區詢問如何生成有序馬爾可夫序列
- 在
yield/yield from實作之前，您應該有一個作業示例并了解它（？），即在這種情況下選擇另一個（更簡單的）問題開始！ - 提供有關問題的更多資訊
考慮
馬爾可夫數是二叉樹的節點，所以實作二叉樹
樹的每一層都有兩個（相對）最小值，最外部的葉子，由斐波那契和佩爾序列描述。斐波那契是最小的。這些可以用作包含 n-Markov 數的串列大小的中斷條件
通過保持簡單，使用貪心演算法......例如，如果你想要一個 n 階馬爾可夫數的串列，請考慮一個完美的二叉樹（它的計算量很大，大小由初始值為 1 的幾何級數建模，并且常見的比率 2) 并按遞增順序對它們進行排序，并考慮此類串列的第 1 個 n 條目，例如 smt
list(sorted(markov_triples, key=lambda p: p[1]))[:n]
評論中提到的危險，維基百科文章中馬爾可夫數194對應的節點沒有正確標記，請參閱我的評論以供參考。這里有一個比維基百科更詳細的馬爾可夫樹。
有關計算樹的葉子的示例代碼。我使用一個完美的樹作為參考，它的節點可以被唯一地描述為幾何序列的術語來定位葉子，然后找到通向根的左右路徑的序列，最后應用“馬爾可夫規則”來找到三元組：
from math import log
def find_lv(n): # provided that the root as vertex 1, n: absolute node index
return int(log(n, 2))
def branch_path(n, k): # leaf to root
# n: depth, k: 0 <= index <= 2**n - 1
path = [k]
for i in range(n-1):
if path[-1] % 2 == 0:
path = [path[-1] // 2]
else:
path = [path[-1] // 2]
return path
def branch_path_as_directions(path): # leaf to root
return ['L' if p % 2 == 0 else 'R' for p in path[:-1]] # the root should be skiped!
def new_sol(triple):
x, y, z = triple
return (x, y, 3*x*y - z)
def left_triple(triple):
x, y, z = triple
return (x, z, y)
def right_triple(triple):
x, y, z = triple
return (y, z, x)
def markov_triples(n):
# n: is the absolute position of a node in the tree, i.e. wrt to a geometric series
# return the branch of triples corresponding to that node
# initial values of the sequence
triples = [(1, 1, 1), (1, 1, 2), (1, 2, 5)]
if n == -2:
return triples[0]
if n == -1:
return triples[1]
if n == 0:
return triples[2]
depth = find_lv(n) 1
# get path the leaf with n
path = branch_path(depth, n)
path_l_r = branch_path_as_directions(path)
# flow from root to leaf
for direction in path_l_r[::-1]:
if direction == 'L':
triples = [new_sol(left_triple(triples[-1]))]
else:
triples = [new_sol(right_triple(triples[-1]))]
return triples
print(markov_triples(10))
輸出
[(1, 2, 5), (1, 5, 13), (5, 13, 194), (5, 194, 2897)]
uj5u.com熱心網友回復：
更新。我能夠使用佇列找到一個相當好的解決方案（盡管并不完美）。
# Markov Numbers
seed = (1,2,5)
markov = set()
markov.add(1)
queue = []
queue.append(seed)
n = int(input('Enter n: '))
while len(markov) <= n**3:
curr = queue.pop()
p,q,r = (curr)
markov.add(p)
markov.add(q)
markov.add(r)
left = (p,r,3*p*r-q)
right = (q,r,3*q*r-p)
queue.insert(0,left)
queue.insert(0,right)
markov = list(markov)
markov.sort()
print(markov[n])
我對此進行了最多 n=39 的測驗（從索引 0 開始）。這與 OEIS 中的前 40 個元素相匹配。https://oeis.org/A002559/list
0th element: 1
1th element: 2
2th element: 5
3th element: 13
4th element: 29
5th element: 34
6th element: 89
7th element: 169
8th element: 194
9th element: 233
10th element: 433
11th element: 610
12th element: 985
13th element: 1325
14th element: 1597
15th element: 2897
16th element: 4181
17th element: 5741
18th element: 6466
19th element: 7561
20th element: 9077
21th element: 10946
22th element: 14701
23th element: 28657
24th element: 33461
25th element: 37666
26th element: 43261
27th element: 51641
28th element: 62210
29th element: 75025
30th element: 96557
31th element: 135137
32th element: 195025
33th element: 196418
34th element: 294685
35th element: 426389
36th element: 499393
37th element: 514229
38th element: 646018
39th element: 925765
這并不完美，因為仍然需要搜索比 n 更遠的距離才能獲得大約 n>10 的準確結果。這就是為什么有 n**3 項的原因。如果有人可以解釋更好的方法，將不勝感激。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/323486.html