Introducción a la Programación Dinámica - Nivel Avanzado

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

Desafíos 3 - Nivel Inicial

Acá van los desafíos del tercer encuentro. Son para practicar la estructura de repetición "for".

1.Mostrar en la pantalla los números del 1 al 100
2.Mostrar en la pantalla los números del 100 al 1 (en ese orden)
3.Mostrar en la pantalla los números del 100 al -100 en ese orden.
4.El usuario ingresa dos números a y b. Deben mostrar todos los números entre a y b inclusive.
5.Hallar la suma de todos los números entre 1 y 100 inclusive.
6.El usuario ingresa dos número a y b. Deben hallar el valor de la suma y de la multiplicación de todos los números entre a y b inclusive.
7.Calcular y mostrar en la pantalla las primeras 30 potencias de 2.



Pongan en comentarios sus programas con la solución a los desafíos!
Saludos!

Desafíos 2 - Nivel Inicial

A continuación, los desafíos correspondientes al segundo encuentro.
Temas: Entrada y Salida por pantalla, variables, estructura condicional ( if ), operadores (>, >=, ==, !=, etc)

1. Deben elegir un número. El usuario tiene que adivinarlo, ingresándolo . Si lo adivina, pongan que ganó. Si no, que perdió.
2. El usuario debe ingresar 2 números. Deben devolver cuál es el mayor.
3. El usuario debe ingresar 2 números. Deben devolver cuál es el mayor, y si son iguales, decir que son iguales.
4. El usuario debe ingresar 3 números y ustedes devolver cuál es el mayor de ellos.
5. El usuario debe ingresar 3 números y ustedes deben devolverlos ordenados (de menor a mayor o viceversa).
6. Hacer una calculadora!! Es decir, el usuario ingresa 3 numeros: los primeros 2 son los números a operar. El tercero es: 1 si quiere sumar, 2 para restar, 3 para multiplicar, 4 para dividir.
   Ej: 4 6 3 devuelve 4*6=24

Saludos a todos, y practiquen!

Desafíos 1 - Nivel Inicial

Como prometí, voy a ir subiendo al blog un resumen de lo que vemos en los encuentros, y desafíos para que puedan practicar lo que vamos viendo.

Por ahora, les dejo los desafíos. Pronto vendrán los resumenes.

Desafíos correspondientes al primer encuentro:
Temas: Entrada y Salida por pantalla, variables (sobre todo enteros)

1. El usuario debe ingresar por pantalla un número, y el programa debe devolver ese mismo número.
2. El usuario debe ingresar por pantalla un número, y el programa debe devolver el siguiente.
3. El usuario debe ingresar por pantalla dos números, y el programa debe devolver su suma.
4. El usuario debe ingresar por pantalla dos números, y el programa debe devolver su cociente (resultado de la división). ¿Siempre devuelve el resultado correcto? Encuentren algunos ejemplos donde no lo haga, y traten de explicar por qué.

Posteen en comentarios sus soluciones!
Saludos a todos, y practiquen!