Download Por ejemplo

Programación 2
Curso 2011/2012
Primera práctica
Primera parte: representaciones binarias (6 puntos)
La primera parte de la práctica consistirá en el diseño e implementación de un
conjunto de funciones para transformar números en su representación binaria en
forma de vector de bits.
Como alguna de las funciones las diseñaremos e implementaremos de forma
recursiva, os recuerdo unas cuantas reglas que os pueden ayudar de cara a
solucionar los problemas:
 n = 2 * (n div 2) + n mod 2
 n mod 2 = valor del bit menos significativo de la representación binaria de
n
o 5 = 101 y 5 mod 2 = 1
o 6 = 110 y 6 mod 2 = 0
 Si multiplico por 2 un número, desplazo una posición a la izquierda su
representación binaria y añado un 0 como bit menos significativo
o 5 = 101 y 5*2=10=1010
 Por tanto la representación binaria de n es la misma que la de (n div 2) si
desplazamos a ésta una posición hacia la izquierda y le añadimos al final un
bit de valor (n mod 2)
o 10 = 101 0, que es 101 seguido de 0, dónde 101 = 5 = (10 div 2) y 0 =
(10 mod 2)
 La representación en binario de un número n (positivo) necesita tantos bits
como el logaritmo en base 2 de ese número+1 (redondeado por exceso)
o Con b bits puedo representar números desde 0 a 2^b-1, por lo que el
n <= 2^b-1 => log (n+1) <= b
o Por ejemplo, para 10 necesito como mínimo log11=3.46=4
o Para el caso especial 0, usaremos un bit
 Para representar números negativos se utiliza complemento a 2
o Los números positivos quedan igual pero se añade un bit (en la
posición de mayor peso) con valor 0
 Por ejemplo, 10=1010 para a ser 01010
o Los números negativos se transforman de la siguiente manera: se
cambian los 1s por 0s y los 0s por 1s (complemento a 1) y se suma 1
al resultado
 Por tanto, para obtener -10, obtenemos primero 10=01010,
hacemos el complemento a 1, es decir, 10101 y sumamos uno
al resultado, por lo que queda 10110
Hasta aquí todo es repaso, muy condensado, de cosas sobradamente conocidas.
Funciones sobre números naturales (3 puntos)
Inicialmente solamente consideraremos números naturales (es decir, enteros
positivos o cero).
Para representar los bits correspondientes a un número usaremos un vector de
enteros de manera que el bit menos significativo esté en la posición 0 del vector. La
J.M. Gimeno y J.L. González
1
Programación 2
Curso 2011/2012
longitud del vector coincidirá exactamente con el número de bits necesarios para
representar el número.
Por ejemplo, el número 10 vendría representado por el vector {0, 1, 0, 1} (fijaos en
que el orden es el inverso de cómo lo escribiríamos).
Las funciones a realizar serán:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int numBitsForNat(int nat) {
// Entrada: nat >= 0
// Salida: mínimo número de bits necesarios para
//
representar nat en binario como número
//
natural.
// Ejemplos: numBitsForNat(0) == 1
//
numBitsForNat(1) == 1
//
numBitsForNat(10) == 4
}
public int bitsToNat(int[] bits) {
// Entrada: vector de bits (solamente 0s y 1s) que
//
representan un número natural en binario.
//
El bit de menor peso está en la posición
//
0 del vector.
// Salida: el natural que representa el vector de bits
// Ejemplos: bitsToNat({0,1}) == 2
//
bitsToNat({0,1,1}) == 6
//
bitsToNat({1,1,0}) == 3
}
public int[] natToBits(int nat) {
// Entrada: nat >= 0
// Salida: un vector (de tamaño igual al
//
de bits necesario) que contiene
//
representación binaria de nat y
//
bit menos significativo está en
// Ejemplos: natToBits(0) == {0}
//
natToBits(6) == {0,1,1}
//
natToBits(3) == {1,1}
}
mínimo número
la
en la que el
la posición 0
NOTA: Los ejemplos en los que se pasa directamente un vector de enteros no
representan código válido en Java.
Funciones para números enteros (3 puntos)
La representación de un número entero usará un bit adicional (que indicará el
signo) y la estrategia de complemento-a-2 para los números negativos. Por
ejemplo, el número 10 será el vector {0, 1, 0, 1, 0} y -10 será {0, 1, 1, 0, 1}.
Para ello se usarán las funciones:
1 public int numBitsForInt(int num) {
2 // Entrada: num
J.M. Gimeno y J.L. González
2
Programación 2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Curso 2011/2012
// Salida: mínimo número de bits necesarios para
//
representar num en binario como número
//
entero.
// Ejemplos: numBitsForInt(0) == 1
//
numBitsForInt(1) == 2
//
numBitsForNat(10) == 5
}
public int bitsToInt(int[] bits) {
// Entrada: vector de bits (solamente 0s y 1s) que
//
representan un número entero en binario
//
usando complemento a 2.
//
El bit de menor peso está en la posición
//
0 del vector.
// Salida: el entero que representa el vector de bits
// Ejemplos: bitsToInt({0}) == 0
//
bitsToInt({0,1,1}) == -2
//
bitsToNat({1,1,0}) == 3
}
public int[] intToBits(int num) {
// Entrada: num
// Salida: un vector (de tamaño igual al mínimo número
//
de bits necesario) que contiene la
//
representación binaria de num usando
//
complemento-a-2 y en la que el bit menos
//
significativo está en la posición 0
// Ejemplos: natToBits(0) == {0}
//
natToBits(6) == {0,1,1,0}
//
natToBits(-3) == {1,0,1}
}
NOTA: En realidad no todos los vectores de bits que podemos pasar a la
función corresponden a representaciones válidas según la hemos definido.
Por ejemplo, {1} es imposible como representación. No hace falta que
comprobéis eso, por lo que en este caso la función puede aplicar el
procedimiento normal (que da un resultado extraño en este caso).
Uno de los objetivos de la práctica es trabajar sobre la manipulación de vectores en
Java y en la combinación de funciones. Es por ello que intentaremos aprovechar las
funciones que tenemos para trabajar sobre naturales para implementar las que
trabajan sobre enteros.
Para ello diseñaremos las siguientes funciones auxiliares:
1 public void copyInto(int[] from, int[] to) {
2 // Entrada: from.length <= to.length
3 // Salida: para las posiciones de to que coinciden
4 //
con las de from, to[i] == from[i]; para las
5 //
restantes to[i] == 0
6 // Ejemplo: int[] src = {0,1,1}, dst = {1,1,0,1,0};
7 //
copyInto(src, dst);
J.M. Gimeno y J.L. González
3
Programación 2
Curso 2011/2012
8 //
// Ahora dst == {0,1,1,0,0}
9}
10
11 public void twosComplement(int[] bits) {
12 // Entrada: vector de bits
13 // Salida: aplica la transformación complemento-a-2
14 //
sobre el vector de bits
15 // Ejemplo: int[] is10 = {0,1,0,1,0}
16 //
twosComplement(is10)
17 //
// Ahora is10 == {0,1,1,0,1}
18 }
19
20 public void onesComplement(int[] bits) {
21 // Entrada: vector de bits
22 // Salida: se ha invertido (0->1, 1->0) el valor de
23 //
todas las posiciones del vector bits.
24 // Ejemplo: int[] is10 = {0,1,0,1,0}
25 //
onesComplement(is10);
26 //
// Ahora is10 == {1,0,1,0,1}
27 }
28
29 public void addOne(int[] bits) {
30 // Entrada:
31 // Salida: suma 1 a la representación binaria que
32 //
representa el vector. Tened en cuenta que
33 //
puede pasar que el acarreo de la última
34 //
posición se pierda (ya que el resultado
35 //
ha de quedar en el mismo vector).
36 // Ejemplo: int[] randomBits = {1,1,0,1,0};
37 //
addOne(randomBits)
38 //
// Ahora randomBits = {0,0,1,1,0}
39 }
Tal y como puede observarse en los ejemplos, todas estas funciones auxiliares
trabajan modificando el contenido del vector que se les pasa como parámetro
(recordad que en Java los vectores se pasan por referencia, por lo que si los
modificamos dentro de una función, al salir de ella, el vector se ha modificado; es
decir, se comportan como parámetros de entrada-salida).
Restricciones adicionales sobre la solución
 La función numBitsForNat se ha de diseñar de forma recursiva.
 La función bitsToNat ha de implementarse recursivamente usando una
función auxiliar que utilice un índice para marcar el subvector de bits del
que estáis calculando el valor como número natural.
J.M. Gimeno y J.L. González
4
Programación 2
Curso 2011/2012
Segunda parte: cálculo del determinante (4 puntos)
Este segundo problema consistirá en el diseño e implementación de una función
recursiva para calcular el determinante de cualquier matriz cuadrada. Ejemplos de
cálculo de determinante para varias matrices serían:
 Matrices 1x1:
|4| = 4
 Matrices 2x2:
1 2
|
| = 1 ∗ 4 − 3 ∗ 2 = −2
3 4
 Matrices 3x3:
