Algoritmo
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Algoritmo as PDF for free.
More details
- Words: 2,089
- Pages: 9
CONCEPTOS BÁSICOS Un algoritmo es una serie de instrucciones que realizadas en orden conducen a la solución de un problema. También se puede decir que un algoritmo es la fase preliminar a escribir un programa en cualquier lenguaje de programación, por lo que la forma de escribirlo puede ser muy personal según el programador que lo esté diseñando, pero en general se debe hacer en una forma tan clara que cualquier otro programador pueda coger dicho algoritmo, entenderlo fácilmente y poderlo traducir a su lenguaje de programación favorito. El programador de computadoras es ante que nada una persona que resuelve problemas, por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. RESOLUCION DE PROBLEMAS Programación: Establecer una secuencia de acciones que tras ser ejecutadas por un procesador resuelva un determinado problema. Fases: 1. Análisis del problema 2. Estudio de su solución 3. Diseño del Algoritmo 4. Codificación del programa 5. Depuración y prueba Ejemplo: a)Diseño del Algoritmo 1. Tomar un vaso. 2. Colocar algunos cubitos de hielo en el vaso. 3. Echar vino tinto en el vaso. 4. Añadir gaseosa al contenido del vaso. 5. Agitar el contenido.
b) Diseño del Algoritmo 1. Tomar un vaso vacío. 2. Colocar tres cubitos de hielo en el vaso. 3. Echar vino tinto hasta la mitad del vaso. 4. Añadir gaseosa hasta llenar el vaso. 5. Agitar tres segundos el contenido. c)Diseño del Algoritmo
1
1. Tomar un vaso vacío. 2. Colocar tres cubitos de hielo en el vaso. a) Sacar la cubitera del congelador. b) Rociar la parte inferior con agua. c) REPETIR d) Extraer un cubito. e) Echarlo al vaso. f) HASTA QUE el no de cubitos sea 3. g) Rellenar los huecos de la cubitera con agua. h) Meter de nuevo la cubitera en el congelador. 3. Echar vino tinto hasta la mitad del vaso. 4. Añadir gaseosa hasta llenar el vaso. 5. Agitar tres segundos el contenido. DEFINICIONES Procesador: Entidad capaz de entender una secuencia finita de acciones y ejecutarlas en la forma en que se especifican Entorno: Conjunto de condiciones necesarias para la ejecución de un algoritmo Acciones primitivas: Son acciones que el procesador es capaz de entender y ejecutar directamente Algoritmo Dado un procesador y un entorno bien definido, es el enunciado de una secuencia finita de acciones primitivas que resuelven un determinado problema
2
TIPOS DE PROGRAMACIÓN En general, hay varias formas de escribir un algoritmo, pero explicaremos las dos mas conocidas: Diagrama de Flujo Que consta de rectángulos que encierran las instrucciones y líneas que apuntan hacia la siguiente instrucción de modo que no se pierda el orden. Además, las operaciones elementales como la entrada de datos, salida de datos, ciclos, etc. se reconocen de las demás instrucciones porque no se encierran en rectángulos sino en otra clase de figuras por lo que según la figura en la que esté encerrada la instrucción se reconoce su significado; Es muy didáctico, por lo que es muy fácil de entender así ni siquiera se conozca al programador que diseñó el algoritmo. Ejemplo: Hacer un programa que me muestre la suma de dos valores
Pseudocodigo En el pseudocodigo, cada instrucción es una línea y las operaciones elementales se escriben de una forma tan clara que será imposible que algún programador no las entienda. Aquí utilizaremos un pseudocodigo un poco personalizado, para hacer más sencilla la explicación. NOTA: Aunque normalmente, en el pseudocodigo, cada línea escrita es una instrucción diferente, a veces, no se puede escribir en una sola línea todo el contenido de una instrucción por lo que si se quiere dividir una instrucción en dos o más líneas diferentes deberán estar unidas por el signo “_” al final, que indicará que la línea que está bajo hace parte de la misma instrucción y no de otra diferente. Para realizar dichas instrucciones, se utilizan básicamente Variables y Operadores. Ejemplo: Hacer un programa que me muestre la suma de dos valores
3
INICIO DECLARAR VARIABLES NUM1, NUM2, SUMA Leer <-- NUM1 Leer <-- NUM2 SUMA <-- NUM1+NUM2 Mostrar --> SUMA FIN PASOS PARA DISEÑAR UN ALGORITMO Aunque no hay un método general para diseñar algoritmos, si se puede decir que lo más adecuado es seguir con los siguientes pasos al tratar de resolver un problema determinado: 1.
EL ANÁLISIS: Es importantísimo hacer un buen análisis de cual es específicamente el problema a resolver. Para esto es bueno ayudarse mediante gráficos del problema o en caso de que no sea graficable, también se puede resolver el problema para casos específicos y luego generalizarlo para todos los posibles casos.
También se deben observar cuales serían los casos especiales, es decir, aquellos casos que no cumplan la norma general, y tratar de evaluarlos de otra forma.
Este paso es el que más tiempo debe llevarle a un buen programador, ya que de un buen análisis depende los buenos resultados que arroje el algoritmo. 2.
ESCRIBIR EL ALGORITMO: Después de haber analizado el problema en una forma abstracta, se debe llevar al papel, mediante instrucciones adecuadas al análisis. Si el problema fue bien analizado, este paso es muy rápido a comparación del anterior.
3.
PRUEBA DE ESCRITORIO: Este paso es opcional y se aplica siguiendo paso por paso las instrucciones del algoritmo, anotando los diferentes valores que van tomando las variables, de forma que se pueda verificar si hay errores en alguna instrucción. Obviamente, éste método es muy engorroso para algoritmos muy extensos, por lo que en estos casos no sería aplicable.
DIAGRAMA DE FLUJO
4
Un Diagrama de Flujo representa la esquematización gráfica de un algoritmo, el cual muestra gráficamente los pasos o procesos a seguir para alcanzar la solución de un problema. También se puede decir que, es un esquema para representar gráficamente un algoritmo. Se basan en la utilización de diversos símbolos para representar operaciones específicas. Se les llama diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de operación. Para hacer comprensibles los diagramas a todas las personas, los símbolos se someten a una normalización; es decir, se hicieron símbolos casi universales, ya que, en un principio cada usuario podría tener sus propios símbolos para representar sus procesos en forma de Diagrama de Flujo. Esto trajo como consecuencia que solo aquel que conocía sus símbolos, los podía interpretar. La simbología utilizada para la elaboración de diagramas de flujo es variable y debe ajustarse a un patrón definido previamente. SIMBOLOGÍA Indica el INICIO y el FIN de un algoritmo. PROCESO, indica que se procesara una operación, ya sea matemática, lógica de asignación, etc. PROCEDIMIENTO, indica que se ejecutará otro algoritmo fuera del cuerpo principal, digamos un Sub algoritmo. TECLADO, indica que se ingresara información por teclado. DECISIÓN, elabora un proceso lógico, este símbolo nos permitirá que nuestro algoritmo tome dos caminos según el resultado lógico. Si es verdadero hará cierta secuencia de procedimientos, caso contrario hará otros. CONECTOR, indica el final de una estructura, ya sea de decisión o de control. CONECTOR, indica la continuación de un algoritmo, cuando nos falte hoja para continuar nuestro algoritmo, utilizamos este símbolo para indicarle que continua en otra parte de nuestra hoja. IPANTALLA, nos indica que mostrara el resultado de un algoritmo por pantalla.
5
IMPRESIÓN, nos indica que mostrará el resultado de un algoritmo por impresora. FOR, hace una serie de procedimientos dentro de su estructura según la cantidad de veces especificadas desde el principio. MIENTRAS, hace una serie de procedimientos mientras el valor lógico sea verdadero, cuando es falso el bucle lógico termina. LINEAS, indica la direccionalidad de nuestro algoritmo, nos permite tener un orden lógico a nuestra programación.
ESTRUCTURAS ALTERNATIVAS Determinan la ejecución de una u otra parte del programa dependiendo de que se cumpla o no una cierta condición. A su vez las estructuras alternativas se subdividen en simples, dobles, etcétera como veremos a continuación.. Alternativa simple Si se cumple una determinada condición se ejecutará un conjunto de instrucciones (que en caso contrario no se ejecutarían). Pseudocódigo: Si (condicion) { instrucciones } Lenguaje C: if (condición) { instrucciones };
Donde: - condición es cualquier expresión que devuelva un valor lógico (true/false). - instrucciones es un bloque de una o más instrucciones que se ejecutarán solo en el caso de que se cumpla la condición.
6
Alternativa doble Si se cumple la condición se ejecutará el primer bloque de instrucciones, si no se cumple se ejecutará el segundo bloque. Pseudocódigo: Si (condicion) { Instrucciones1 } sino { Instrucciones2 } Lenguaje C: if (condición) { instrucciones1 } else { instrucciones2 }; Estructuras repetitivas En ocasiones necesitaremos que un bloque de instrucciones se ejecute varias veces seguidas; en estos casos utilizaremos estructuras repetitivas o bucles. Estructura while (mientras). La estructura while ejecuta un bloque de instrucciones y repite dicha ejecución mientras que se cumpla una condición. Pseudocódigo: Mientras (condicion) { Instrucciones } Lenguaje C: while(condición) { instrucciones }
7
Donde: - condición es la condición cuyo valor deberá ser true para que se produzca la entrada en el bucle y que será comprobado antes de cada nueva ejecución del bloque de instrucciones.
-
instrucciones es el bloque de instrucciones que se ejecutará.
Funcionamiento: 1.- Al encontrar la estructura while lo primero que hace (antes de entrar por primera vez en el bucle) es evaluar la condición: si es verdadera entra en el bucle y ejecuta el bloque de instrucciones, pero si es falsa ni siquiera llegará a entrar en el bucle. 2.- Una vez ejecutadas las instrucciones del bucle se evalúa de nuevo la condición para determinar si se vuelve a ejecutar el bloque o no (si es verdadera se ejecuta, si es falsa deja de ejecutarse). Este punto se repite hasta que la condición deja de ser verdadera. 3.- Cuando al evaluar la condición el resultado es false, el flujo del programa va a la línea siguiente al final del bucle. Observaciones: • Debemos asegurarnos de que en algún momento se produzca la salida del bucle ya que de lo contrario estaríamos ante un bucle sin fin. Por ejemplo, si en lugar de la condición while (Nota < 0 || Nota > 10) hubiésemos escrito: while (Nota > 0 || Nota < 10) el bucle hubiese estado iterando constantemente y no finalizaría nunca. • Para que esta salida se produzca se deberá modificar el valor de la expresión. En nuestro caso la modificación se produce al leer un nuevo valor del teclado. • Se puede forzar una salida del bucle en cualquier momento mediante la cláusula break. • También se puede forzar a realizar un nuevo ciclo aún sin terminar todas las instrucciones del bucle mediante la cláusula continue. Pero ninguna de estas dos últimas opciones es recomendable ya que dificultan la legibilidad de los programas y, por tanto, su posterior mantenimiento. Estructura do..while. (hacer mientras) La estructura do..while es similar a la anterior pero en este caso la comprobación se produce después de ejecutar el bloque de instrucciones.
8
Pseudocódigo: Hacer { } mientras (condición)
instrucciones
Lenguaje C: Do { instrucciones } while(condicion)
La única diferencia entre la estructura while y la estructura do..while está en la primera vez que se ejecuta el bucle: - la estructura while comprueba la condición antes de entrar por primera vez en el bucle y si la condición no se cumple, no entrará. - la estructura do..while ejecuta el bucle la primera vez sin comprobar la condición. Para las demás iteraciones el funcionamiento es idéntico en ambas estructuras (únicamente se producen variaciones en el caso de utilizar la cláusula continue). Estructura for (para). La estructura for ejecuta un bucle un número determinado de veces controlando automáticamente el número de iteraciones. La utilizaremos siempre que sepamos previamente el número de veces que se ejecutará el bucle. Su formato genérico es el siguiente: condiciónContinuaciÓn; ExpresiónIncremento) { instrucciones ... } Donde: - VariableControl: es una variable interna o local al bucle (no hay que declararla previamente) que se utiliza normalmente como contador del numero de ejecuciones del bucle en cada momento. - ValorInicio: es el valor inicial que tomará la VariableControl. - CondicionContinuacion: es una condición que será comprobada antes de realizar cada ejecución del bucle. Si se cumple, se ejecutará el bloque de instrucciones; en caso contrario pasará el control a la línea siguiente al final de la estructura. - ExpresionIncremento: es una expresión que modificará el valor de la variable de control. Normalmente se trata de una simple suma pero puede ser cualquier expresión que permita en algún momento la salida del programa.
9
b) Diseño del Algoritmo 1. Tomar un vaso vacío. 2. Colocar tres cubitos de hielo en el vaso. 3. Echar vino tinto hasta la mitad del vaso. 4. Añadir gaseosa hasta llenar el vaso. 5. Agitar tres segundos el contenido. c)Diseño del Algoritmo
1
1. Tomar un vaso vacío. 2. Colocar tres cubitos de hielo en el vaso. a) Sacar la cubitera del congelador. b) Rociar la parte inferior con agua. c) REPETIR d) Extraer un cubito. e) Echarlo al vaso. f) HASTA QUE el no de cubitos sea 3. g) Rellenar los huecos de la cubitera con agua. h) Meter de nuevo la cubitera en el congelador. 3. Echar vino tinto hasta la mitad del vaso. 4. Añadir gaseosa hasta llenar el vaso. 5. Agitar tres segundos el contenido. DEFINICIONES Procesador: Entidad capaz de entender una secuencia finita de acciones y ejecutarlas en la forma en que se especifican Entorno: Conjunto de condiciones necesarias para la ejecución de un algoritmo Acciones primitivas: Son acciones que el procesador es capaz de entender y ejecutar directamente Algoritmo Dado un procesador y un entorno bien definido, es el enunciado de una secuencia finita de acciones primitivas que resuelven un determinado problema
2
TIPOS DE PROGRAMACIÓN En general, hay varias formas de escribir un algoritmo, pero explicaremos las dos mas conocidas: Diagrama de Flujo Que consta de rectángulos que encierran las instrucciones y líneas que apuntan hacia la siguiente instrucción de modo que no se pierda el orden. Además, las operaciones elementales como la entrada de datos, salida de datos, ciclos, etc. se reconocen de las demás instrucciones porque no se encierran en rectángulos sino en otra clase de figuras por lo que según la figura en la que esté encerrada la instrucción se reconoce su significado; Es muy didáctico, por lo que es muy fácil de entender así ni siquiera se conozca al programador que diseñó el algoritmo. Ejemplo: Hacer un programa que me muestre la suma de dos valores
Pseudocodigo En el pseudocodigo, cada instrucción es una línea y las operaciones elementales se escriben de una forma tan clara que será imposible que algún programador no las entienda. Aquí utilizaremos un pseudocodigo un poco personalizado, para hacer más sencilla la explicación. NOTA: Aunque normalmente, en el pseudocodigo, cada línea escrita es una instrucción diferente, a veces, no se puede escribir en una sola línea todo el contenido de una instrucción por lo que si se quiere dividir una instrucción en dos o más líneas diferentes deberán estar unidas por el signo “_” al final, que indicará que la línea que está bajo hace parte de la misma instrucción y no de otra diferente. Para realizar dichas instrucciones, se utilizan básicamente Variables y Operadores. Ejemplo: Hacer un programa que me muestre la suma de dos valores
3
INICIO DECLARAR VARIABLES NUM1, NUM2, SUMA Leer <-- NUM1 Leer <-- NUM2 SUMA <-- NUM1+NUM2 Mostrar --> SUMA FIN PASOS PARA DISEÑAR UN ALGORITMO Aunque no hay un método general para diseñar algoritmos, si se puede decir que lo más adecuado es seguir con los siguientes pasos al tratar de resolver un problema determinado: 1.
EL ANÁLISIS: Es importantísimo hacer un buen análisis de cual es específicamente el problema a resolver. Para esto es bueno ayudarse mediante gráficos del problema o en caso de que no sea graficable, también se puede resolver el problema para casos específicos y luego generalizarlo para todos los posibles casos.
También se deben observar cuales serían los casos especiales, es decir, aquellos casos que no cumplan la norma general, y tratar de evaluarlos de otra forma.
Este paso es el que más tiempo debe llevarle a un buen programador, ya que de un buen análisis depende los buenos resultados que arroje el algoritmo. 2.
ESCRIBIR EL ALGORITMO: Después de haber analizado el problema en una forma abstracta, se debe llevar al papel, mediante instrucciones adecuadas al análisis. Si el problema fue bien analizado, este paso es muy rápido a comparación del anterior.
3.
PRUEBA DE ESCRITORIO: Este paso es opcional y se aplica siguiendo paso por paso las instrucciones del algoritmo, anotando los diferentes valores que van tomando las variables, de forma que se pueda verificar si hay errores en alguna instrucción. Obviamente, éste método es muy engorroso para algoritmos muy extensos, por lo que en estos casos no sería aplicable.
DIAGRAMA DE FLUJO
4
Un Diagrama de Flujo representa la esquematización gráfica de un algoritmo, el cual muestra gráficamente los pasos o procesos a seguir para alcanzar la solución de un problema. También se puede decir que, es un esquema para representar gráficamente un algoritmo. Se basan en la utilización de diversos símbolos para representar operaciones específicas. Se les llama diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de operación. Para hacer comprensibles los diagramas a todas las personas, los símbolos se someten a una normalización; es decir, se hicieron símbolos casi universales, ya que, en un principio cada usuario podría tener sus propios símbolos para representar sus procesos en forma de Diagrama de Flujo. Esto trajo como consecuencia que solo aquel que conocía sus símbolos, los podía interpretar. La simbología utilizada para la elaboración de diagramas de flujo es variable y debe ajustarse a un patrón definido previamente. SIMBOLOGÍA Indica el INICIO y el FIN de un algoritmo. PROCESO, indica que se procesara una operación, ya sea matemática, lógica de asignación, etc. PROCEDIMIENTO, indica que se ejecutará otro algoritmo fuera del cuerpo principal, digamos un Sub algoritmo. TECLADO, indica que se ingresara información por teclado. DECISIÓN, elabora un proceso lógico, este símbolo nos permitirá que nuestro algoritmo tome dos caminos según el resultado lógico. Si es verdadero hará cierta secuencia de procedimientos, caso contrario hará otros. CONECTOR, indica el final de una estructura, ya sea de decisión o de control. CONECTOR, indica la continuación de un algoritmo, cuando nos falte hoja para continuar nuestro algoritmo, utilizamos este símbolo para indicarle que continua en otra parte de nuestra hoja. IPANTALLA, nos indica que mostrara el resultado de un algoritmo por pantalla.
5
IMPRESIÓN, nos indica que mostrará el resultado de un algoritmo por impresora. FOR, hace una serie de procedimientos dentro de su estructura según la cantidad de veces especificadas desde el principio. MIENTRAS, hace una serie de procedimientos mientras el valor lógico sea verdadero, cuando es falso el bucle lógico termina. LINEAS, indica la direccionalidad de nuestro algoritmo, nos permite tener un orden lógico a nuestra programación.
ESTRUCTURAS ALTERNATIVAS Determinan la ejecución de una u otra parte del programa dependiendo de que se cumpla o no una cierta condición. A su vez las estructuras alternativas se subdividen en simples, dobles, etcétera como veremos a continuación.. Alternativa simple Si se cumple una determinada condición se ejecutará un conjunto de instrucciones (que en caso contrario no se ejecutarían). Pseudocódigo: Si (condicion) { instrucciones } Lenguaje C: if (condición) { instrucciones };
Donde: - condición es cualquier expresión que devuelva un valor lógico (true/false). - instrucciones es un bloque de una o más instrucciones que se ejecutarán solo en el caso de que se cumpla la condición.
6
Alternativa doble Si se cumple la condición se ejecutará el primer bloque de instrucciones, si no se cumple se ejecutará el segundo bloque. Pseudocódigo: Si (condicion) { Instrucciones1 } sino { Instrucciones2 } Lenguaje C: if (condición) { instrucciones1 } else { instrucciones2 }; Estructuras repetitivas En ocasiones necesitaremos que un bloque de instrucciones se ejecute varias veces seguidas; en estos casos utilizaremos estructuras repetitivas o bucles. Estructura while (mientras). La estructura while ejecuta un bloque de instrucciones y repite dicha ejecución mientras que se cumpla una condición. Pseudocódigo: Mientras (condicion) { Instrucciones } Lenguaje C: while(condición) { instrucciones }
7
Donde: - condición es la condición cuyo valor deberá ser true para que se produzca la entrada en el bucle y que será comprobado antes de cada nueva ejecución del bloque de instrucciones.
-
instrucciones es el bloque de instrucciones que se ejecutará.
Funcionamiento: 1.- Al encontrar la estructura while lo primero que hace (antes de entrar por primera vez en el bucle) es evaluar la condición: si es verdadera entra en el bucle y ejecuta el bloque de instrucciones, pero si es falsa ni siquiera llegará a entrar en el bucle. 2.- Una vez ejecutadas las instrucciones del bucle se evalúa de nuevo la condición para determinar si se vuelve a ejecutar el bloque o no (si es verdadera se ejecuta, si es falsa deja de ejecutarse). Este punto se repite hasta que la condición deja de ser verdadera. 3.- Cuando al evaluar la condición el resultado es false, el flujo del programa va a la línea siguiente al final del bucle. Observaciones: • Debemos asegurarnos de que en algún momento se produzca la salida del bucle ya que de lo contrario estaríamos ante un bucle sin fin. Por ejemplo, si en lugar de la condición while (Nota < 0 || Nota > 10) hubiésemos escrito: while (Nota > 0 || Nota < 10) el bucle hubiese estado iterando constantemente y no finalizaría nunca. • Para que esta salida se produzca se deberá modificar el valor de la expresión. En nuestro caso la modificación se produce al leer un nuevo valor del teclado. • Se puede forzar una salida del bucle en cualquier momento mediante la cláusula break. • También se puede forzar a realizar un nuevo ciclo aún sin terminar todas las instrucciones del bucle mediante la cláusula continue. Pero ninguna de estas dos últimas opciones es recomendable ya que dificultan la legibilidad de los programas y, por tanto, su posterior mantenimiento. Estructura do..while. (hacer mientras) La estructura do..while es similar a la anterior pero en este caso la comprobación se produce después de ejecutar el bloque de instrucciones.
8
Pseudocódigo: Hacer { } mientras (condición)
instrucciones
Lenguaje C: Do { instrucciones } while(condicion)
La única diferencia entre la estructura while y la estructura do..while está en la primera vez que se ejecuta el bucle: - la estructura while comprueba la condición antes de entrar por primera vez en el bucle y si la condición no se cumple, no entrará. - la estructura do..while ejecuta el bucle la primera vez sin comprobar la condición. Para las demás iteraciones el funcionamiento es idéntico en ambas estructuras (únicamente se producen variaciones en el caso de utilizar la cláusula continue). Estructura for (para). La estructura for ejecuta un bucle un número determinado de veces controlando automáticamente el número de iteraciones. La utilizaremos siempre que sepamos previamente el número de veces que se ejecutará el bucle. Su formato genérico es el siguiente: condiciónContinuaciÓn; ExpresiónIncremento) { instrucciones ... } Donde: - VariableControl: es una variable interna o local al bucle (no hay que declararla previamente) que se utiliza normalmente como contador del numero de ejecuciones del bucle en cada momento. - ValorInicio: es el valor inicial que tomará la VariableControl. - CondicionContinuacion: es una condición que será comprobada antes de realizar cada ejecución del bucle. Si se cumple, se ejecutará el bloque de instrucciones; en caso contrario pasará el control a la línea siguiente al final de la estructura. - ExpresionIncremento: es una expresión que modificará el valor de la variable de control. Normalmente se trata de una simple suma pero puede ser cualquier expresión que permita en algún momento la salida del programa.
9
