EVP7

Algoritmo de ordenamiento

El ordenamiento es una labor común que realizamos continuamente. ¿Pero te has preguntado qué es ordenar? ¿No? Es que es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento.

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voy a mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.

 Ordenamiento Rápido (Quicksort)

^

^

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 (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.

Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).

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 (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas. ejm

 Nombre Procedimiento: OrdRap

 Parámetros:

    lista a ordenar (lista)

    índice inferior (inf)

    índice superior (sup)

                  

    // Inicialización de variables

    1. elem_div = lista[sup];

    2. i = inf - 1;

    3. j = sup;

    4. cont = 1;

   

    // Verificamos que no se crucen los límites

    5. if (inf >= sup)

    6.      retornar;

   

    //  Clasificamos la sublista

    7. while (cont)

    8.      while (lista[++i] < elem_div);

    9.      while (lista[--j] > elem_div);

   10.      if (i < j)

   11.           temp = lista[i];

   12.           lista[i] = lista[j];

   13.           lista[j] = temp;

   14.      else

   15.           cont = 0;

  

   // Copiamos el elemento de división

   // en su posición final

   16. temp = lista[i];

   17. lista[i] = lista[sup];

   18. lista[sup] = temp;

  

   // Aplicamos el procedimiento

   // recursivamente a cada sublista

   19. OrdRap (lista, inf, i - 1);

   20. OrdRap (lista, i + 1, sup);

 Ordenamiento por Selección

^

Este algoritmo también es sencillo. Consiste en lo siguiente:

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.ejm

   1. for (i=0; i<TAM - 1; i++) 

    2.      pos_men = Menor(lista, TAM, i);

    3.      temp = lista[i];

    4.      lista[i] = lista [pos_men];

    5.      lista [pos_men] = temp;

Ordenamiento Burbuja (Bubblesort)

^

^

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. ejm

    1. for (i=1; i<TAM; i++)

    2.      for j=0 ; j<TAM - 1; j++)

    3.           if (lista[j] > lista[j+1])

    4.                temp = lista[j];

    5.                lista[j] = lista[j+1];

    6.                lista[j+1] = temp;

EVP 6

MATRICES

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];

int es el tipo de dato, matrix es el nombre del todo el conjunto de datos y debo de especificar el numero de filas y columnas.

Las matrices también pueden ser de distintos tipos de datos como char, float, double, etc. Las matrices en C++ se almacenan al igual que los vectores en posiciones consecutivas de memoria.

Usualmente uno se hace la idea que una matriz es como un tablero, pero internamente el manejo es como su definición lo indica, un vector de vectores, es decir, los vectores están uno detrás del otro juntos.

La forma de acceder a los elementos de la matriz es utilizando su nombre e indicando los 2 subíndices que van en los corchetes.

Si coloco int matriz[2][3] = 10; estoy asignando al cuarto elemento de la tercera fila el valor 10.

No olvidar que tanto filas como columnas se enumeran a partir de 0. Bueno y para recorrer una matriz podemos usar igualmente un bucle. En este caso usando 2 for:

for(int i = 0; i < rows; i++) {   for(int j = 0; j < cols; j++) {     matrix[i][j] = i % j;   } }

EVP 5

VECTORES

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. La primera posición del array es la posición 0.

Podríamos agrupar en un array una serie de elementos de tipo enteros, flotantes, caracteres, objetos, etc.

Ejm:

int a[5]; // Vector de 5 enteros float b[5]; // vector de 5 flotantes Producto product[5]; // vector de 5 objetos de tipo Producto

Podríamos también inicializar el vector en la declaración:

int a[] = {5, 15, 20, 25, 30}; float b[] = {10.5, 20.5, 30.5, 12.5, 50.5} Producto product[] = {celular, calculadora, camara, ipod, usb}

Como hay 5 elementos en cada array, automáticamente se le asignará 5 espacios de memoria a cada vector, pero si trato de crear el vector de la forma int a[] , el compilador mostrará un error, porque no indiqué el tamaño del vector ni tampoco inicializé sus elementos.

