Algoritmo
Recursivo
Los Aros Chinos admiten un algoritmo recursivo.
Es habitual cuando está involucrado el código Gray.
Un algoritmo se denomina recursivo cuando
recurre a sí mismo para su definición.
Esta sección puede ser complicada
de entender si no programas, pero puedes intentar entender las ideas básicas.
En Los Aros Chinos la recursividad no es
tan didáctica como en otros puzzles.
Empecemos con la nomenclatura.
Realizaremos un Algoritmo Recursivo para
solucionar el puzzle de N aros. En las figuras utilizaré N=5.
Denomino SOLUCION (N) al proceso para solucionar
el puzzle desde La Posición Inicial Extrema.
Es decir el proceso que saca el último
aro.
Denomino NOICULOS (N) al proceso contrario.
Partiendo de la posición con todos los aros fuera permite llegar
hasta la Posición Inicial Extrema.
Es decir el proceso que mete el último
aro.
Sabemos que son procesos inversos.
EDCBA
00000
10000
Por otro lado conviene definir las
manipulaciones básicas de un sólo aro X.
Las denominaremos:
METER Aro X
SACAR Aro X
Tenemos que definir los procesos no
básicos, SOLUCION, NOICULOS. Es en principio necesario, ya que son
procesos diferentes
SOLUCION
El proceso de SOLUCION puede ser expresado
de modo gráfico, para N=5
Indicando unos estados intermedios claves.
Figuras 23, 24, 25.
| EDCBA |
Proceso |
| 10000 |
|
| |
NOICULOS (N-1) |
| 11000 |
|
| |
SACAR ARO N |
| 01000 |
|
| |
SOLUCION (N-1) |
| 00000 |
|
Figuras 23, 24, 25. SOLUCION recursiva
en modo gráfico
SOLUCION (N)
Sí N=1 Entonces
En caso contrario
-
NOICULOS ( N -1 )
-
SACAR ARO N
-
SOLUCION ( N -1 )
NOICULOS
El proceso de NOICULOS expresado de modo
gráfico es el siguiente, para N=5:
| EDCBA |
Proceso |
| 00000 |
|
| |
NOICULOS (N-1) |
| 01000 |
|
| |
METER ARO N |
| 11000 |
|
| |
SOLUCION (N-1) |
| 10000 |
|
NOICULOS (N)
Sí N=1 Entonces
En caso contrario
-
NOICULOS ( N -1 )
-
METER ARO N
-
SOLUCION ( N -1 )
Es curiosa esta doble recurrencia.
En principio el Algoritmo está bien
definido, ya que recurre a procesos con un número N inferior. Tienen
lo que se denomina salida por la base, cuando N=1, que deja de realizar
llamadas recursivas y realiza un proceso básico.
Si el proceso SOLUCION imprimiese el aro
a manipular, nos encontraríamos con la conocida secuencia:
A B A C A B A D A B A C A B A E A B A C A
B A D A B A C A B A
Sabemos que aunque son procesos inversos,
en realidad son casi iguales, manipulan los mismos aros y realizan la misma
manipulación, excepto con el último aro. (Ver sección
NOICULOS)
Podemos intentar definir un solo proceso,
ya que manipulan los mismos aros y siempre conmutan el estado que tenga.
Podemos denominarlo CUA, Conmutador Ultimo
Aro.
Este proceso realizará la SOLUCION,
si se parte de la Posición Inicial Extrema y NOISCULO si partimos
de la Posición Final, con todos los aros fuera.
Por otro lado a las manipulaciones básicas
de un sólo aro X, las denominaremos:
CONMUTAR ARO X
Veamos como definir el proceso unificado
CUA.
CUA (N)
Sí N=1 Entonces
En caso contrario
-
CUA ( N -1 )
-
CONMUTAR ARO N
-
CUA ( N -1 )
