5

我正在为我的期中考试而学习，其中一个练习题是：

考虑递归伪算法 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，m 的可能性对于递归函数 MILK(b); 的输入变得越来越小，最终达到满足条件 a = 1; 的 1; 因此吃饼干并终止算法。

2) 让 M(a) 是您在运行 MILK(a) 时喝的牛奶量。确定 M(a) 的准确值

对于这个，我假设它将是 M(a) = a + a，因为每次运行它时，'a' 都是输入，并且将每个输入加在一起会给你总数。

我的答案看起来如何？或者这完全不正确。谢谢！

4

4 回答 4

2

对于第二个问题，您可以使用总概率定律（转移到预期值 - 您可能必须搜索这个）。

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 程序中），您应该能够识别出一个简单的模式，该模式可能可以通过归纳来证明。

于 2013-10-15T15:47:08.460 回答
1

对于您的第一个问题，请注意以下两个表达式都小于 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); }
于 2013-10-15T17:11:12.770 回答
1

第一个答案很好。

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

于 2013-10-15T15:41:17.627 回答
0

提示：计算 M(a) 的前几个值。了解封闭式公式。用归纳法证明。

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

于 2013-10-15T15:47:49.003 回答