Рубрики

ВОРОТА | GATE-CS-2002 | Вопрос 3

Решение рекуррентного уравнения T (2 k ) = 3 T (2 k-1 ) + 1, T (1) = 1, имеет вид:
(А) 2 К
(В) (3 k + 1 — 1) / 2
(С) 3 бревно
(D) 2 log 3k

Ответ: (Б)
Пояснение: у нас есть

T (2 k ) = 3 T (2 k-1 ) + 1

= 3 2 Т (2 к-2 ) + 1 + 3
= 3 3 Т (2 к-3 ) + 1 + 3 + 9
, , , (k шагов рекурсии (глубина рекурсии))
= 3 кт (2 кк ) + (1 + 3 + 9 + 27 +… + 3 к-1 )
= 3 к + ((3 к -1) / 2)
= ((2 * 3 к ) + 3 к — 1) / 2
= ((3 * 3 к ) — 1) / 2
= (3 k + 1 — 1) / 2

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

ВОРОТА | GATE-CS-2002 | Вопрос 3

0.00 (0%) 0 votes