我的老师在算法课上给了我们一个很难的问题。
让我们考虑下面的代码，在该代码中，cc是一个返回随机整数值的原语，它均匀地分布在cc中，并且具有复杂度random(a)。
int test(int n)
{
if(n<=2) return n;
int i = random(n-2);
return test(i) + test(n-2-i);
}
n=9时可能返回的函数；
表达式测试（2016）的最小值是多少？
表达式测试（2016）的最大值是多少？
我试图将表达式推广到一般步骤
[0;a]，但我陷入了概率性的问题中，不知道如何表达它们。这不是家庭作业，只是一些需要考虑的事情。
最佳答案
让我们试着计算i:3..9的test（i），以知道它可能返回9
我们有test（n）=test（i）+test（j），i+j=n-2，i测试（3）=测试（1）+测试（0）=1
试验（4）=试验（2）+试验（0）|试验（1）+试验（1）=2
测试（5）=测试（3）+测试（0）测试（2）+测试（1）=1 3（从这里开始问题）
测试（6）=测试（4）+测试（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%2=0，则返回小于n的偶数（这很酷）
至于最小测试（2016），如果随机数总是返回0，则您将进行测试（2016）=测试（2014）…=测试（2）=2
对于max test（2016），如果随机总是返回（n-2）/2，则为1008
我做了编辑测试（2016）=1008事实上
测试（4n）可以返回{2,4，…，2n}
测试（4n+1）可能返回{1,3，…，2n+1}
测试（4n+2）可能返回{2,4，…，2n+2}
测试（4n+3）可能返回{1,3，…，2n+1}
我认为这可以通过归纳法来验证，对于n=1
测试（4n+4）=测试（2）+测试（4n），因为测试（4n）可能返回=2n我们有测试（4n+4）可能返回2n+测试（2）=2n+2
因为test（4n+4）可以返回test（4n+2），test（4n）=>test（4n+4）可以返回test（4n）=>返回的值都是{2,42n+2}
显然，检验（4n+4）不能返回一个an even数，它是两个检验（i）和检验（j）的和，因为i+j=4n+4，所以i和j都是偶数或都是偶数，并且在归纳法的假设下，结果是偶数最后一步是证明测试（4n+4）不能大于2n+2：
试验（4n+4）=试验（i）+试验（j），其中i+j=4n+2，同样采用归纳法的假设max（试验（i）=所以测试（4n+4）