Ejercicios Semana 9: Ejercicios adicionales sobre recurrencia

Post date: Mar 18, 2013 4:25:03 PM

Para cada uno de los siguientes problemas, el estudiante debe plantear soluciones recurrentes.

1. Considere un conjunto S de números naturales. El conjunto S se llama perfectamente bi-particionable sii S puede ser particionado en dos subconjuntos S1 y S2 (es decir, la intersección de S1 y S2 es vacia y la unión de S1 y S2 es igual a S) tales que M = |S1| = |S2|, en donde M = |S|/2. Para cualquier conjunto de números naturales R, la expresión |R| denota la suma de los elementos en R. Escriba una fución que dado un conjunto S y la suma de sus elementos |S|, determine si S es perfectamente bi-particionable. Puede suponer que S es tal que |S| es par.
   • Por ejemplo, si S = {1,2,3} la respuesta debe ser afirmativa dado que |S| = 6 y S1 = {1,2} y S2 = {3} son tales que |S1| = 3 = |S2|. Al contrario, S = {1,2,3,8} no es perfectamente bi-particionable.
2. Considere un arreglo D[0,N) de números naturales, con N >= 1 que representa denominaciones de monedas; suponga que D[0] = 1, que D está ordenado ascendentemente, que no hay denominaciones repetidas en D y que de cada denominación hay una fuente inagotable de monedas. Defina una función que dado un número entero M >= 0, determine de cuántas formas se puede expresar M con monedas de denominaciones en D.
   • Por ejemplo, si D = [1,2,5] y M = 5, entonces hay 4 formas de expresar M con monedas de denominaciones en D:
     • 5 monedas de $1
     • 3 monedas de $1 y 1 moneda de $2
     • 1 moneda de $1 y 2 monedas de $2
     • 1 monedas de $5