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 に対して何が返されるかを調べてみましょう。= n-2 かつ 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
したがって、test(n) は、n%2 =0 の場合は n より小さい偶数を返し、それ以外の場合は n より小さい偶数を返す可能性があります (これはクールです)
。 0 を返すと、test(2016)= test(2014)....=test(2) =2
となります。最大 test(2016) の場合、ランダムが常に (n-2)/2
を返す場合は 1008 です。 edit 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 を返す可能性があるので、 2
test(4n+4) は test(4n+2) を返す可能性があり、また test(4n) => test(4n+4) は test(4n) によって返されるすべての値を返す可能性があるため => {2,4, ... 2n+2}
test(4n+4) が偶数を返すことができないことは明らかです。これは、2 つの test(i) と test(j) の合計であり、i+j = 4n+4 であるため、iおよび 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 に答える