我正在学习期中考试,并且练习题目之一是:
考虑递归伪算法 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'都是输入,将每个输入相加就可以得到总数。
我的答案看起来怎么样?还是完全不正确的吗?谢谢!
M(a)
的确切值?还是期望值? - phimuemue