Obviamente el método setPrecio() debe de estar implementado. Para llenar, recorrer e imprimir un vector podemos utilizar un bucle for:

#include <iostream> using namespace std; int main() {   int dim;   cout << "Ingresa la dimension del vector" << endl;   cin >> dim; // Supongamos que ingrese 10   int vector[dim]; // mi vector es de tamanyo 10   for(int i = 0; i < dim; i++){     vector[i] = i * 10;     cout << vector[i] << endl;   }   return 0; }

EVP 4

Algoritmos como Funciones

Conocido como una subrutina o subprograma, como idea general, se presenta como un Subalgoritmo que forma parte del algoritmo principal, el cual permite resolver una tarea específica. Algunos lenguajes de programación, como Visual Basic .NET o Fortran, utilizan el nombre función para referirse a subrutinas que devuelven un valor.

 Una subrutina al ser llamada dentro de un programa hace que el código principal se detenga y se dirija a ejecutar el código de la subrutina, en cambio cuando se llama a una macro, el compilador toma el código de la macro y lo implanta donde fue llamado, aumentando así el código fuente y por consiguiente el objeto.. Es decir que todo algoritmo calcula una función f:N----N donde cada número natural es la codificación de un problema o de una solución.

En ocasiones los algoritmos son susceptibles de nunca terminar, por ejemplo, cuando entran a un bucle infinito. Cuando esto ocurre, el algoritmo nunca devuelve ningún valor de salida, y podemos decir que la función queda indefinida para ese valor de entrada. Por esta razón se considera que los algoritmos son funciones parciales, es decir, no necesariamente definidas en todo su dominio de definición.

Cuando una función puede ser calculada por medios algorítmicos, sin importar la cantidad de memoria que ocupe o el tiempo que se tarde, se dice que dicha función es computable. No todas las funciones entre secuencias datos son computables.

Ciclo Hamiltoniano

Funciones definidas por el usuario.

 Se crea para cubrir necesidades que están fuera del alcance de las funciones estándar. Cada función tiene una misión muy concreta, de modo que nunca tiene un número de líneas excesivo y siempre se mantiene dentro de un tamaño manejable. Es muy frecuente que al hacer una modificación para añadir una funcionalidad o corregir un error, se introduzcan nuevos errores en partes del programa que antes funcionaban correctamente.

 Una misma puede ser llamada muchas veces en un mismo programa, e incluso puede ser reutilizada por otros programas. Una función es capaz de mantener una gran independencia con el resto del programa.

PROCEDIMIENTOS

—  Las funciones son muy útiles como herramientas de programación, pero tienen una seria limitación: sólo pueden devolver un resultado al algoritmo que las invoca. Y en muchas ocasiones es necesario devolver más de un resultado.

—  Para eso existen los procedimientos, también llamados subrutinas, que son, en esencia, iguales a las funciones.

EJEMPLO:

EVAP3

Bucle (programación)

Tambien llamado ciclo, en programación, es una sentencia que se realiza repetidas veces a un trozo aislado de código, hasta que la condición asignada a dicho bucle deje de cumplirse.

Es utilizado para hacer una acción repetida sin tener que escribir varias veces el mismo código, lo que ahorra tiempo, deja el código más claro y facilita su modificación en el futuro.

El bucle y los condicionales representan la base de la programación estructurada. Es una evolución del código ensamblador, donde la única posibilidad de iterar un código era establecer una sentencia jump (que en los lenguajes de programación fue sustituida por el "ir a" o GOTO).

BUCLES FINITOS

Los bucles definidos ejecutan instrucciones de código un número determinado de veces. Existen programas que requieren efectuar lo mismo una y otra vez hasta legar al número determinado. Los bucles son muy útiles pues al escribir el código a ser repetido solo una vez, se reduce la posibilidad de errores.

