Hace poco he participado en una prueba más de TopCoder.com, un excelente sitio para mantener engrasados los conocimientos de estructuras de datos, algoritmos, análisis y diseño de sistemas y programación general. Una de las pruebas me dejó varado y no pude completar a tiempo el ejercicio. Posteriormente he leído bastante al respecto y profundizado en la serie de los números de Catalan, en la que se basa la solución al problema. Sin más, os dejo con el enunciado, a ver si conseguís solucionarlo 😉
Consideremos una reunión de n personas alrededor de una mesa circular. Antes de comenzar la reunión, se dan la mano unos a otros. Cada persona estrecha la mano de otra persona en un momento dado (y sólo de una). Los apretones de manos se dan todos a la vez (es decir, en un momento dado, cada persona está estrechando la mano de otra) Decimos que un apretón de manos es perfecto si no hay brazos que se crucen entre sí en el momento del apretón. Dado un entero n, devolver el número de apretones de manos perfectos posibles que existen para n personas sentadas a la mesa.
Ejemplo:
si n = 4 personas, los posibles apretones de mano son:
Las primeras dos figuras muestran apretones de manos perfectos. La 3ª no es un apretón de manos perfecto. La solución para n=4 por tanto es 2. Para n=8 sería 14.