Clase 16 de Marzo 2013
Se les comunica que los proximos dos fines de semana no habra clase, entonces nuestra proxima clase seria el sabado 7 de abril, de todos modos yo voy a estar contestando correos, aquellos que tengas dudas de los problemas de tareas no duden en escribirme a rodrigo.burgos@gmail.com
Les coloco los codigos que hicimos en clase:
Permutaciones
Como sacar todas las permutaciones de una cadena donde todos los elementos son diferernte:
# include <stdio.h>
# include <string.h>
char cad[100], path[100];
char mark[100];
void backtrack( int level ){
int x;
if( level == strlen( cad )){
cad[ level ] = '\0';
printf("%s\n", path);
}
for( x = 0; x < strlen( cad ); x++)
if( mark[x] == 0 ){
mark[x] = 1;
path[ level ] = cad[x];
path[ level + 1] = '\0';
backtrack( level + 1);
mark[x] = 0;
}
}
main(){
while( scanf("%s", cad) != EOF ){
memset( mark, 0, sizeof( mark ));
backtrack( 0 );
}
return 0;
}
Búsqueda Binaria.
la función busbiniter es la forma iterativa de la búsqueda binaria, también tenemos la función busbinrec que es la función recursiva.
# include <stdio.h>
# include <string.h>
int n;
int list[100000];
int busbiniter( int inf, int sup, int val ){
int med;
while( inf <= sup ){
med = (inf + sup ) / 2;
if( list[ med ] == val ) return med;
if( list[med] < val ) inf = med + 1;
else sup = med - 1;
}
return -1;
}
int busbinrec( int inf, int sup, int val ){
int med = ( inf + sup ) / 2;
if( inf > sup ) return -1;
if( list[ med ] == val ) return med;
if( list[med] < val ) return busbinrec( med + 1, sup, val);
return busbinrec( inf, med - 1, val);
}
main(){
int x, val;
n = 0;
for( x = 0 ; x <= 100000; x+= 3) list[n++] = x;
while( scanf("%d", &val) != EOF ){
printf("%d\n", busbiniter( 0, n - 1, val ) ) ;
}
return 0;
}
Tour del caballo
Este código resuelve el problema que vimos en clase, dado el un tablero de ajedrez de N x N, y la posición inicial del caballo encontrar un camino donde el caballo visite todos los cuadros del tablero.
# include <stdio.h>
# include <string.h>
int board[100][100];
int dr[8] = {2,2,-2,-2,-1,-1,1,1};
int dc[8] = {1,-1,1,-1,2,-2,2,-2};
int n;
int backtrack(int level, int r, int c){
int dir, x, y, res = 0;
if( level == n * n + 1 ){
for( x = 0; x < n; x++){
for( y = 0; y < n; y++) printf("%3d", board[x][y]);
printf("\n");
}
printf("---\n");
return 1;
}
if( r < 0 || r >= n || c < 0 || c >= n ) return 0;
if( board[r][c] != 0 ) return 0;
board[r][c] = level;
for( dir = 0; dir < 8; dir++)
res += backtrack(level + 1, r + dr[ dir ] , c + dc[ dir ] );
board[r][c] = 0;
return res;
}
main(){
int posr, posc;
int r;
while( scanf("%d %d %d", &n, &posr, &posc) != EOF ){
memset(board, 0, sizeof( board ));
r = backtrack(1, posr, posc);
printf("%d\n", r);
}
return 0;
}
Problema del Sudoku
El siguiente programa resuelve el problema del sudoku, como vismo en clase es muy util utilizar el bactraking y para evitar crecer mucho el codigo utilizamos la tecnica de hash, con la filas, columnas y los cuadrantes.
# include <stdio.h>
# include <string.h>
int hashRow[10][10];
int hashCol[10][10];
int hashCua[10][10];
int numcuad[10][10];
char sudoku[10][10];
int print(){
int x, y;
for( x = 0; x < 9; x++){
for( y = 0; y < 9; y++) printf("%c", sudoku[x][y]);
printf("\n");
}
printf("---\n");
}
int backtrack( int row, int col ){
int dig, x;
if( row == 10 ){
print();
return 1;
}
if( col == 10 ) return backtrack( row + 1, 1 );
if( sudoku[row-1][col-1] != '_') return backtrack( row , col + 1);
for( dig = 1 ; dig <= 9; dig++){
if( hashRow[ row ][ dig ] == 1 ) continue;
if( hashCol[ col ][ dig ] == 1 ) continue;
if( hashCua[ numcuad[row -1][col -1 ] ][ dig ] == 1 ) continue;
hashRow[ row ][ dig ] = 1;
hashCol[ col ][ dig ] = 1;
hashCua[ numcuad[row -1][col -1 ] ][ dig ]= 1;
sudoku[row-1][col-1] = '0' + dig;
if( backtrack( row, col + 1) ) return 1;
hashRow[ row ][ dig ] = 0;
hashCol[ col ][ dig ] = 0;
hashCua[ numcuad[row -1][col -1 ] ][ dig ]= 0;
sudoku[row-1][col-1] = '_';
}
return 0;
}
main(){
int x, y, ncases, cases, row, col;
for(x = 0; x < 9; x++)
for( y = 0; y< 9; y++){
numcuad[x ][ y ] = ( ((x / 3) ) * 3 + (y / 3) ) + 1;
}
for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++ ){
memset( hashRow, 0, sizeof( hashRow));
memset( hashCol, 0, sizeof( hashCol));
memset( hashCua, 0, sizeof( hashCua));
for(row = 0; row < 9;row++){
scanf("%s", sudoku[row]);
for( col = 0; col < 9; col++)
if( sudoku[row][col] != '_'){
hashRow[ row + 1 ][ sudoku[row][col] - '0'] = 1;
hashCol[ col + 1 ][ sudoku[row][col] - '0'] = 1;
hashCua[ numcuad[row][col] ][ sudoku[row][col] - '0'] = 1;
}
}
backtrack( 1, 1 );
}
return 0;
}
Problemas:
Backtracking
http://uva.onlinejudge.org/external/1/167.html (Problema de las 8 reinas, utilizen la tecnica de hash, sobre fila, columna y diagonales, pueden poner una matriz como hicimos en el problema del sudoku para saber que diagonal le corresponde, recuerden que son dos tipos de diagonales).
http://uva.onlinejudge.org/external/5/524.html ( Problema de bactracking y primos , ya estan listos para estos problemas ).
http://uva.onlinejudge.org/external/5/574.html (Pueden ordenar los elementos para hacer una poda eficiente al bactrackign).
http://uva.onlinejudge.org/external/6/624.html
http://uva.onlinejudge.org/external/6/628.html
http://uva.onlinejudge.org/external/105/10582.html
http://uva.onlinejudge.org/external/6/677.html ( revisen la primera clase y el probleam del The lord of the ring, para ver como crear una matriz de adyacencia, en la siguiente clase veremos grafos, pero con lo que saben pueden resolver este problema).
http://uva.onlinejudge.org/external/7/750.html (Otro problema de las 8 reinas).
http://uva.onlinejudge.org/external/103/10344.html
http://uva.onlinejudge.org/external/8/868.html (aun que se puede hacer un algoritmo mas rapido con memorizacion es buena practica para un backtraking.)
http://uva.onlinejudge.org/external/103/10309.html (recursividad con memorizacion, notar que todas son de 10 x 10 , por tanto solo hay 10 1’s o 0’s , ¿eso no les recuerda a los bits ?.)
Binary Search:
http://uva.onlinejudge.org/external/106/10611.html
http://uva.onlinejudge.org/external/107/10742.html
http://uva.onlinejudge.org/external/110/11057.html
http://uva.onlinejudge.org/external/118/11876.html
Suerte, y recuerden que pueden resolver problemas aun que no esten en la lista.
Saludos.
Algoritmos y Demas 