如何找到一个递推方程(对于这个伪码)？
提问于 2018-09-27 06:57:25
我的任务是为下面的问题找到答案，但老实说，我完全不知道该从哪里开始。我不是在寻找直截了当的答案(尽管他们会很感激)，而是我如何找到/得到它们。我理解递归，我只是不知道如何找到一个递归方程。
a.)给出了随机的预期运行时间的递推。
b.)给出对随机(N)调用所执行的递归调用的期望次数的精确递推方程。
c.)给出在第14行执行rerun语句的预期次数的精确递推方程，在所有调用为随机(N)的情况下，递归或不递归。
伪码：
函数随机(U)
- 如果u=1那么
- 回归(1)
- 否则
- 以概率1/2指定x=0，或
- 以概率1/3指定x=1，或
- 按概率1/6分配x=2
- 如果是x=0的话
- (随机(u-1)+随机(u-2))
- 主要目的-如果
- 如果是x=1的话
- (随机(U)+2*随机(u-1))
- 主要目的-如果
- 如果是x=2的话
- (3*随机(U)+随机(U)+ 3)
- 主要目的-如果
- 结束-如果
端随机
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-09-27 08:21:49
首先，需要注意的是，由于问题要求运行时/否。对于调用，递归调用RANDOM之前的系数并不重要(因为所有答案都不取决于实际的返回值)。
此外，由于这些问题询问的是预期的数量，所以您可以将适当的递归调用按概率混合。
a)
一开始很容易。函数的概率混合：
T(u) = [1/2] * [T(u-1) + T(u-2)] +
[1/3] * [T(u) + T(u-1)] +
[1/6] * [T(u) + T(u) ] // + constant amount of workb)
与以前一样，但请记住，每次调用都要添加一个：
N(u) = [1/2] * [N(u-1) + N(u-2) + 2] +
[1/3] * [N(u) + N(u-1) + 2] +
[1/6] * [N(u) + N(u) + 2] // no constants herec)
这比其他两个人更棘手。这个问题要求“所有对随机(U)的调用，无论是递归的还是非递归的”，这似乎是矛盾的，但只有第14行的调用是递归的.
无论如何，忽略这些次要的细节，需要注意的关键是，第11行对RANDOM(u)的调用也可以生成所需的递归调用，而不需要对总数本身作出贡献。修改上述内容：
R(u) = [1/3] * [R(u) ] + // don't add 1 here
[1/6] * [R(u) + R(u) + 2] // add 2 as before请注意，这个问题可能期望您将所有的T(u), N(u), R(u)条款重新安排到LHS。我把这件事留给你，因为这是微不足道的事。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52539858
复制相关文章
点击加载更多
腾讯云开发者
