0

我的老师给了我们一道关于算法课程的非常难的问题。

让我们考虑下面的代码，其中random(a)是一个返回随机整数值的原语，均匀分布[0;a]，并且具有复杂性Theta(1)。

  int test(int n)
{
  if(n<=2) return n;
  int i = random(n-2);
  return test(i) + test(n-2-i);
}

  1. 什么可能返回 n = 9 的函数；

  2. 表达式测试（2016）的最小值是多少？

  3. 表达式测试（2016）的最大值是多少？

我试图将表达式概括为通用步骤k，但我陷入了概率性事物中，我不知道如何表达它们。这不是家庭作业，只是需要思考的事情。

4

1 回答 1

1

让我们尝试计算 i:3..9 的 test(i) 以了解 9 可能返回的结果
我们有 test(n) = test(i) + test(j) 且 i+j = n-2, i < = n-2 and j <= n-2
test(3)= test(1) + test(0) = 1
test(4)= test(2) + test(0) || 测试(1)+ 测试(1) = 2
测试(5)= 测试(3) + 测试(0) || 测试(2) + 测试(1) = 1 || 3 (这里开始问题)
test(6) = test(4)+ test(0) || 测试(3)+ 测试(1) || 测试(2)+ 测试(2) = 2 || 4
测试(7) = 测试(5)+ 测试(0) || 测试(4)+ 测试(1) || 测试(3)+ 测试(2) = 1 || 3
测试(8) = 测试(6)+ 测试(0) || 测试(5)+ 测试(1) || 测试(4)+ 测试(2) || 测试(3)+ 测试(3)= 2 || 4
测试(9) = 测试(7)+ 测试(0) || 测试(6)+ 测试(1) || 测试(5)+ 测试(2) || 测试(4)+ 测试(3)= 1 || 3 || 5
因此，如果 n%2 =0，test(n) 可能会返回小于 n 的偶数，而在另一种情况下会返回小于 n 的偶数（这很酷）
至于最小测试（2016），如果随机总是返回 0 你将有 test(2016)= test(2014)....=test(2) =2
对于 max test(2016) 它是 1008，如果随机总是返回 (n-2)/2
我做了编辑 test(2016) = 1008 实际上
test(4n) 可能返回 {2,4,...,2n}
test(4n+1) 可能返回 {1,3,...,2n+1}
test(4n +2) 可能返回 {2,4,...,2n+2}
test(4n+3) 可能返回 {1,3,...,2n+1}
我认为这可以通过归纳来验证，它对于 n =1
test(4n+4) = test(2) + test(4n) 为真，因为 test(4n) 可能返回 = 2n 我们有 test(4n+4) 可能返回 2n + test(2) = 2n + 2
因为 test(4n+4) 可能返回 test(4n+2) 并且 test(4n) => test(4n+4) 可能返回 test(4n) 返回的所有值 => 它可以返回 {2,4, ... 2n+2}
很明显 test(4n+4) 不能返回一个偶数，它是两个 test(i) 和 test(j) 的和，因为 i+j = 4n+4，我和 j 都是偶数或都是偶数，并且在归纳法的假设下，结果是偶数。
最后一步是证明 test(4n+4) 不能大于 2n +2：
test(4n+4) = test(i) + test(j) with i+j = 4n +2，再次用归纳法假设 max(test(i)=< (i/2)+1 and max(test(j)) <= (j/2)+1
所以 test(4n+4) <= 2n + 3 并且因为它是偶数测试(4n+4) <= 2n + 2。

于 2016-06-21T09:41:15.093 回答