回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我一直在尝试解决麻省理工学院的计算机科学数学习题集,这里有一个问题:</p>
<blockquote>
<p>Each monk entering the Temple of Forever is given a bowl with 15 red beads and 12 green beads. Each time the Gong of Time rings, a monk must do one of two things:</p>
<ol>
<li>Exchange: If he has 3 red beads in his bowl, then he may exchange 3 red beads for 2 green beads.</li>
<li>Swap: He may replace each green bead in his bowl with a red bead and replace each red bead in his bowl with a green bead. That is, if he starts with i red beads and j green beads, then after he performs this operation, he will have j red beads and i green beads.</li>
</ol>
<p>A monk may leave the Temple of Forever only when he has exactly 5 red beads and 5 green beads in his bowl.</p>
</blockquote>
<p>这其中有一些子问题:</p>
<ol>
<li>证明没有人离开过圣殿。我用数学归纳法证明了这一点</李>
<li>证明这个问题只能达到有限个状态。这一证明也是通过数学归纳法完成的,证明了红色珠子和绿色珠子的数量之和只能减少或保持不变</李>
<li>(这就是我被卡住的地方)一个僧侣在任何执行永世殿机器的过程中可以访问的唯一状态的真实最大数量是多少</李>
</ol>
<p>在花了相当长的时间思考子问题3之后,我放弃了,决定写一个程序来计算唯一状态的数量</p>
<pre><code>class Node:
def __init__(self, r, g):
self.r = r
self.g = g
def swap(self):
if self.g <= 0 or self.r <= 0:
return None
return Node(self.g, self.r)
def exchange(self):
if self.r >= 3:
return Node(self.r - 3, self.g + 2)
return None
def __hash__(self):
return hash((self.r, self.g))
def __eq__(self, other):
if self is None and other is None:
return True
if self is None or other is None:
return False
return self.r == other.r and self.g == other.g
def __repr__(self):
return "({}, {})".format(self.r, self.g)
start = Node(15, 12)
queue = []
graph = []
visited = set()
queue.append(start)
while (queue):
curr = queue.pop(0)
visited.add(curr)
graph.append(curr)
s = curr.swap()
e = curr.exchange()
for el in [s, e]:
if el != None:
if el not in visited:
queue.append(el)
print(visited, len(visited))
</code></pre>
<p>我从程序中得到的答案是</p>
<blockquote>
<p>{(6, 9), (16, 9), (0, 7), (2, 5), (8, 5), (5, 8), (10, 8), (10, 7), (16, 3), (5, 18), (0, 17), (14, 1), (8, 15), (10, 13), (4, 16), (9, 16), (7, 5), (14, 2), (13, 10), (3, 1), (6, 13), (20, 3), (3, 11), (4, 12), (10, 3), (6, 14), (7, 15), (18, 5), (3, 6), (8, 6), (4, 1), (9, 7), (6, 4), (11, 4), (16, 4), (5, 17), (11, 9), (0, 18), (14, 6), (13, 6), (19, 2), (18, 6), (1, 19), (15, 7), (0, 8), (4, 11), (3, 5), (4, 6), (9, 2), (5, 7), (4, 17), (11, 3), (7, 4), (14, 12), (12, 4), (19, 1), (3, 15), (1, 3), (5, 13), (3, 21), (11, 14), (12, 9), (18, 1), (15, 12), (2, 19), (3, 10), (1, 14), (8, 10), (9, 11), (3, 16), (8, 16), (11, 13), (0, 22), (17, 5), (6, 18), (7, 14), (12, 14), (19, 6), (15, 3), (2, 20), (1, 4), (0, 12), (1, 9), (4, 2), (2, 14), (9, 6), (5, 3), (6, 8), (11, 8), (16, 8), (14, 7), (13, 5), (1, 18), (2, 4), (9, 12), (4, 7), (9, 1), (12, 5), (15, 8), (0, 3), (2, 9), (8, 1), (5, 12), (3, 20), (10, 12), (6, 3), (9, 17), (7, 10), (12, 10), (13, 11), (1, 13), (8, 11), (2, 10), (0, 23), (17, 4), (6, 19), (14, 11), (12, 15), (7, 9), (13, 1), (17, 9), (15, 2), (20, 2), (0, 13), (21, 3), (1, 8), (2, 15), (5, 2), (10, 2)} 129</p>
</blockquote>
<p>所以,129。但当我看问题集的解决方案时(对于子问题#3),下面是它的说明</p>
<blockquote>
<p>Each move in the sequence must be either an exchange or swap, since these are the only legal moves. Now, whenever the monk performs an exchange operation, the sum r + g decreases by one. </p>
<p>(r - 3) + (g + 2) = (r + g) - 1</p>
<p>In contrast, swaps do not have any effect on the sum. Furthermore, we know that the sum r + g must be at least 3 to perform an exchange operation. Therefore, there can be at most 25 exchange operations in the sequence. </p>
<p>Now consider swap operations: between each pair of exchanges in the sequence, there may be an unlimited number of swaps. However, only a single swap can take the monk to a new state: if at step k the monk is in state (r, g), then at step k + 2, he will return to the same state. Therefore, an upper bound on the number of unique states in any execution of the machine is 25 + 26 + 1 = 52 (if swaps are inserted at both the beginning and end of the sequence).</p>
</blockquote>
<p>我的程序哪里出错了?我对问题陈述的理解是否不正确(与我编写的程序不符)?而且,我真的不理解他们给出的解决方案。有更好的解释方法吗?例如,我不了解的一个问题/事情是,解决方案指出,每次交换操作,珠子的总和减少1。因此,我们可以通过交换操作获得25个新的州。但图中每一层的每一个和都可以用多种方式表示,是吗?那么必须有更多的状态是通过exchange操作创建的?这是完整问题集的<a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/recitations/MIT6_042JF10_rec03.pdf" rel="nofollow noreferrer">link</a>,它是<a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/recitations/MIT6_042JF10_rec03_sol.pdf" rel="nofollow noreferrer">solution</a></p>