Ejercicios en C++

1) Matriz Mágica de 3x3


#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

bool esMagica(int matriz[3][3], int largo);

/*
 *
 */
int main(int argc, char** argv) {

    int matriz[3][3];
    int i, j;
    int largo = 3;

    /**
     *
     * Llenar la matriz
     */
    for (i = 0; i < largo; i++) {
        for (j = 0; j < largo; j++) {
            cout << "\nIngrese el valor de Matriz[" << i << "][" << j << "]: ";
            int valor;
            cin >> valor;
            matriz[i][j] = valor;
        }
    }

    if (esMagica(matriz, 3)) {
        cout << "\n La matriz es magica" << endl;
    } else {
        cout << "\n La matriz NO es magica" << endl;
    }


    return 0;
}

bool esMagica(int matriz[3][3], int largo) {
    bool ok = false;
    int i;
    if (largo == 3) {
        int sumaFilaUno = 0;
        int sumaFilaDos = 0;
        int sumaFilaTres = 0;
        int sumaColumnaUno = 0;
        int sumaColumnaDos = 0;
        int sumaColumnaTres = 0;
        int sumaDiagonalUno = 0;
        int sumaDiagonalDos = 0;

        // Suma de la Fila 1
        for (i = 0; i < largo; i++) {
            sumaFilaUno = sumaFilaUno + matriz[0][i];
        }

        // Suma de la Fila 2
        for (i = 0; i < largo; i++) {
            sumaFilaDos = sumaFilaDos + matriz[1][i];
        }

        // Suma de la Fila 3
        for (i = 0; i < largo; i++) {
            sumaFilaTres = sumaFilaTres + matriz[2][i];
        }

        // Suma de la Columna 1
        for (i = 0; i < largo; i++) {
            sumaColumnaUno = sumaColumnaUno + matriz[i][0];
        }

        // Suma de la Columna 2
        for (i = 0; i < largo; i++) {
            sumaColumnaDos = sumaColumnaDos + matriz[i][1];
        }

        // Suma de la Columna 3
        for (i = 0; i < largo; i++) {
            sumaColumnaTres = sumaColumnaTres + matriz[i][2];
        }

        // Suma Diagonal 1
        sumaDiagonalUno = (matriz[0][0] + matriz[1][1] + matriz[2][2]);
        sumaDiagonalDos = (matriz[2][0] + matriz[1][1] + matriz[0][2]);

        if (sumaFilaUno == sumaFilaDos) {
            if (sumaFilaTres == sumaFilaDos) {
                if (sumaFilaTres == sumaColumnaUno) {
                    if (sumaColumnaUno == sumaColumnaDos) {
                        if (sumaColumnaTres == sumaColumnaDos) {
                            if (sumaColumnaTres == sumaDiagonalUno) {
                                if (sumaDiagonalUno == sumaDiagonalDos) {
                                    ok = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    } else {
        cout << "\nSolo soporta matrices de 3x3" << endl;
    }

    return ok;
}



2) Operaciones con Matrices (Calculadora de Matrices)


 #include <iostream>
#include <cstdlib>

using namespace std;

/**
 * Función que determina la selección de un usuario
 * @return
 */
int menuPrincipal();

/**
 * Limpia la pantalla, llamando a comandos de sistema operativo.
 */
void limpiarPantalla();

/**
int** crearMatriz(int filas, int columnas);



int** llenarMatriz(int filas, int columnas);

/**
 * Imprime una matriz en pantalla.
 * @param matriz Puntero a la matriz.
 * @param filas Cantidad de Filas.
 * @param columnas Cantidad de Columnas.
 */
void imprimirMatriz(int** matriz, int filas, int columnas);

/**
 * Elimina la memoria usada por la matriz.
 * @param matriz Puntero a la matriz.
 * @param filas Cantidad de Filas.
 * @param columnas Cantidad de Columnas.
 */
void eliminarMatriz(int** matriz, int filas, int columnas);

/**
 * Realiza una suma de matrices.
 * @param primera Primera Matriz.
 * @param filasPrimera Filas de la primera matriz.
 * @param columnasPrimera Columnas de la primera matriz.
 * @param segunda Segunda Matriz.
 * @param filasSegunda Filas de la segunda Matriz.
 * @param columnasSegunda columnas de la segunda Matriz.
 * @param filasRespuesta Cantidad de filas de respuesta.
 * @param columnasRespuesta Cantidad de columnas de respuesta.
 * @return Una Matriz
 */
int** sumarMatrices(int** primera, int filasPrimera, int columnasPrimera, int** segunda, int filasSegunda, int columnasSegunda, int *filasRespuesta, int *columnasRespuesta);

/**
 * Realiza una resta de matrices.
 * @param primera Primera Matriz.
 * @param filasPrimera Filas de la primera matriz.
 * @param columnasPrimera Columnas de la primera matriz.
 * @param segunda Segunda Matriz.
 * @param filasSegunda Filas de la segunda Matriz.
 * @param columnasSegunda columnas de la segunda Matriz.
 * @param filasRespuesta Cantidad de filas de respuesta.
 * @param columnasRespuesta Cantidad de columnas de respuesta.
 * @return Una Matriz
 */
int** restarMatrices(int** primera, int filasPrimera, int columnasPrimera, int** segunda, int filasSegunda, int columnasSegunda, int *filasRespuesta, int *columnasRespuesta);

/**
 * Multiplica la matriz por un escalar
 * @param escalar Número a Multiplicar
 * @param primera Matriz
 * @param filasPrimera Filas
 * @param columnasPrimera columnas
 * @return una Matriz de Resultado
 */
int** multiplicarEscalarMatrices(int escalar, int** primera, int filasPrimera, int columnasPrimera, int *filasRespuesta, int *columnasRespuesta);

/**
 * Realiza una multiplicación de matrices.
 * @param primera Primera Matriz.
 * @param filasPrimera Filas de la primera matriz.
 * @param columnasPrimera Columnas de la primera matriz.
 * @param segunda Segunda Matriz.
 * @param filasSegunda Filas de la segunda Matriz.
 * @param columnasSegunda columnas de la segunda Matriz.
 * @param filasRespuesta Cantidad de filas de respuesta.
 * @param columnasRespuesta Cantidad de columnas de respuesta.
 * @return Una Matriz
 */
int** multiplicarMatrices(int** primera, int filasPrimera, int columnasPrimera, int** segunda, int filasSegunda, int columnasSegunda, int *filasRespuesta, int *columnasRespuesta);

/**
 * Cuerpo del programa.
 * @param argc Cantidad de argumentos pasados por la línea de comandos
 * @param argv Matriz con los argumentos de la línea de comandos.
 * @return Un código de Salida
 */
int main(int argc, char** argv) {

    int seleccion = 99;
    int numero;
    int filasUno, filasDos, filasResultado;
    int columnasUno, columnasDos, columnasResultado;
    int **uno, **dos, **resultado;

    while (seleccion != 0) {
        // Selecciono una opción
        seleccion = menuPrincipal();
        switch (seleccion) {
            case 0:
                limpiarPantalla();
                cout << "\n Tarea computacional desarrollada por Guillermo Salazar Molina" << endl;
                break;

            case 1:
                // Llenamos Matriz uno
                limpiarPantalla();
                cout << "\nLlenando matriz UNO" << endl;
                cout << "\n Ingrese la cantidad de filas: ";
                cin >> filasUno;

                cout << "\n Ingrese la cantidad de Columnas: ";
                cin >> columnasUno;

                uno = llenarMatriz(filasUno, columnasUno);
                imprimirMatriz(uno, filasUno, columnasUno);
                break;

            case 2:
                // Llenamos Matriz dos
                limpiarPantalla();
                cout << "\nLlenando matriz DOS" << endl;
                cout << "\n Ingrese la cantidad de filas: ";
                cin >> filasDos;

                cout << "\n Ingrese la cantidad de Columnas: ";
                cin >> columnasDos;

                dos = llenarMatriz(filasDos, columnasDos);
                imprimirMatriz(dos, filasDos, columnasDos);
                break;

            case 3:
                imprimirMatriz(uno, filasUno, columnasUno);
                break;

            case 4:
                imprimirMatriz(dos, filasDos, columnasDos);
                break;

            case 5:
                resultado = sumarMatrices(uno, filasUno, columnasUno, dos, filasDos, columnasDos, &filasResultado, &columnasResultado);
                imprimirMatriz(resultado, filasResultado, columnasResultado);
                break;

            case 6:
                resultado = restarMatrices(uno, filasUno, columnasUno, dos, filasDos, columnasDos, &filasResultado, &columnasResultado);
                imprimirMatriz(resultado, filasResultado, columnasResultado);
                break;

            case 7:
                limpiarPantalla();
                cout << "\nIngrese un escalar: ";
                cin >> numero;

                resultado = multiplicarEscalarMatrices(numero, uno, filasUno, columnasUno, &filasResultado, &columnasResultado);
                imprimirMatriz(resultado, filasResultado, columnasResultado);
                break;

            case 8:
                limpiarPantalla();
                cout << "\nIngrese un escalar: ";
                cin >> numero;

                resultado = multiplicarEscalarMatrices(numero, dos, filasDos, columnasDos, &filasResultado, &columnasResultado);
                imprimirMatriz(resultado, filasResultado, columnasResultado);
                break;

            case 9:
                resultado = multiplicarMatrices(uno, filasUno, columnasUno, dos, filasDos, columnasDos, &filasResultado, &columnasResultado);
                imprimirMatriz(resultado, filasResultado, columnasResultado);
                break;

            default:
                cout << "Opción invalida" << endl;
                break;
        }
    }

    eliminarMatriz(uno, filasUno, columnasUno);
    eliminarMatriz(dos, filasDos, columnasDos);
    eliminarMatriz(resultado, filasResultado, columnasResultado);

    return 0;
}

int menuPrincipal() {
    int seleccion = 99;

    /**
     *
     * Iteramos hasta que se seleccione una opción válida.
     */
    while (seleccion < 0 || seleccion > 9) {
        cout << "\n\t Bienvenido a la calculadora de matrices" << endl;
        cout << "1\t - Llenar Matriz uno." << endl;
        cout << "2\t - Llenar Matriz dos." << endl;
        cout << "3\t - Imprimir Matriz uno." << endl;
        cout << "4\t - Imprimir Matriz dos." << endl;
        cout << "5\t - Sumar Matrices (uno + dos)." << endl;
        cout << "6\t - Restar Matrices (uno - dos)." << endl;
        cout << "7\t - Multiplicar Matriz UNO por un escalar." << endl;
        cout << "8\t - Multiplicar Matriz DOS por un escalar." << endl;
        cout << "9\t - Multiplicar Matrices (uno * dos)." << endl;
        cout << "0\t - Salir." << endl;
        cout << "Seleccione una opcion: ";
        cin >> seleccion;
    }

    return seleccion;
}

void limpiarPantalla() {

    if (system("CLS")) {
        system("clear");
    }
}

int** crearMatriz(int filas, int columnas) {
    int** matriz = NULL;
    int i, j;
    if (filas > 0) {
        if (columnas > 0) {
            /**
             * Una matriz es un arreglo de arreglos, la estrategia es definir
             * un arreglo del largo de las filas.
             */
            matriz = new int*[filas];
            for (i = 0; i < filas; i++) {
                // Por cada fila, definimos un arreglo del largo de columnas.
                matriz[i] = new int[columnas];
                for (j = 0; j < columnas; j++) {
                    // Relleno con 0
                    matriz[i][j] = 0;
                }
            }
        }
    }
    return matriz;
}

int** llenarMatriz(int filas, int columnas) {
    int** matriz = NULL;
    int i, j;
    if (filas > 0) {
        if (columnas > 0) {
            /**
             * Una matriz es un arreglo de arreglos, la estrategia es definir
             * un arreglo del largo de las filas.
             */
            matriz = new int*[filas];
            for (i = 0; i < filas; i++) {
                // Por cada fila, definimos un arreglo del largo de columnas.
                matriz[i] = new int[columnas];
                for (j = 0; j < columnas; j++) {
                    int valor;
                    cout << "\n Ingrese el valor para la posicion [" << i << "][ " << j << " ]:";
                    cin >> valor;
                    matriz[i][j] = valor;
                }
            }
        }
    }
    return matriz;
}

void imprimirMatriz(int** matriz, int filas, int columnas) {
    int i, j;
    limpiarPantalla();
    if (matriz != NULL) {
        if (filas > 0) {
            if (columnas > 0) {

                cout << "\n Imprimiendo MATRIZ " << endl;

                for (i = 0; i < filas; i++) {
                    cout << endl;
                    for (j = 0; j < columnas; j++) {
                        int valor = matriz[i][j];
                        cout << "[" << valor << " ]";
                    }
                }
                cout << endl;
            } else {
                cout << "\nMatriz con valor para columnas invalido" << endl;
            }
        } else {
            cout << "\nMatriz con valor para filas invalido" << endl;
        }
    } else {
        cout << "\nMatriz NULA o invalida" << endl;
    }
}

void eliminarMatriz(int** matriz, int filas, int columnas) {
    if (matriz != NULL) {
        if (filas > 0) {
            if (columnas > 0) {
                for (int i = 0; i < filas; i++) {
                    // Recorremos las filas y borramos los arreglos internos.
                    delete [] matriz[i];
                }
                // Eliminamos la referencia externa.
                delete [] matriz;
            }
        }
    }
}

int** sumarMatrices(int** primera, int filasPrimera, int columnasPrimera, int** segunda, int filasSegunda, int columnasSegunda, int *filasRespuesta, int *columnasRespuesta) {
    int** resultado = NULL;
    int i, j;
    if (filasPrimera == filasSegunda && columnasPrimera == columnasSegunda) {
        *filasRespuesta = filasPrimera;
        *columnasRespuesta = columnasPrimera;
        resultado = crearMatriz(filasPrimera, columnasPrimera);

        for (i = 0; i < filasPrimera; i++) {
            for (j = 0; j < columnasPrimera; j++) {
                resultado[i][j] = primera[i][j] + segunda[i][j];
            }
        }

    } else {
        cout << "\nNo se cumplen las condiciones para la suma de matrices." << endl;
        *filasRespuesta = 0;
        *columnasRespuesta = 0;
    }
    return resultado;
}

int** restarMatrices(int** primera, int filasPrimera, int columnasPrimera, int** segunda, int filasSegunda, int columnasSegunda, int *filasRespuesta, int *columnasRespuesta) {
    int** resultado = NULL;
    int i, j;
    if (filasPrimera == filasSegunda && columnasPrimera == columnasSegunda) {
        *filasRespuesta = filasPrimera;
        *columnasRespuesta = columnasPrimera;
        resultado = crearMatriz(filasPrimera, columnasPrimera);

        for (i = 0; i < filasPrimera; i++) {
            for (j = 0; j < columnasPrimera; j++) {
                resultado[i][j] = primera[i][j] - segunda[i][j];
            }
        }

    } else {
        cout << "\nNo se cumplen las condiciones para la resta de matrices." << endl;
        *filasRespuesta = 0;
        *columnasRespuesta = 0;
    }
    return resultado;
}

int** multiplicarEscalarMatrices(int escalar, int** primera, int filasPrimera, int columnasPrimera, int *filasRespuesta, int *columnasRespuesta) {
    int** resultado = NULL;
    int i, j;
    if (filasPrimera > 0 && columnasPrimera > 0) {
        *filasRespuesta = filasPrimera;
        *columnasRespuesta = columnasPrimera;
        resultado = crearMatriz(filasPrimera, columnasPrimera);

        for (i = 0; i < filasPrimera; i++) {
            for (j = 0; j < columnasPrimera; j++) {
                resultado[i][j] = primera[i][j] * escalar;
            }
        }

    } else {
        cout << "\nNo se cumplen las condiciones para la multiplicacion escalar de matrices." << endl;
        *filasRespuesta = 0;
        *columnasRespuesta = 0;
    }
    return resultado;
}

int** multiplicarMatrices(int** primera, int filasPrimera, int columnasPrimera, int** segunda, int filasSegunda, int columnasSegunda, int *filasRespuesta, int *columnasRespuesta) {
    int** resultado = NULL;
    int i, j, k;
    if (columnasPrimera == filasSegunda) {
        *filasRespuesta = filasSegunda;
        *columnasRespuesta = columnasPrimera;
        resultado = crearMatriz(filasPrimera, columnasPrimera);

        for (i = 0; i < filasPrimera; i++) {
            for (j = 0; j < columnasSegunda; j++) {
                for (k = 0; k < columnasPrimera; k++) {
                    resultado[i][j] = resultado[i][j] + (primera[i][k] * segunda[k][j]);
                }
            }
        }

    } else {
        cout << "\nNo se cumplen las condiciones para la multiplicacion de matrices." << endl;
        *filasRespuesta = 0;
        *columnasRespuesta = 0;
    }
    return resultado;
}

Páginas de Interés:

http://c.conclase.net/
http://comunidad.dragonjar.org/f179/
http://www.sorting-algorithms.com/
http://www.lawebdelprogramador.com/codigo/C-Visual-C/index1.html
https://ronnyml.wordpress.com/2009/07/04/vectores-matrices-y-punteros-en-c/


Canales de Youtube para aprender

https://www.youtube.com/channel/UCWIJXDfj7QNvnxb0g6k8-xQ

https://www.youtube.com/user/deividcoptero

Metodos de Ordenamiento:

1) Ordenamiento de la burbuja

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian.

Algoritmo

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

2) Ordenamiento por Selección
-Buscas el elemento más pequeño de la lista.
-Lo intercambias con el elemento ubicado en la primera posición de la lista.
-Buscas el segundo elemento más pequeño de la lista.
-Lo intercambias con el elemento que ocupa la segunda posición en la lista.
-Repites este proceso hasta que hayas ordenado toda la lista.

Algoritmo

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

3) Ordenamiento por Quick
Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente:

-Eliges un elemento de la lista. Puede ser cualquiera Lo llamaremos elemento de división.
-Buscas la posición que le corresponde en la lista ordenada
-Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores. En este momento el elemento de división separa la lista en dos sublistas .
-Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.

Algoritmo

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

4) Ordenamiento por inserción
Se guarda una copia del elemento actual y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

Algoritmo

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--) 
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

5) Ordenamiento por Shell
Adaptación y mejora del método por inserción directa. Se utiliza un array con gran número de elemento en el cual compara a cada elemento con el que está a cierto número de lugares a su izquierda. Este salto es constante a razón de N/2 (siendo N el número de elementos). Se realiza el ciclo hasta que no se intercambien mas elementos de sitio. Este salto se reduce a la mitad y se vuelven a dar pasadas hasta que no se intercambie nadie con nadie. El algoritmo finaliza en el momento en que el salto es 1.

Algoritmo

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

6) Ordenamiento por Heap

Este método es una variante del método por selección, donde la búsqueda del elemento máximo de un arreglo se realiza mediante técnicas basadas en la construcción de un montículo.

Puede ser un montículo ascendente o descendente.

Algoritmo

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

7) Ordenamiento por Merge
  MergeSort es un algoritmo de ordenamiento muy eficiente que utliza la técnica "divide y venceras". Su orden asintótico es O(n*log(n)).

Para ordenar un vector lo divide por la mitad en dos segmentos y ordena cada segmento de forma recursiva osea nuevamente divide cada segmento y ordena los subsegmentos de forma recursiva... hasta que en algún momento los segmentos serán de longitud 1 es cuando se llama a la función "merge" (mezclar) que intercala los elementos del ultimo segmento dividido colocando primero los elementos menores.

Algoritmo

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position