La relación de recurrencia que captura el tiempo óptimo del problema de la Torre de Hanoi con n discos es. (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
Respuesta: (D)
Explicación: Los siguientes son los pasos a seguir para resolver la Torre de Hanoi problema de forma recursiva.
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
La función de recurrencia T(n) para la complejidad temporal de la solución recursiva anterior se puede escribir de la siguiente manera.
T(n) = 2T(n-1) + 1
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA