Tarea 5 de Diseño de Algoritmos
Trimestre 2012 Primavera
Entrega: 11 de junio de 2012 a las 22:00.
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++) 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. Puede
suponer que 0 <= B <= M <= 32.
Ejemplo de entrada
|
Ejemplo de salida
|
4 2
|
3
|
Notas: Sus programas no
deben
leer ni escribir nada adicional a lo que se indica en el
enunciado. El
tiempo de ejecución de sus algoritmos será considerado
como parte de la evaluación.