2 votos

Confusión en la Torre de Hanoi a partir de las matemáticas concretas

Así que acabo de empezar a leer Concrete Mathematics como precursor de The Art of Computer Programming vol. 1. Estoy en la página 3 y ya me cuesta. De todos modos, se dice que la recurrencia es:

$2T_{n-1} +1$

Pero no entiendo cómo funciona esto. Si $n$ es 3, entonces tendríamos:

$2T_{3-1}+1$

o

$2(2) + 1 = 4$

¿correcto? Pero eso no es correcto. La respuesta aquí es 7. Siguen calculando diciendo:

$T_3 = 2 * 3 + 1 = 7; T_4 = 2*7+1=15$

Ahora el $T_4$ uno tiene un poco de sentido si se calcula $2*4 - 1$ en lugar de $2*(4-1)$ pero esa lógica no parece aplicarse a éste. Estoy tratando de averiguar si es un rango de $n$ a $1$ pero $2*(3*2*1) + 1 = 13$ así que obviamente eso no está bien...

Oh, tal vez lo tengo. Estoy sustituyendo $2T_{n-1}$ con $2(n-3)$ cuando se supone que debo usar el resultado de $T_{n-1}$ en su lugar y multiplicarlo por 2 y sumarle 1.

Gracias de antemano.

5voto

Anthony Shaw Puntos 858

Una pista:

$T_1=\color{#C00}{1}$
$T_2=2T_1+1=2\cdot\color{#C00}{1}+1=\color{#090}{3}$
$T_3=2T_2+1=2\cdot\color{#090}{3}+1=\color{#00F}{7}$
$T_4=2T_3+1=2\cdot\color{#00F}{7}+1=15$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X