伪代码递归函数

Question

我正在学习期中考试，并且练习题目之一是：

考虑递归伪算法 Milk(a)，其中输入整数 a≥1。

MILK(a)
    if a = 1;
    then eat cookie;
    else drink glass of milk;
       select a random integer b with 1 <= b <= a-1
       MILK(b);
       MILK(a-b);
    endif

1) 解释为什么对于任何整数 a>= 1 算法 MILK(a) 都会终止。

我认为这是因为 n-1 的存在，使得输入到递归函数 MILK(b) 中的 m 的可能性变得越来越小；最终达到满足条件 a = 1 的情况，并吃掉一个饼干从而结束算法。

2) 让 M(a) 表示运行 MILK(a) 时喝的牛奶杯数。确定 M(a) 的确切值。

对于这个问题，我认为 M(a) = a + a，因为每次运行时'a'都是输入，将每个输入相加就可以得到总数。

我的答案看起来怎么样？还是完全不正确的吗？谢谢！

- pyramid

---

是要求 M(a) 的确切值？还是期望值？ - phimuemue

Answer 1

对于第二个问题，您可以使用总概率法则（转换为期望值-您可能需要搜索此内容）。 M（a）表示玻璃数量（正如您所建议的），E（）是某些事物的期望值。然后，这个总概率法则会得出以下结果：

E(M(a)) = sum(E(M(a) | b=i) * Pr(b=i), i=1..a-1) =
        = ... =
        = 1/(a-1) * (1+sum(E(M(i)+M(a-i), i=1..a-1)))

据我所了解，基本情况 M（1）= 0 成立。

如果您转换上述递归关系并尝试它（例如在小型 Python 程序中），您应该能够识别出一种简单的模式，可能可以通过归纳证明。

- phimuemue

Answer 2

对于你的第一个问题，请注意下面两个表达式都小于a，当a等于1时递归停止，你能观察到milk()被调用了多少次吗？它是有界的吗？

b < a
a-b < a
MILK(1) returns (no recursion)

手动计算一些值得出饮用牛奶的数量，你会看到一个模式。这有助于你理解。

请注意，随机数生成增加了复杂性，但是问问自己，如果你选择b=1、b=2、b=a/2或者b=a-1，结果是否有所不同？

你的答案是正确的，但上述内容可以帮助你解释你的推理。

一旦你计算了几个MILK(v)的调用的饮用数量，你应该能够得出一个公式：MILK(v)=formula(v)。

试试MILK(3)、MILK(4)、MILK(5)、MILK(9)。

请注意，Ruby可以用很少的语法表达你的算法。

rdm = Random.new
def milk(a)
    if(a==1) then
        print "eat cookie\n";
    else
        print "drink milk\n";
        b = Random.rand(1..a-1)
        print "rand (1,#{a-1}) #{b}\n";
        milk(b)
        milk(a-b)
    end
end
ARGV.each { |argi| milk(argi.to_i); }

- ChuckCottrill

Answer 3

第一个答案很好。

然而，第二个答案不正确。考虑a=1。你的答案是两杯牛奶，而正确答案是零。提示：尝试手动计算一些小例子，以了解算法中正在发生的事情。

- NPE

---

谢谢，但我能不能这样说，在B(n) = n + n - 1（n的总数）。所以如果是2，例如，它将是2+2-2，因为n最终会变成1？如果我的回答有点令人困惑，请见谅。 - pyramid

@pyramid B(n)是从哪里来的？这和M(a)是一样的吗？ - Mashmagar

哦，对不起，我看错了问题。B(n)与M(a)相同。我的意思是M(a)= a + a -1。 - pyramid

Answer 4

提示：计算M（a）的前几个值。了解封闭形式公式的想法。通过归纳证明。

下一个提示：思考一下，这个值是否取决于每个b的选择？

- chill