La forma de escribir un Bucle es por medio de la instrucción For…Next. Dentro de esta, se encuentra el código que se desea ejecutar una cantidad de veces específica

Ejemplo 1

Queremos realizar una animación en la que una bailarina se mueve sobre el escenario en una

dirección, luego se mueve en la dirección contraria y finalmente se para.

Pautas de implementación:

Abre un nuevo proyecto e importa un nuevo objeto: cassy-dancing-3. Sitúala

inicialmente en (-100, 100), apuntando en la dirección 90º. Usa una operación

de deslizar para moverla 100 pasos a la derecha, luego gírala 180º, y muévela

100 pasos a la izquierda.

Puedes bloquear las posibilidades de giro del objeto para que no se de la

vuelta el objeto y vaya boca abajo.

BUCLE INFINITO

Es un error que consiste en realizar un ciclo que se repite de forma indefinida ya que su condición para finalizar nunca se cumple.Debe contener condiciones que establezcan cuándo empieza y cuándo acaba, de manera que, mientras las condiciones se cumplan, ejecute una secuencia de código de manera repetitiva. En el caso de ciclo infinito, como la condición de finalización no se alcanza, el bucle sigue ejecutando el segmento de código indefinidamente.

EJEMPLO 2

#include
#include

int main(void)
{
int x = 0;
while(x < 10)
{
printf("\xadNo acabar\x82 nunca!\n");
}
return 0;
}

Se observa que la sentencia printf("\xadNo acabaré nunca!\n"); siempre se ejecuta porque la condición del bucle while() siempre es cierta, no existe una condición de salida que obligue al bucle a finalizar. Exactamente, no se alcanza la condición de salida. Si en el ejemplo anterior, dentro del bloque de código del bucle while, se encontrase la instrucción x++.

EVAP2

TOMA DE DECISION

Es el proceso mediante el cual se realiza una elección entre las opciones o formas para resolver diferentes situaciones de la vida en diferentes contextos: a nivel laboral, familiar, sentimental, empresarial (utilizando metodologías cuantitativas que brinda la administración). La toma de decisiones consiste, básicamente, en elegir una opción entre las disponibles, a los efectos de resolver un problema actual o potencial La toma de decisiones a nivel individual se caracteriza por el hecho de que una persona haga uso de su razonamiento y pensamiento para elegir una solución a un problema que se le presente en la vida; es decir, si una persona tiene un problema, deberá ser capaz de resolverlo individualmente tomando decisiones con ese específico motivo.

Es la elección de un camino a seguir, por lo que en un estado anterior deben evaluarse alternativas de acción. Si estas últimas no están presentes, no existirá decisión.

Es necesario conocer, comprender, analizar un problema, para así poder darle solución. En algunos casos, por ser tan simples y cotidianos, este proceso se realiza de forma implícita y se soluciona muy rápidamente, pero existen otros casos en los cuales las consecuencias de una mala o buena elección pueden tener repercusiones en la vida y si es en un contexto laboral en el éxito o fracaso de la organización, para los cuales es necesario realizar un proceso más estructurado que puede dar más seguridad e información para resolver el problema.

Simples

 Lo que se hace es EVALUAR la condición, si la condición es verdadera realiza la acción, en caso contrario termina el programa. Es con una condición.

La estructura de selección simple permite ejecutar una acción o un grupo de acciones sólo si se cumple una determinada condición. Así, en el gráfico, si la condición es verdadera se ejecuta la acción acciona; en caso contrario, no se hace nada.

Por ejemplo, si se desea cambiar el signo de un número únicamente en caso que sea negativo, podemos escribir:

SI( numero < 0 )
    numero = -1 * numero

Si el número no es negativo, simplemente esta estructura se pasaría por alto y se continuaría en la siguiente instrucción después del SI.

EJERCICIO 1

Doble

 Luego de evaluar una condición si esta se cumple, es decir si es verdadera realiza una serie de acciones, y si esta es falsa se realiza otra serie de acciones distinta a la primera. Es con dos decisiones con el sí o con el no.

