Tarea 3 de Diseño de Algoritmos
Trimestre 2007 Primavera
Entrega: 31 de mayo de 2007 a las 22:00.
Problema
1: Sean M y B dos enteros no negativos. Diseñe un
algoritmo de búsqueda con retroceso que encuentre todas las
cadenas de M bits que tiene exactamente B bits iguales a 1 y no hay dos
de ellos consecutivos. Por ejemplo, si M = 4 y B = 2 entonces hay 3
cadenas que son 1010, 1001 y 0101. Escriba un programa en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado bitunoZZ (donde ZZ es una clave de dos
dígitos asignada por el profesor) basado en su algoritmo
que acepte como entrada dos enteros M y B y que escriba como salida la
cantidad de cadenas de M bits que cumplen la propiedad descrita. De
nuevo, si la entrada
fuera 4 2
entonces la salida debe ser 3.
Puede suponer que 0 <= B <= M <= 32.
Problema 2: Sea N un entero
positivo. Una permutación
P del 1 al N es un arreglo P[1], P[2], ..., P[N] que contiene cada
entero del 1 al N exactamente una vez. Un punto fijo de una
permutación P del 1 al N es un entero I tal que P[I] = I.
Diseñe un algoritmo de búsqueda con retroceso que
encuentre todas las permutaciones del 1 al N que no tienen puntos fijos. Por ejemplo,
si N = 4 entonces hay 9 permutaciones sin puntos fijos que son [2, 1,
4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4,
2, 1], [4, 1, 2, 3], [4, 3, 1, 2] y [4, 3, 2, 1]. Escriba
un programa en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado nofijoZZ
(donde ZZ es una clave de
dos dígitos asignada por el profesor) basado en su algoritmo que
acepte como entrada un entero N y que
escriba como salida la cantidad de permutaciones del 1 al N sin puntos
fijos. De nuevo, si la entrada
fuera 4
entonces la salida debe ser 9.
Puede suponer que 0 < N < 32.
Nota: Sus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado.