Ikasten.IO
Learning, Aprendiendo

Reto de programación: apretones de manos 27 agosto, 2007

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.

  • Arky dice:

    Interesante ejercicio, pena de no tener tiempo para pensar en él. Por cierto, quedaría muy bien para hacer defensa de Epaile 😉

  • admin dice:

    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

  • Neiru dice:

    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 *