0

This question just went over my head:

A function G(m) is defined as below:

a) If m <= 100 then G(m) = G(G(m + 11))

b) If m > 100 then G(m) = m – 10

According to above question, how do I design a constant-time algorithm that calculates G(m)?

4

1 回答 1

1

（b）部分显然可以在恒定时间内计算，假设m适合整数变量。

问题要求证明的棘手部分是（a）部分是恒定的。然后O(1)时间随之而来。这可以使用数学归纳法或其他方式来完成。

归纳证明如下。

首先观察G(101)根据定义等于 101 - 10 = 91。

因为90 <= n <= 100它认为G(n) = G(G(n + 11))，在哪里n + 11 > 100。因此G(n)它等于G(n + 11 - 10) = G(n+1)，即 91。

由此，十个方程G(91 - 1) = 91, G(91 - (1 - 1)) = 91, ...,G(91 - (1 - 10)) = 91都是正确的。这是一般归纳的基础。

归纳步骤：假设G(91 - i) = 91, G(91 - (i - 1)) = 91, ...,对于从 1 到某个界限G(91 - (i - 10)) = 91的所有数字都为真。i

然后G(91 - (i + 1)) = G(G(91 - i - 1 + 11)) = G(G(91 - (i - 10)))。从基本步骤，我们知道G(91 - (i - 10)) = 91. 将其代入上面的等式，我们得到G(91)，也已知为 91。由此可以得出，假设也适用i+1。

因此，G(91 - n)对于所有 ， 等于 91 n >= 1。归纳证明。

GPython中用于计算的恒定时间算法的示例：

def G(m):
   if m > 100:
      return m - 10
   else:
      return 91
于 2017-08-16T19:53:46.947 回答