La Torre de Hanoi

"En el gran templo de Benarés, bajo la cúpula que señala el centro del mundo, reposa una bandeja de cobre sobre la cual

Views 77 Downloads 0 File size 322KB

Report DMCA / Copyright

DOWNLOAD FILE

Recommend stories

Citation preview

"En el gran templo de Benarés, bajo la cúpula que señala el centro del mundo, reposa una bandeja de cobre sobre la cual están colocadas tres agujas de diamante. Benarés, cuyo nombre oficial es Vanarasi, tiene aproximadamente unos dos millones y medio de habitantes. También se la conoce como Kashi (la ciudad de la luz). Esta ciudad situada a orillas del río Ganges es considerada como una de las siete ciudades sagradas de los hindúes.

Se cuenta que una mañana lluviosa el rey mandó colocar en una de las agujas sesenta y cuatro discos de oro puro, ordenados por tamaños; desde el mayor, que reposa en la bandeja, hasta el más pequeño, en lo alto de la aguja. Se llama la torre de Brahma.

Incansablemente, día tras día, los sacerdotes del templo mueven los discos haciéndolos pasar de una aguja a otra, de acuerdo a las leyes de Brahma, que dictan que el sacerdote en turno no mueva más de un disco a la vez, ni lo sitúe encima de un disco de menor tamaño..."

El templo de Benarés ya no existe.

Pero el problema sí.

Las reglas son las siguientes: 1 Sólo se puede mover un disco cada vez. 2 Para cambiar los discos de lugar se pueden usar las tres columnas del juego; es decir que los distintos discos se pueden ir acomodando en las columnas según convenga. 3 Nunca deberá quedar un disco grande sobre un disco pequeño.

Para 1 disco se hace 1 movimiento Para 2 discos se hacen 3 movimientos Para 3 discos se hacen 7 movimientos Para 4 discos se hacen 15 movimientos Para 5 discos se hacen 31 movimientos Para 6 discos se hacen 63 movimientos En general... Para n discos hacen falta 2n - 1 movimientos

Datos experimentales Considerando que: M= movimientos mínimos n= número de discos Los valores obtenidos experimentalmente son: N 1 2 3 4 5

M 1 3 7 15 31

Propuesta de modelo • La propuesta del modelo debe ser obtenido con base en los datos anteriores, considerando a M= variable dependiente y n= variable independiente y que cumple para n discos es: • M= 2n - 1

Identificación de un modelo estudiado en MEI empleando un cambio de variable Si el modelo es M= 2n - 1

entonces: Y=M+1 = 2n (modelo exponencial) Tomando logarítmos: log Y= n log 2 ó lnY= n ln 2 Finalmente Y= exp(n ln2)= exp(0.69N), que puede graficarse linearizando.

Linearización • Con log Y= n log 2 • Identificar a log Y como la función de la variable dependiente y a n como la variable de tipo independiente y comparándolo con la ecuación: • Y=mX +b • Y= log Y;

X= N ; m= log2= 0.301; b= 0

Tabla de datos finales n

M

Y=M+1

logY

1

1

2

0.3010

2

3

4

0.6021

3

7

8

0.9031

4

15

16

1.2041

5

31

32

1.5051

Gráfica Exponencial 0.6931x

y=e

35

2

R =1

30

log Y

25 20 15 10 5 0 0

1

2

3

4

N (número de discos)

5

6