El día de ayer vimos un problema clásico de programación dinámica, pero que tiene relación con otras técnicas:http://www.blogger.com/img/blank.gif
Máxima subsecuencia creciente
Explicación en Algorithmist
Explicación en Wikipedia
El problema consiste en, dada una secuencia de números, encontrar la subsecuencia más larga de números ordenados en forma creciente (no necesariamente consecutivos).
Ejemplo:
En la secuencia 3 1 4 5 2 17 8 11
La secuencia más larga es 3 4 5 8 11, con longitud 5.
Ayer vimos una solución sencilla que tarda o(n^2)
También vimos una solución que usa busqueda binaria, o trucos equivalentes, para reducir la complejidad a o(n*logn).
Si alguno se anima, puede dejar en los comentarios un programa que resuleva el problema!
Nico
Mostrando entradas con la etiqueta Problemas. Mostrar todas las entradas
Mostrando entradas con la etiqueta Problemas. Mostrar todas las entradas
jueves, 23 de junio de 2011
lunes, 6 de julio de 2009
Desafíos y Links
Acá abajo les dejos los primeros desafíos, y los links que nos van a ser útiles:
Problemas:
1) El usuario debe ingresar por entrada estandar (la que conocemos) dos numeros, y nuestro programa deberá decir si el primer número es divisible por el segundo. Además, el programa deberá devolver el resto de la división.
Ej1: Si 0, si la entrada fuera 12 y 4
Ej2: No 5, si la entrada fuera 16 y 11
2) El usuario debe ingresar por entrada estandar un número, y nuestro programa deberá devolver TODOS los divisores de ese número.
Ej: 1, 2, 3, 4, 6 y 12, si la entrada fuera 12
3)El usuario debe ingresar por entrada estandar un número, y nuestro programa debe decidir si ese número es primo o no.
Ej1: No es primo, si la entrada fuera 9
Ej2: Es primo, si la entrada fuera 7
4) El usuario debe ingresar por entrada estandar 3 números a, b y c, y nuestro programa debe decidir, en caso de que esas fueran las medidas de los lados de un triángulo, si tal triángulo podría existir o no en la realidad.
Ej1: Si, si las medidas fueran 3, 3 y 4
Ej2: No, si las medidas fuera 2, 6 y 10
Esos serían los primeros ejercicios. Para empezar a practicar con los problemas de verdad:
http://www.oma.org.ar/enunciados/index.htm#cym
http://www.oia.org.ar/problemas#categoria_programacion
Suerte a todos, escriban con sus ideas, dudas, códigos o lo que se les ocurra.
Saludos,
Nico
Problemas:
1) El usuario debe ingresar por entrada estandar (la que conocemos) dos numeros, y nuestro programa deberá decir si el primer número es divisible por el segundo. Además, el programa deberá devolver el resto de la división.
Ej1: Si 0, si la entrada fuera 12 y 4
Ej2: No 5, si la entrada fuera 16 y 11
2) El usuario debe ingresar por entrada estandar un número, y nuestro programa deberá devolver TODOS los divisores de ese número.
Ej: 1, 2, 3, 4, 6 y 12, si la entrada fuera 12
3)El usuario debe ingresar por entrada estandar un número, y nuestro programa debe decidir si ese número es primo o no.
Ej1: No es primo, si la entrada fuera 9
Ej2: Es primo, si la entrada fuera 7
4) El usuario debe ingresar por entrada estandar 3 números a, b y c, y nuestro programa debe decidir, en caso de que esas fueran las medidas de los lados de un triángulo, si tal triángulo podría existir o no en la realidad.
Ej1: Si, si las medidas fueran 3, 3 y 4
Ej2: No, si las medidas fuera 2, 6 y 10
Esos serían los primeros ejercicios. Para empezar a practicar con los problemas de verdad:
http://www.oma.org.ar/enunciados/index.htm#cym
http://www.oia.org.ar/problemas#categoria_programacion
Suerte a todos, escriban con sus ideas, dudas, códigos o lo que se les ocurra.
Saludos,
Nico
Suscribirse a:
Entradas (Atom)