1 2 3
1∗5∗9+2∗6∗7+3∗4∗8
| 4 5 6| =
=0
−3 ∗ 5 ∗ 7 − 2 ∗ 4 ∗ 9 − 1 ∗ 6 ∗ 8
7 8 9
Estos son casos particulares (y bien conocidos) de la manera de calcular el
determinante.
Una formulación recursiva (es decir, una formulación en la que el cálculo de un
determinante se puede expresar como una combinación de cálculos de
determinantes de matrices de menor tamaño) es el método de cálculo del
determinante por adjuntos.
Menores complementarios y adjuntos de una matriz cuadrada
El menor complementario 𝛼𝑖𝑗 de una matriz cuadrada 𝐴 de orden 𝑛, es el
determinante de la matriz de orden 𝑛 − 1 que resulta de eliminar la fila 𝑖 y la
columna 𝑗 de la matriz original.
Por ejemplo, dada
1 2 3
𝐴 = (4 5 6 )
7 8 9
tenemos que
5 6
𝛼11 = |
| = 5 ∗ 9 − 8 ∗ 6 = 45 − 48 = −3
8 9
2
𝛼21 = |
8
3
| = 2 ∗ 9 − 8 ∗ 3 = 18 − 24 = −6
9
2
𝛼31 = |
5
3
| = 2 ∗ 6 − 5 ∗ 3 = 12 − 15 = −3
6
De forma similar se definen los adjuntos 𝐴𝑖𝑗 como los menores complementarios
anteponiendo el signo + o – dependiendo de si la suma de los índices 𝑖 y 𝑗 es par o
impar.
Por ejemplo,
 𝐴11 = +𝛼11 = +(−3) = −3 (ya que la suma de 1+1=2 es par)
 𝐴21 = −𝛼21 = −(−6) = 6 (ya que la suma de 2+1=3 es impar)
 𝐴31 = +𝛼31 = +(−3) = −3 (ya que la suma 3+1=4 es par)
J.M. Gimeno y J.L. González
5
Programación 2
Curso 2011/2012
Desarrollo del determinante por adjuntos
El determinante de una matriz cuadrada de orden n es igual a la suma de los
productos de los elementos de una fila (o columna) por los adjuntos respectivos.
Por ejemplo, si desarrollamos por los adjuntos de la primera columna:
1 2 3
|4 5 6| = 1 ∗ 𝐴11 + 4 ∗ 𝐴21 + 7 ∗ 𝐴31 = (−3) + 4 ∗ 6 + 7 ∗ (−3) = 0
7 8 9
Fijaos en que, de esta manera, para calcular el determinante de una matriz de
orden 3, hemos tenido que calcular los determinantes (uno por cada adjunto) de 3
matrices de orden 2.
Pistas sobre el diseño e implementación
En la implementación definiremos, como mínimo, las funciones:
1 public int[][] removeRowCol(int[][] mat, int r, int c) {
2 // Entrada: mat una matriz cuadrada, r índice de una
3 //
fila y c el de una columna (recordad que
4 //
tanto filas como columnas se numeran desde 0)
5 // Salida: la matriz cuadrada resultante de eliminar
6 //
la fila r y la columna c de la matriz mat
7 // Ejemplo: int[][] m = {{1,2,3},{4,5,6},{7,8,9}}
8 //
int[][] m02 = removeRowCol(m,0,2)
9 //
// Ahora m02 == {{4,5},{7,8}}
10 }
Y luego la que calcula el determinante de la matriz:
1 public int determinant(int[][] mat) {
2 // Entrada: mat una matriz cuadrada
3 // Salida: valor del determinante de la matriz mat
4 // Ejemplo: int det = determinant({1,2},{3,4})
5 //
// Ahora det == -2
6}
Podéis suponer, dentro de las funciones que la matrices tienen los tamaños
correctos. Si queréis, podéis hacer funciones auxiliares para comprobarlo y usarlas
en el programa principal (función run) antes de llamar a la función determinante.
J.M. Gimeno y J.L. González
6
Programación 2
Curso 2011/2012
Instrucciones generales de la práctica





Las prácticas se han de realizar individualmente.
Cada parte de la práctica será un proyecto Netbeans.
La parte del programa principal (función run) no hace falta que pida datos
al usuario. Puede, perfectamente, usar números, vectores y matrices
prefijados (eso sí, de varios tamaños) para comprobar que vuestras
implementaciones funcionan.
La entrega ser realizará en el campus virtual (sakai) en la actividad
Primera práctica.
La entrega consistirá en un fichero .zip que contendrá:
o Los dos proyectos de Netbeans (para que ocupen menos, hacer un
limpiar del proyecto antes de comprimirlo).
o Un informe de 3 ó 4 páginas en el que expliquéis cómo habéis
diseñado las funciones recursivas y aquellos aspectos que más os ha
costado solucionar, los errores que habéis cometido (antes de
arreglarlos en la solución final), etc.
J.M. Gimeno y J.L. González
7