La estructura de selección doble permite seleccionar una ruta de dos rutas posibles en base a la verdad o falsedad de una condición. Así, en la Figura, si la condición es verdadera, se ejecuta la acción A; en caso contrario, se ejecuta la acción B.

En la Figura se muestra el diagrama de flujo y el pseudocódigo de la estructura de selección doble.

Por ejemplo, la siguiente estructura de selección doble determina si una persona es mayor o menor de edad:

SI( edad >= 18 )
    estado = "Mayor de edad"
SINO
    estado = "Menor de edad"

Esto imprime "Mayor de edad" si la persona tiene 18 años ó más e imprime "Menor de edad" si la persona tiene menos de 18 años. En cualquiera de los casos, después de efectuar la impresión, se ejecutará la primera instrucción que sigue a la estructura SI...SINO. 

EJECICIO 2

Triple

 Se realiza a partir de anidar estructuras simples y/o dobles, de manera tal que se realicen diferentes acciones con base a varias comparaciones, así habrá tantas opciones como se requieran. Es con tres decisiones a más toma de decisiones.

La estructura de selección de triple está formada por varias estructuras de selección doble SI-SINO puestas una a continuación de otra de forma que aun SI-SINO le sigue otro SI-SINO.

En la estructura triple las condiciones se evalúan en orden descendente, pasando de una condición a otra si la condición anterior resulta falsa. En el momento que se encuentra una condición verdadera, se efectúa la acción correspondiente a dicha condición y se corta el resto de la estructura. Si todas las condiciones resultan falsas, se efectúa la acción correspondiente al último SINO, que se considera como la acción por defecto.

Por ejemplo, la siguiente estructura de selección doble en cascada determina el signo de un número entre positivo, negativo o cero:

SI(n > 0 )    
    signo = "Positivo"
SINO
    SI( n < 0 )
        signo = "Negativo"
    SINO       
        signo = "Cero"

Usando el otro formato tendríamos:

SI( n > 0 )    
    signo = "Positivo"
SINO SI( n < 0 )
    signo = "Negativo"
SINO       
    signo = "Cero"

 EJERCICIO 3

EVAP1

ALGORITMO DE UNA RUTINA CASERA

LAVADO DE PRENDAS EN LA LAVADORA

DECLARACION:

Detergente, agua, lavadora, suavizante, las prendas (de algodón y los tejidos, los tejidos sintéticos o diferentes tipos de tejidos y las prendas de lana o delicadas)

ASIGNACION:

o   Detergente (1taza pequeña)

o   Suavizante (normalmente es una tapa llena)

o   La ropa sucia (solo debe llegar a la mitad de la lavadora)

o   Agua (depende el tanque de la lavadora que debe llenarse)

PROCESO:

      Primero separar las prendas de color y las blancas.

            Poner las prendas dentro de la lavadora.
Prender la lavadora y colocar el nivel del agua en alto, medio o bajo, que correspona con la parte del tamque que debe llenarse para lavar la ropa.
Echar el detergente y vierte el detergente directamente en el deposito de la lavadora
Echar la cantidad indicada del suavizante
Vierte el suavizante en el dispensador que se encuentra en el centro del agitador
Cierra la tapa de la lavadora
Active la programación del lavado y enjuague teniendo en cuenta:

·         Las prendas de algodón y los tejidos resistentes se pueden poner en el programa más largo, que tiene un centrifugado normal.

·         Los tejidos sintéticos o las mezclas de diferentes tipos de tejidos tienen un programa más corto, con un centrifugado reducido.

·         Las prendas de lana o delicadas tienen un programa específico con una fase de centrifugado muy corta o inexistente.

RESULTADO:

Las prendas ya están limpias y listas para ser tendidas en el cordel.
FIN DEL LAVADO
Si sobro prendas sucias todavía, vuelva a seguir las indicaciones.