Tarea #3 [solución]

Generador de Tajadeadores

{ // [0] [1] [2] [3] [4] [5] int V[] = { 0 , 1 , 2 , 3 , 4 }; int *it = &V[0]; // it = V+0; int *itEND = &V[5]; // itEND = V+dim(V) for ( it = &V[0]; it != itEND ; ++it ) { std::cout << (*it); } }

      Para aplicarle alguna acción a todos los elementos de un contenedor lo usual es usar iterador C++, que son punteros inteligentes implementados como clases amigas del contenedor. Sin embargo, esta forma de iteración no es la más antigua, pues previamente habían sido usado los generadores para el lenguaje Alphard:

Shaw, Mary & Wulf, William A.:

Abstraction and Verification in Alphard: Defining and Specifying Iteration and Generators, Communications of the ACM, Vol.20, No.8, Aug 1977.

      Los iteradores Java funcionan diferente pues todos respetan la interfaz java.util.Iterator en la que están definidas las 3 operaciones de cualquier iterador { next() , hasNext() , remove() }.

class Random { unsigned m_qty; ///< #. unsigned m_last; ///< Max. long m_val; ///< current(). public: Random( int n=1 , long seed=3145159 ) : m_qty(0), m_last(n) { srand(seed); } bool hasNext() const { return m_qty < m_last; } const long& next() { m_qty++; return (m_val = rand()) ; } };

void generateRandom( ) { Random iter( 15, 271828 ); while ( iter.hasNext() ) { std::cout << iter.next() << std::endl; } }

      Aquí se muestra lo sencillo que es encapsular un generador de números aleatorios en un iterador Java. Cada ves que se ejecuta el ciclo se debe a que hasNext() es verdadero, cuyo valor cambia debido a la ejecución de next() (a menos que desde el principio ya hasNext() fuera falso, lo que ocurriría si se inicializa el generador con el valor n=0).

      En la tarea anterior usted implementó 6 operaciones que permiten sacarle tajadas a una matriz. Si se trabaja con matrices cuadradas grandes, de dimensiones de cientos o de miles de columnas, es concebible construir la clase itrHadamard que sirva para generar todas las formas en que es posible sacarle tajadas a la matriz original de tamaño NxN para obtener otra de tamaño (N-4)x(N-4), que tiene 4 columnas y 4 filas menos, lo que se logra sacándole tajadas para eliminarle 4 columnas y 4 filas a la matriz original.

12,354 → No.Sec colDel_sliceFromCol( 7 , M[8x8] , M[8x7] ) colDel ( 3 , M[8x7] , M[8x6] ) rowDel_sliceFromRow( 5 , M[8x6] , M[7x6] ) colDel_sliceFromCol( 2 , M[7x6] , M[7x5] ) rowDel_sliceFromCol( 0 , M[7x5] , M[6x5] ) colDel_sliceFromRow( 4 , M[6x5] , M[6x4] ) rowDel_sliceFromRow( 5 , M[6x4] , M[5x4] ) rowDel ( 1 , M[5x4] , M[4x4] ) M[8x8]→cc(7)→c(3)→rr(5)→cc(2)→rc(0)→cr(4)rr(5)→r(1)→M[4x4]

      A primera vista pareciera que es necesario usar matrices para implementar su generador, pero en realidad eso no hace falta. Basta que su generador produzca la secuencia de invocaciones, como se muestra aquí. Note que hay 2 formas de presentar cada iteración: la primera es mucho más clara, pues en cada renglón se indica qué operación hay que aplicar, mientras que la segunda es una forma muy resumida, en la que se usan abreviaturas como "rc" para "rowDel_sliceFromCol()", por ejemplo. Su programa debe leer un número que es la dimensión y un segundo parámetro opcional que indique que se debe grabar la versión completa en lugar de la abreviada.

C:\DIR\SubDir> itrHadamard 8
...
M[8x8]->cc(7)->c(3)->rr(5)->cc(2)->rc(0)->cr(4)rr(5)->r(1)->M[4x4]
M[8x8]->cc(7)->c(3)->rr(5)->cc(2)->rc(0)->cr(4)rr(5)->r(2)->M[4x4]
M[8x8]->cc(7)->c(3)->rr(5)->cc(2)->rc(0)->cr(4)rr(5)->r(3)->M[4x4]
M[8x8]->cc(7)->c(3)->rr(5)->cc(2)->rc(0)->cr(4)rr(5)->r(4)->M[4x4]
....

C:\DIR\SubDir> itrHadamard 8 -x
....
colDel_sliceFromCol( 7 , M[8x8] , M[8x7] )
colDel             ( 3 , M[8x7] , M[8x6] )
rowDel_sliceFromRow( 5 , M[8x6] , M[7x6] )
colDel_sliceFromCol( 2 , M[7x6] , M[7x5] )
rowDel_sliceFromCol( 0 , M[7x5] , M[6x5] )
colDel_sliceFromRow( 4 , M[6x5] , M[6x4] )
rowDel_sliceFromRow( 5 , M[6x4] , M[5x4] )
rowDel             ( 1 , M[5x4] , M[4x4] )
....

Consulta:

Profe, cuando uno hace el programa que crea la forma en la que se va a cortar la matriz, ¿desde dónde empieza el número de columna o fila a eliminar? ¿Debo empezar al azar? Además, al generar los formas posibles de cortar las tajadas, ¿hay que repetir los métodos para cortar una columna/fila?

Respuesta:

Al declarar la clase itrHadamard es necesario definir cuáles son las operaciones de sacar tajadas que se van a usar:

enum { FIRST=0,
       colDel=FIRST,        rowDel,
       colDel_sliceFromRow, rowDel_sliceFromRow,
       colDel_sliceFromCol, rowDel_sliceFromCol,
       LAST
};
enum {
       c=colDel,               r=rowDel,
       cr=colDel_sliceFromRow, rr=rowDel_sliceFromRow,
       cc=colDel_sliceFromCol, rc=rowDel_sliceFromCol,
};

      Esta declaración también sirve para definir un orden entre las operaciones de tajadeo. Por ejemplo, el colDel() viene de primero y el rowDel_sliceFromCol() queda de último. Además, se aplica la operación antes a la fila 0 que a la 1, etc. Por eso, el orden no es antojadizo, sino que corresponde al orden definido al declarar los tipos de tajadas que se pueden extraer de la matriz. Su programa debe respetar este orden, pero también es conveniente que sea posible definir desde dónde comenzar la iteración:

{
    itrHadamard itr;
    itr.setDim( 1000 );  // Dimensión de la matriz: [1,000 x 1,000]
    itr.setMax( 12000 ); // Cantidad máxima de iteraciones
    // Establece desde dónde se comienza a generar las tajadas
    itr.setOp( itrHadamard::colDel_sliceFromRow, 12 );
    while ( itr.hasNext() ) {
        itr.next(); // avanza
        for ( int i=0; iif ( itr.delRow() ) {
                cout << itr.vec(i).nRow();
            }
            else {
                cout << itr.vec(i).nCol();
            }
            cout << endl;
            }
        }
    }
}

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

Entrega de Tareas

Tiempo de entrega:	1 semana
Modalidad:	En parejas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2011
Derechos de autor reservados © 2011