Blog

3.1 Proposiciones y bloques
3.2 If-else
3.3 Else-if

Ejercicio 3-1

int binsearch(int x, int v[], int n)
{
	int low, high, mid;

	low = 0;
	hight = n-1;
	while(low <= high) {
		mid = (low + high) / 2;
		if(x < v[mid])
			high = mid-1;
		else if (x > v[mid])
			low = mid + 1;
		else /* el elemento fue encontrado */
			return mid;
	}
	return -1; /* no se encontró */
}

#include 
#include 
#include 

long int binsearch_original(long int x, long int v[], long int n);
long int binsearch_reescrita(long int x, long int v[], long int n);

int main()
{
    long int n = 500000; /* tamaño del array */
    long int v[n];
    long int i, x;
    clock_t t1, t2;
    double tiempo_original, tiempo_reescrita;
    
    /* Generar un array ordenado de números enteros */
    for(i = 0; i < n; i++)
        v[i] = i;
            
    /* Buscar un número aleatorio en el array */
    srand(time(NULL));
    x = rand() % n;
    
    /* Medir el tiempo de ejecución de la función original */
    t1 = clock();
    for(i = 0; i < 1000; i++)
        binsearch_original(x, v, n);
    t2 = clock();
    tiempo_original = (double)(t2 - t1) / CLOCKS_PER_SEC / 1000.0;
    
    /* Medir el tiempo de ejecución de la función reescrita */
    t1 = clock();
    for(i = 0; i < 1000; i++)
        binsearch_reescrita(x, v, n);
    t2 = clock();
    tiempo_reescrita = (double)(t2 - t1) / CLOCKS_PER_SEC / 1000.0;
    
    printf("Tiempo de ejecución de la función original: %f segundos\n", tiempo_original);
    printf("Tiempo de ejecución de la función reescrita: %f segundos\n", tiempo_reescrita);
    
    return 0;
}

long int binsearch_original(long int x, long int v[], long int n)
{
    long int low, high, mid;
    low = 0;
    high = n-1;
    while(low <= high) {
        for(int j = 0; j < 100000; j++)
            ;
        mid = (low + high) / 2;
        if(x < v[mid])
            high = mid-1;
        else if (x > v[mid])
            low = mid + 1;
        else /* el elemento fue encontrado */
            return mid;
    }
    return -1; /* no se encontró */
}

long int binsearch_reescrita(long int x, long int v[], long int n)
{
    long int low, high, mid;
    low = 0;
    high = n-1;
    while(low <= high) {
        for(int j = 0; j < 100000; j++)
            ;
        mid = (low + high) / 2;
        if(x == v[mid])
            return mid;
        else if(x < v[mid])
            high = mid-1;
        else
            low = mid + 1;
    }
    return -1; /* no se encontró */
}

La función binsearch realiza dos pruebas dentro del ciclo while, una para verificar si x es menor que el elemento medio del array v, y otra para verificar si x es mayor que el elemento medio de v. Podemos reescribir la función para que sólo realice una prueba y comprobar si x es igual al elemento medio de v. Para ello, podemos cambiar el else-if por un else.

Para medir la diferencia de tiempo entre las dos funciones, podemos crear un programa que genere un array de un millón de elementos ordenados y realice una búsqueda binaria en el array para encontrar un número aleatorio. Podemos ejecutar cada función varias veces y calcular el tiempo promedio de ejecución.

En este programa, generamos un array ordenado de un millón de elementos y buscamos un número aleatorio en el array. Medimos el tiempo de ejecución de la función binsearch_original y de la función binsearch_reescrita al buscar este número aleatorio en el array. Ejecutamos cada función 1000 veces y calculamos el tiempo promedio de ejecución.

Finalmente, imprimimos los tiempos de ejecución de ambas funciones en segundos. Este programa nos permite comparar los tiempos de ejecución de ambas funciones y ver cuál es más rápida.

Tiempo de ejecución de la función original: 0.002768 segundos
Tiempo de ejecución de la función reescrita: 0.002762 segundos

3.4 Switch

Ejercicio 3-2

Escriba una función en lenguaje C denominada escape(s,t) que convierte caracteres como nueva línea y tabulación en secuencias de escape visibles como \n y \t, mientras copia la cadena t a s. Escriba también la función en dirección inversa, convirtiendo secuencias de escape en caracteres reales. Escriba un programa que ilustre el funcionamiento de ambas funciones.

#include 

void escape(char s[], char t[]) {
    int i, j;
    for (i = 0, j = 0; t[i] != '\0'; i++) {
        switch (t[i]) {
            case '\n':
                s[j++] = '\\';
                s[j++] = 'n';
                break;
            case '\t':
                s[j++] = '\\';
                s[j++] = 't';
                break;
            default:
                s[j++] = t[i];
                break;
        }
    }
    s[j] = '\0';
}

void unescape(char s[], char t[]) {
    int i, j;
    for (i = 0, j = 0; t[i] != '\0'; i++) {
        if (t[i] == '\\') {
            switch (t[++i]) {
                case 'n':
                    s[j++] = '\n';
                    break;
                case 't':
                    s[j++] = '\t';
                    break;
                default:
                    s[j++] = '\\';
                    s[j++] = t[i];
                    break;
            }
        } else {
            s[j++] = t[i];
        }
    }
    s[j] = '\0';
}

int main() {
    char t[] = "Hello\tworld\n";
    char s1[100];
    char s2[100];
    escape(s1, t);
    unescape(s2, s1);
    printf("Original: %s", t);
    printf("Escaped: %s\n", s1);
    printf("Unescaped: %s\n", s2);
    return 0;
}

La función escape(s, t) toma una cadena t y copia su contenido en la cadena s, convirtiendo los caracteres especiales como \n y \t en secuencias de escape visibles como \\n y \\t. La función unescape(s, t) hace lo contrario, convirtiendo las secuencias de escape en caracteres reales.

El programa de ejemplo ilustra el funcionamiento de ambas funciones, imprimiendo la cadena original, la cadena escapada y la cadena desescapada en la consola.