Рубрики

Алгоритмы | Анализ алгоритмов | Вопрос 3

Рекуррентное соотношение, фиксирующее оптимальное время задачи Ханойской башни с n дисками, равно. (GATE CS 2012)
(A) T (n) = 2T (n — 2) + 2
(B) T (n) = 2T (n — 1) + n

(C) T (n) = 2T (n / 2) + 1
(D) T (n) = 2T (n — 1) + 1

Ответ: (Д)
Объяснение: Ниже приведены шаги, которые необходимо выполнить для рекурсивного решения проблемы Ханойской башни .

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n

Рекуррентная функция T (n) для временной сложности вышеупомянутого рекурсивного решения может быть записана следующим образом.

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

Алгоритмы | Анализ алгоритмов | Вопрос 3

0.00 (0%) 0 votes