Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 51

Рассмотрим следующий псевдокод. Какое общее количество умножений должно быть выполнено?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

(A) Половина произведения трех последовательных целых чисел.
(B) Одна треть произведения трех последовательных целых чисел.
(C) Одна шестая произведения трех последовательных целых чисел.
(D) Ничего из вышеперечисленного.

Ответ: (с)
Объяснение: Оператор «D = D * 3» выполняется n * (n + 1) * (n-1) / 6 раз. Давайте посмотрим, как.
Для i = 1 оператор умножения выполняется (n-1) + (n-2) + .. 2 + 1 раз.
Для i = 2 оператор выполняется (n-2) + (n-3) + .. 2 + 1 раз
……………………… ..
……………………….
Для i = n-1 оператор выполняется один раз.
Для i = n оператор вообще не выполняется

В общем, заявление выполняется в следующий раз
[(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] +… + 1 + 0

Вышеприведенная серия может быть записана как
S = [n * (n-1) / 2 + (n-1) * (n-2) / 2 +… .. + 1]

Сумма вышеуказанных рядов может быть получена путем вычитания рядов из стандартного ряда S1 = n2 + (n-1) 2 + .. 12. Сумма этого стандартного ряда равна n * (n + 1) * (2n + 1) / 6

S1 — 2S = n + (n-1) +… 1 = n * (n + 1) / 2
2S = n * (n + 1) * (2n + 1) / 6 — n * (n + 1) / 2
S = n * (n + 1) * (n-1) / 6
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 51

0.00 (0%) 0 votes