1

以下是我的算法和数据结构课程中的一个练习，旨在教授一些关于使用循环不变量分析算法的知识。

设置如下；我们有一个装有n 个弹珠的罐子。大理石要么是红色的，要么是蓝色的。我们还有无数的红色弹珠。我们的目标是通过使用这个算法来清空罐子

算法如下：

input: Jar with *n* marbles each of color RED or BLUE
i <- n
while i > 1 do
  Pick two arbitrary marbles m1, m2 from the jar.
  if Color(m1) == Color(m2) then
    Throw the two marbles away
    Place a RED marble in the jar
  end
  else
    Throw away the RED marble
    Put the BLUE marble back in the jar
  end
  i = i - 1
end

1）争辩说，在算法结束时，我们在罐子里留下了 1 个弹珠。我的想法是说我们有一个如下的循环不变式

在 while 循环的迭代开始时，还剩下 n-(ni) 个弹珠

然后证明在初始化、维护和终止期间不变量是正确的，但是我不确定我应该如何处理这个问题，有人可以帮忙吗？

例如，在初始化时，很明显循环不变量是因为我们在 jar 中有n 个弹珠，因此n-0 = n来自不变量，但是我应该如何处理其余的？

4

1 回答 1

1

由于这是家庭作业，我不想为你做整个问题，但我可以让你朝着正确的方向开始。

让我们从最简单的问题形式之一开始：n = 2

现在有3种可能：

  1. 2 红色
  2. 2 蓝色
  3. 1 个红色和 1 个蓝色

案例 1 和 2：

把两个弹珠都拉出来，它们是相同的颜色，所以把两个都扔掉，从堆里拉出一个红色的弹珠，放进罐子里。罐子里还剩下一颗大理石，所以我们停下来。

案例3：

把两个弹珠都拉出来，它们颜色不一样，所以扔掉红色的，把蓝色的放回去。罐子里还剩下一颗弹子，所以我们停下来。

现在 n = 2 已经计算在内，证明你可以从 3, 4, 5 ... n 颗弹珠达到这个状态。对于 n = 1，显然罐子里只有一个弹珠，因为你永远不会进入循环。我不知道你想对 n = 0 做什么，那将是唯一可以让罐子变空的情况。

于 2020-02-04T22:10:08.457 回答