Coco estaba tibio con la respuesta, pero parte de la respuesta es explicar de una manera concreta como solucionarlo y como estaba muy cerca, les regalo la solución:
La clave para resolver este problema es "recursión", veamos porque:
Vamos a generar una tabla de números para observar el patrón de generación:
1 A
2 B
3 AA
4 BA
5 AB
6 BB
7 AAA
8 BAA
9 ABA
10 BBA
11 AAB
12 BAB
13 ABB
14 BBB
15 AAAA
16 BAAA
17 ABAA
18 BBAA
19 AABA
.
.
.
Ok, lo primero que notamos es que hay un patrón y está clarísimo.
Lo primero más obvio es notar que cuando un número es par, empieza en B, y cuando es impar empieza en A.
Lo que quizás tome un poco más de tiempo descubrir es que un patrón viejo se repite agregándole una A o una B segun sea par o impar, observemos el patrón generado por ejemplo por el número 4 = BA, ahora miremos el patrón del número 9 = ABA y ahora el del número 19 = AABA.
Si queremos resolver el patrón para el 19 (AABA), primero ponemos una "A" (porque es impar) y luego ponemos a continuación el patrón del 9 (ABA), para resolver el patrón del 9 (ABA) ponemos una "A" (porque es impar) y ponemos a continuación el patrón del 4 (BA). Para resolver el patrón del 4 (BA) ponemos una "B" (porque es par) y luego ponemos el patrón del 1 (A). Y ya sabemos resolver el patrón del 1 a ojos cerrados.
Es decir, para el patrón de cualquier número, primero debemos resolver patrones de números anteriores, y luego concatenarlos hasta llegar al caso base. Para este algoritmo el caso base (a ojos cerrados) es cuando es 1 = A y 2 = B.
Por lo tanto necesitamos una función que se llame a sí misma (recursiva) para que calcule los valores pasados, hasta que sea tan obvio de calcular que tire la respuesta inmediata (caso base).
Pero como saber que numero le corresponde calcular previamente para resolver por ejemplo 19?
Aqui otra vez pensamos si hay alguna relación:
En el ejemplo anterior:
Para calcular el 19, necesitamos el 9. (19=AABA y 9=ABA)
Para calcular el 9, necesitamos el 4. (9=ABA y 4=BA)
Y por ejemplo para calcular el 17 necesitamos el 8. (17=ABAA y 8=BAA)
Entonces la relación es (n-1)/2
Nótese que esto funciona para los números impares... y para los pares? veamos la tabla y observamos que:
Para calcular el 8, necesitamos el 3. (8=BAA y 3=AA)
Para calcular el 10, necesitamos el 4. (10=BBA y 4=BA)
Para calcular el 16, necesitamos el 7. (16=BAAA y 7=AAA)
Entonces la relación es (n-2)/2
Ok entonces ya tenemos un algoritmo, pero como hacemos la función recursiva? De la siguiente manera:
A tener en cuenta:
* El caso base: cuando n =1 o n =2 vale A y B respectivamente
* Si n es impar, calcula primero el valor de (n-1)/2 y luego concaténalo con "A".
* Si n es par, calcula primero el valor de (n-2)/2 y luego concaténalo con "B".
El pseudocódigo:
Funcion calcula(entero n)
inicio_funcion
si (n = 1) retorna "A"
si (n = 2) retorna "B"
si (n>=3)
si (n es impar)
retorna "A" concatenado con calcula((n-1)/2)
si (n es par)
retorna "B" concatenado con calcula((n-2)/2)
fin_funcion
