ago 27 2007
Reto de programación: apretones de manos
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.
Interesante ejercicio, pena de no tener tiempo para pensar en él. Por cierto, quedaría muy bien para hacer defensa de Epaile ;)
Arky: claro que sí, cógelo como ejemplo para tu PFC :-) (y seguro que entre café y café podrás sacar un rato para pensar en él… y tirar del hilo, porque es de esos ejercicios que cuanto más sabes de él, más te queda por saber :-O
primera vez que posteo… jeje bonito ejercicio, pero te hace comerte el tarro cosa fina, llevo como dos horas dandole vueltas, casi lo tengo echo en PHP pero me falla algo…. y no me da el resultado jejeje, lo sacaré!!