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;
}
domingo, 22 de noviembre de 2015
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
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
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
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
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
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
6) Ordenamiento por Heap
Algoritmo
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
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
domingo, 4 de octubre de 2015
Un poco sobre los algoritmos
Algoritmo: Conjunto de Instrucciones bien definidas, ordenadas y finitas que resuelvan un problema. Entre las operaciones matemáticas están la suma, resta, división y multiplicación
Programación Estructurada
Busca que el programador desarrolle programas más sencillos y fáciles de entender, para poder cumplir esto, se hace uso de 3 estructuras básicas de control. La programación estructurada se basa en un teorema el cual plantea que cualquier programa (sin importar el tipo de trabajo que ejecute) puede ser elaborado utilizando únicamente las 3 estructuras básicas, las cuales son:
1- Estructura Secuencial: Indica que una instrucción se ejecute una después de la otra, y en orden.
2- Estructura Selectiva: También conocida como SI-VERDADERO-FALSO plantea la selección entre 2 alternativas de una condición.
3- Estructura Repetitiva (Iterativa): Conocida como HACER-MIENTRAS-QUE, es una ejecución repetida de una instrucción mientras que se cumpla una condición.
Representación de un Algoritmo
Hay varias formas de representar un algoritmo, las más conocidas son:
1) Diagrama de flujo: Es un esquema de representación gráfica, usa elementos gráficos como rectángulos y rombos, tambien se debe mencionar que se pueden hacer operaciones matemáticas.
2) Pseudo-Código : Es un esquema que usa subconjuntos del lenguaje natural del diseñador de algoritmos, elimina posibles ambigüedades empleando una notación que aunque libre es más limitada que la del lenguaje general
Ejemplo Diagrama de flujo y Pseudo-Código
Tambien puede ser una buena forma de representar algoritmos con C y C++
Ejemplos de C y C++
Estructura de C++
Tipos de Datos en C++:
int (Números enteros)
float (Números decimales)
double (Números reales más grandes que float)
bool (valores lógicos)
char (Caracteres)
void (Sirve para indicar que una función no devuelve valores)
Cin
El archivo de la biblioteca de C++ <iostream.h> proporciona un flujo de entrada estándar cin y un operador de extracción >>, para extraer valores de flujo y almacenarlos en variables.
cin>>variables , donde variables puede ser 1 o más separados por >>
Cout
Parecido al cin, solamente que el archivo de la biblioteca proporciona un flujo de salida estándar cout y un operador de extracción <<, que normalmente se manda a la pantalla del usuario
cout << lista , donde lista puede ser una variable, valores constantes o expresiones separadas por <<.
Instrucciones de Selección
If - else : Permite decidir si ejecutar o no un conjunto de instrucciones
Forma: if (expresión) instrucción1 else instrucción2
ejemplo
#include <iostream.h>
void main()
{
int nota;
cout << "Ingrese la nota:";
cin >> nota;
if (nota >= 4)
{
cout << "Aprobado, felicitaciones!"<<endl;
}
else
{
cout << "No aprobado."<<endl;
};
cout <<"Fin del programa.";
}
While: Se utiliza para crear ciclos, en los cuales un grupo de instrucciones se ejecuta de forma repetida, hasta que se satisface alguna condición.
Forma: while (expresión) instrucción
ejemplo
#include <iostream.h>
int main() {
int repetir = 1;
while(repetir==1) {
cout <<“Ingrese un valor:” ;
cin>>repetir;
}
return 0;
}
Do - While : Se utiliza para realizar una comprobación final de cada pasada
Forma: do instrucción while (expresión)
ejemplo
#include <iostream.h>
int main() {
int repetir;
do {
cout <<“Ingrese un valor:” ;
cin>>repetir;
} while(repetir==1);
return 0;
For: Quizás es el más frecuentemente usado de las instrucciones para crear ciclos. Incluye una expresión que especifica el valor inicial de un índice, también tiene una segunda expresión que determina cuando continúa o no el ciclo, y finalmente tiene una tercera expresión que permite que el índice se modifique al final de cada pasada.
Forma: for(expresión1 ; expresión2 ; expresión3) instrucción
ejemplo
#include <iostream.h>
int main() {
int i;
for(i=0; i<10; i++) {
cout <<“i<< i;
}
return 0;
}
Switch: Hace que se selecciones un grupo de instrucciones entre varios grupos disponibles. La selección se basa en el valor de una expresión que se incluye en la instrucción switch
Forma: switch(expresión) instrucción , donde expresión devuelve un valor entero, expresión también puede ser tipo char
ejemplo
cout << "Uso de SWITCH" << endl;
switch(num){
case 1: cout << "Valor es 1 " << endl;
break;
case 2: cout << "Valor es 2 " << endl;
break;
case 3: cout << "Valor es 3 " << endl;
break;
case 4: cout << "Valor es 4 " << endl;
break;
case 5: cout << "Valor es 5 " << endl;
break;
default:cout << "Valor es mayor que 5 " << endl;
}
return 0;
}
Break: Se utiliza para terminar la ejecución de ciclos o salir de una instrucción switch. Se puede utilizar dentro de una instrucción while, do-while, for o switch.
Forma: Break;
Comparación de Ciclos:
Vectores y Matrices:
Vector: Un vector, también llamado array(arreglo) unidimensional, es una estructura de datos que permite agrupar elementos del mismo tipo y almacenarlos en un solo bloque de memoria juntos, uno despues de otro. A este grupo de elementos se les identifica por un mismo nombre y la posición en la que se encuentran. La primera posición del array es la posición 0.
Matriz: Una matriz es un vector de vectores o un también llamado array bidimensional. La manera de declarar una matriz es C++ es similar a un vector:
Programación Estructurada
Busca que el programador desarrolle programas más sencillos y fáciles de entender, para poder cumplir esto, se hace uso de 3 estructuras básicas de control. La programación estructurada se basa en un teorema el cual plantea que cualquier programa (sin importar el tipo de trabajo que ejecute) puede ser elaborado utilizando únicamente las 3 estructuras básicas, las cuales son:
1- Estructura Secuencial: Indica que una instrucción se ejecute una después de la otra, y en orden.
2- Estructura Selectiva: También conocida como SI-VERDADERO-FALSO plantea la selección entre 2 alternativas de una condición.
3- Estructura Repetitiva (Iterativa): Conocida como HACER-MIENTRAS-QUE, es una ejecución repetida de una instrucción mientras que se cumpla una condición.
Representación de un Algoritmo
Hay varias formas de representar un algoritmo, las más conocidas son:
1) Diagrama de flujo: Es un esquema de representación gráfica, usa elementos gráficos como rectángulos y rombos, tambien se debe mencionar que se pueden hacer operaciones matemáticas.
2) Pseudo-Código : Es un esquema que usa subconjuntos del lenguaje natural del diseñador de algoritmos, elimina posibles ambigüedades empleando una notación que aunque libre es más limitada que la del lenguaje general
Ejemplo Diagrama de flujo y Pseudo-Código
Tambien puede ser una buena forma de representar algoritmos con C y C++
Ejemplos de C y C++
Estructura de C++
Tipos de Datos en C++:
int (Números enteros)
float (Números decimales)
double (Números reales más grandes que float)
bool (valores lógicos)
char (Caracteres)
void (Sirve para indicar que una función no devuelve valores)
Cin
El archivo de la biblioteca de C++ <iostream.h> proporciona un flujo de entrada estándar cin y un operador de extracción >>, para extraer valores de flujo y almacenarlos en variables.
cin>>variables , donde variables puede ser 1 o más separados por >>
Cout
Parecido al cin, solamente que el archivo de la biblioteca proporciona un flujo de salida estándar cout y un operador de extracción <<, que normalmente se manda a la pantalla del usuario
cout << lista , donde lista puede ser una variable, valores constantes o expresiones separadas por <<.
Instrucciones de Selección
If - else : Permite decidir si ejecutar o no un conjunto de instrucciones
Forma: if (expresión) instrucción1 else instrucción2
ejemplo
#include <iostream.h>
void main()
{
int nota;
cout << "Ingrese la nota:";
cin >> nota;
if (nota >= 4)
{
cout << "Aprobado, felicitaciones!"<<endl;
}
else
{
cout << "No aprobado."<<endl;
};
cout <<"Fin del programa.";
}
While: Se utiliza para crear ciclos, en los cuales un grupo de instrucciones se ejecuta de forma repetida, hasta que se satisface alguna condición.
Forma: while (expresión) instrucción
ejemplo
#include <iostream.h>
int main() {
int repetir = 1;
while(repetir==1) {
cout <<“Ingrese un valor:” ;
cin>>repetir;
}
return 0;
}
Do - While : Se utiliza para realizar una comprobación final de cada pasada
Forma: do instrucción while (expresión)
ejemplo
#include <iostream.h>
int main() {
int repetir;
do {
cout <<“Ingrese un valor:” ;
cin>>repetir;
} while(repetir==1);
return 0;
For: Quizás es el más frecuentemente usado de las instrucciones para crear ciclos. Incluye una expresión que especifica el valor inicial de un índice, también tiene una segunda expresión que determina cuando continúa o no el ciclo, y finalmente tiene una tercera expresión que permite que el índice se modifique al final de cada pasada.
Forma: for(expresión1 ; expresión2 ; expresión3) instrucción
ejemplo
#include <iostream.h>
int main() {
int i;
for(i=0; i<10; i++) {
cout <<“i<< i;
}
return 0;
}
Switch: Hace que se selecciones un grupo de instrucciones entre varios grupos disponibles. La selección se basa en el valor de una expresión que se incluye en la instrucción switch
Forma: switch(expresión) instrucción , donde expresión devuelve un valor entero, expresión también puede ser tipo char
ejemplo
cout << "Uso de SWITCH" << endl;
switch(num){
case 1: cout << "Valor es 1 " << endl;
break;
case 2: cout << "Valor es 2 " << endl;
break;
case 3: cout << "Valor es 3 " << endl;
break;
case 4: cout << "Valor es 4 " << endl;
break;
case 5: cout << "Valor es 5 " << endl;
break;
default:cout << "Valor es mayor que 5 " << endl;
}
return 0;
}
Break: Se utiliza para terminar la ejecución de ciclos o salir de una instrucción switch. Se puede utilizar dentro de una instrucción while, do-while, for o switch.
Forma: Break;
Comparación de Ciclos:
Vectores y Matrices:
Vector: Un vector, también llamado array(arreglo) unidimensional, es una estructura de datos que permite agrupar elementos del mismo tipo y almacenarlos en un solo bloque de memoria juntos, uno despues de otro. A este grupo de elementos se les identifica por un mismo nombre y la posición en la que se encuentran. La primera posición del array es la posición 0.
int a[5]; // Vector de 5 enterosMatriz: Una matriz es un vector de vectores o un también llamado array bidimensional. La manera de declarar una matriz es C++ es similar a un vector:
int matrix[rows][cols]; Tipos de matrices   Suma y Producto de un número real por una matriz.   Producto de Matrices Dadas
dos matrices A = (aij)m×n y B = (bij)p×q donde n = p, es decir, el
número de columnas de la primera matriz A es igual al número de filas de
la matriz B , se define el producto A·B de la siguiente forma : |
Algebra Binaria
El hombre trabaja normalmente con el sistema decimal (base 10), mientras que el ordenador trabaja con el sistema binario (base 2). En el sistema binario se emplean 10 símbolos (0 al 9), mientras que el binario solo se emplean 2 (0 y 1)
Sistema Binario: Sistema de enumeración en el que solo se utilizan las cifras 0 y 1. Es el sistema ocupado por los computadores, ya que trabajan con 2 niveles de voltaje ( encendido 1 y apagado 0)
Código Binario: Sistema de representación de datos o procesadores de instrucciones de ordenador, utiliza el sistema binario.
En Informática y Telecomunicaciones se usan variados métodos de decodificación de datos tales como cadena de caracteres, o cadena de bits. Estos métodos pueden ser de ancho fijo o variable. En un código binario de ancho fijo cada letra, número, dígito o símbolo esta representado por una cadena de bits de la misma longitud como un numero binario que suelen aparecer en las tablas en notación octal, decimal, hexadecimal.
Conversiones
Decimal a binario
Se toma un numero y se empieza a dividir por 2, cada división da un resto que puede ser 0 o 1, el resto es lo que permite saber el numero binario de un decimal, se debe tomar en consideración que se debe tomar de derecha a izquierda los valores de los restos
Decimal fraccionario (con decimales) a Binario
Se inicia por el lado izquierdo, multiplicando cada número por 2 (si la parte entera es mayor que 0 en binario será 1, y en caso contrario es 0)
En caso de ser 1, en la siguiente multiplicación se utilizan sólo los decimales.
Después de realizar cada multiplicación, se colocan los números obtenidos en el orden de su obtención.
Algunos números se transforman en dígitos periódicos, por ejemplo: el 0,1
Ejemplo
0.3125 (decimal) => 0.0101 (binario).
Proceso: 0.3125 x 2 = 0.625 => 0
0.625 x 2 = 1.25 => 1
0.25 x 2 = 0.5 => 0
0.5 x 2 = 1 => 1
En orden: 0101 -> 0.0101 (binario)
Binario a Decimal
Se debe utilizar las potencias del numero 2, cada valor del número binario equivale a una potencia del numero 2, donde el 1 binario dice que tiene un valor asignado (una potencia de 2) y el 0 que no tiene valor asignado, para poder pasar de binario a decimal se suman las potencias, la siguiente foto explica de mejor forma lo que quiero decir
Para poder entender mejores las conversiones aquí una tabla con sus respectivas equivalencias
Operaciones con números binarios
Suma Resta División Multiplicación
donde: donde: donde: donde:
0+0=0 0-0=0 0/0=No existe 0x0=0
0+1=1 0-1=1* 0/1=0 0x1=0
1+0=1 1-0=1 1/0= Indef. 1x0=0
1+1=0* 1-1=0 1/1=1 1x1=1
Representación de Caracteres
- ASCII (American Standard Code for Information Interchange): Estándar Americano para intercambio de información. La tabla básica de ASCII está compuesta por 128 caracteres que incluye símbolos y caracteres de control. Cada carácter esta representado por 7 bits. ASCII tiene una versión que se extiende hasta los 256 caracteres
- EBCDIC (Extended Binary Coded Decimal Interchange Code): Es una codificación de caracteres de 8 bits utilizada en los mainframes de IBM y en AS/400s
- Unicode: Es una norma de codificación de caracteres.
Tabla de Capacidades de almacenamientos
Sistema Binario: Sistema de enumeración en el que solo se utilizan las cifras 0 y 1. Es el sistema ocupado por los computadores, ya que trabajan con 2 niveles de voltaje ( encendido 1 y apagado 0)
Código Binario: Sistema de representación de datos o procesadores de instrucciones de ordenador, utiliza el sistema binario.
En Informática y Telecomunicaciones se usan variados métodos de decodificación de datos tales como cadena de caracteres, o cadena de bits. Estos métodos pueden ser de ancho fijo o variable. En un código binario de ancho fijo cada letra, número, dígito o símbolo esta representado por una cadena de bits de la misma longitud como un numero binario que suelen aparecer en las tablas en notación octal, decimal, hexadecimal.
Conversiones
Decimal a binario
Se toma un numero y se empieza a dividir por 2, cada división da un resto que puede ser 0 o 1, el resto es lo que permite saber el numero binario de un decimal, se debe tomar en consideración que se debe tomar de derecha a izquierda los valores de los restos
Decimal fraccionario (con decimales) a Binario
Se inicia por el lado izquierdo, multiplicando cada número por 2 (si la parte entera es mayor que 0 en binario será 1, y en caso contrario es 0)
En caso de ser 1, en la siguiente multiplicación se utilizan sólo los decimales.
Después de realizar cada multiplicación, se colocan los números obtenidos en el orden de su obtención.
Algunos números se transforman en dígitos periódicos, por ejemplo: el 0,1
Ejemplo
0.3125 (decimal) => 0.0101 (binario).
Proceso: 0.3125 x 2 = 0.625 => 0
0.625 x 2 = 1.25 => 1
0.25 x 2 = 0.5 => 0
0.5 x 2 = 1 => 1
En orden: 0101 -> 0.0101 (binario)
Binario a Decimal
Se debe utilizar las potencias del numero 2, cada valor del número binario equivale a una potencia del numero 2, donde el 1 binario dice que tiene un valor asignado (una potencia de 2) y el 0 que no tiene valor asignado, para poder pasar de binario a decimal se suman las potencias, la siguiente foto explica de mejor forma lo que quiero decir
Para poder entender mejores las conversiones aquí una tabla con sus respectivas equivalencias
Operaciones con números binarios
Suma Resta División Multiplicación
donde: donde: donde: donde:
0+0=0 0-0=0 0/0=No existe 0x0=0
0+1=1 0-1=1* 0/1=0 0x1=0
1+0=1 1-0=1 1/0= Indef. 1x0=0
1+1=0* 1-1=0 1/1=1 1x1=1
Representación de Caracteres
- ASCII (American Standard Code for Information Interchange): Estándar Americano para intercambio de información. La tabla básica de ASCII está compuesta por 128 caracteres que incluye símbolos y caracteres de control. Cada carácter esta representado por 7 bits. ASCII tiene una versión que se extiende hasta los 256 caracteres
- EBCDIC (Extended Binary Coded Decimal Interchange Code): Es una codificación de caracteres de 8 bits utilizada en los mainframes de IBM y en AS/400s
- Unicode: Es una norma de codificación de caracteres.
Tabla de Capacidades de almacenamientos
Un poco de Historia de la Computación e Informática.
Una breve síntesis de la historia de la computación
- 500 A.C. --> Aparece el Ábaco
- 1642 --> Se crea la Pascalina (por Blaise Pascal), que es una máquina calculadora
- 1670 --> Gottfried Leibniz mejora la pascalina, añadiéndole la opción de multiplicar, dividir y para la raíz cúbica
- 1679 --> G. Leibniz desarrolla el modo aritmético binario, basado en el 0 y 1
- 1786 --> Johann Von Müller idea una calculadora mecánica, la cual solo se quedó en su pensamiento, ya que nunca la pudo concretar
- 1822 --> Charles Babbage re-descubre la idea de Müller y en este año diseña la máquina diferencial, la cual tampoco se pudo concretar
- 1833 --> C. Babbage diseña la máquina Analítica, que tampoco pudo ser construida.
- La condesa Ada Byron de Lovelace trabajo sobre la máquina analítica de Babbage. La condesa es considerada la primera programadora de la historia, ya que fue la primera en crear un algoritmo para la máquina.
- 1854 --> George Boole desarrollo la teoría del álgebra de Boole, la cual permite el desarrollo para la álgebra binaria
- 1886 --> Herman Hollerith inventa la máquina censadora o máquina tabuladora, la cual le permitio almacenar la información de las personas censadas y tabular su información, está basado en tarjetas perforadas
- 1940 --> Konrad Zuse finaliza su modelo Z2, la cual fue la primera computadora electro-mecánia completamente funcional
- 1941 --> Alan Turing, con ayuda de M.H.A.Neuman construyeron una gran máquina llamada Colossus, esta máquina tenía como finalidad descifrar los códigos alemanes durante la II Guerra Mundial
- 1942 --> Se termina de construir la primera computadora digital, aunque nunca se mejoró y sus creadores nunca la patentaron, por lo que hubieron conflictos con IBM
- 1944 --> Jhon Louis Von Neumann contribuyo de forma directa con las computadores de la primera generación, asesoro a los creadores de la ENIAC, que más tarde crearon la UNIAC. En la década de los 50 trabajo en IBM como consultor. Él también ayudo en la construcción de la computadora Mark I
- La Mark I es la primera máquina que puede ejecutar operaciones largas de forma automática.
- 1946 --> Se construye la ENIAC (Fue para fines militares)
- 1947 --> Se inventa el Transistor
- 1949 --> Se construye la EDVAC (Primer equipo con capacidad de almacenamiento).
- 1949 --> Jack Forrest inventa la memoria de núcleo de acero.
- 1951 --> Grace Hooper crea el primer compilador, llamado A-0 (Math Matic)
- 1951 --> Fue presentada la UNIVAC
- 1958 --> Se inventan los Circuitos Integrados
- 1960 --> G. Hooper presenta su primera versión del lenguaje COBOL
- 1964 --> IBM presenta su primera generación de computadores, IBM 360
- 1970 --> El Network Working Group acabó el protocolo host a host inicial para ARPANET, llamado Network Control Protocol (NCP). Durante los periodos de 1971-1972 los usuarios de la red pudieron comenzar a desarrollar aplicaciones.
- 1974 --> Intel crea la primera CPU
- 1975 --> Se funda Microsoft
- 1981 --> IBM presenta la Personal Computer ( IBM PC)
- 1984 --> Apple presenta la Macintosh, la cual se caracteriza por un sistema operativo que cuenta con una vistosa e intuitiva G.U.I. (Graphics Unit Interface)
- 1991 --> Se comienza a desarrollar Linux
- 1995 --> Microsoft lanza Windows 95
- 2000 --> Macintosh lanza su sistema operativo Mac OS X
- 2015 --> Microsoft lanza Windows 10
El aumento del conocimiento depende por completo de la existencia del desacuerdo.
Karl Popper
- 500 A.C. --> Aparece el Ábaco
- 1642 --> Se crea la Pascalina (por Blaise Pascal), que es una máquina calculadora
- 1670 --> Gottfried Leibniz mejora la pascalina, añadiéndole la opción de multiplicar, dividir y para la raíz cúbica
- 1679 --> G. Leibniz desarrolla el modo aritmético binario, basado en el 0 y 1
- 1786 --> Johann Von Müller idea una calculadora mecánica, la cual solo se quedó en su pensamiento, ya que nunca la pudo concretar
- 1822 --> Charles Babbage re-descubre la idea de Müller y en este año diseña la máquina diferencial, la cual tampoco se pudo concretar
- 1833 --> C. Babbage diseña la máquina Analítica, que tampoco pudo ser construida.
- La condesa Ada Byron de Lovelace trabajo sobre la máquina analítica de Babbage. La condesa es considerada la primera programadora de la historia, ya que fue la primera en crear un algoritmo para la máquina.
- 1854 --> George Boole desarrollo la teoría del álgebra de Boole, la cual permite el desarrollo para la álgebra binaria
- 1886 --> Herman Hollerith inventa la máquina censadora o máquina tabuladora, la cual le permitio almacenar la información de las personas censadas y tabular su información, está basado en tarjetas perforadas
- 1940 --> Konrad Zuse finaliza su modelo Z2, la cual fue la primera computadora electro-mecánia completamente funcional
- 1941 --> Alan Turing, con ayuda de M.H.A.Neuman construyeron una gran máquina llamada Colossus, esta máquina tenía como finalidad descifrar los códigos alemanes durante la II Guerra Mundial
- 1942 --> Se termina de construir la primera computadora digital, aunque nunca se mejoró y sus creadores nunca la patentaron, por lo que hubieron conflictos con IBM
- 1944 --> Jhon Louis Von Neumann contribuyo de forma directa con las computadores de la primera generación, asesoro a los creadores de la ENIAC, que más tarde crearon la UNIAC. En la década de los 50 trabajo en IBM como consultor. Él también ayudo en la construcción de la computadora Mark I
- La Mark I es la primera máquina que puede ejecutar operaciones largas de forma automática.
- 1946 --> Se construye la ENIAC (Fue para fines militares)
- 1947 --> Se inventa el Transistor
- 1949 --> Se construye la EDVAC (Primer equipo con capacidad de almacenamiento).
- 1949 --> Jack Forrest inventa la memoria de núcleo de acero.
- 1951 --> Grace Hooper crea el primer compilador, llamado A-0 (Math Matic)
- 1951 --> Fue presentada la UNIVAC
- 1958 --> Se inventan los Circuitos Integrados
- 1960 --> G. Hooper presenta su primera versión del lenguaje COBOL
- 1964 --> IBM presenta su primera generación de computadores, IBM 360
- 1970 --> El Network Working Group acabó el protocolo host a host inicial para ARPANET, llamado Network Control Protocol (NCP). Durante los periodos de 1971-1972 los usuarios de la red pudieron comenzar a desarrollar aplicaciones.
- 1974 --> Intel crea la primera CPU
- 1975 --> Se funda Microsoft
- 1981 --> IBM presenta la Personal Computer ( IBM PC)
- 1984 --> Apple presenta la Macintosh, la cual se caracteriza por un sistema operativo que cuenta con una vistosa e intuitiva G.U.I. (Graphics Unit Interface)
- 1991 --> Se comienza a desarrollar Linux
- 1995 --> Microsoft lanza Windows 95
- 2000 --> Macintosh lanza su sistema operativo Mac OS X
- 2015 --> Microsoft lanza Windows 10
El aumento del conocimiento depende por completo de la existencia del desacuerdo.
Karl Popper
Suscribirse a:
Entradas (Atom)