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:

HandsShaking_4_correct/tmp/HandsShaking_4_correct_2.GIF/tmp/HandsShaking_4_wrong.GIF

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.

3 comentarios sobre “Reto de programación: apretones de manos”

  1. 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

  2. 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é!!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.