Download Algoritmos y Estructura de datos:

Algoritmos y Estructura de datos:
Definición de algoritmo
Un algoritmo es el conjunto de operaciones y procedimientos que deben seguirse para resolver un
problema. Un algoritmo recibe un conjunto de entradas, realiza ciertos procedimientos y devuelve
una salida.
Se dice que un algoritmo es correcto, si para cualquier conjunto de entradas el algoritmo siempre
nos dará la salida correcta.
Lo que pretende un algoritmo es sintetizar de alguna forma una tarea, cálculo o mecanismo antes de
ser transcrito al ordenador. Los pasos a seguir para resolver un algoritmo son los siguientes:
Análisis previo del problema.
Primera visión del método de resolución.
Descomposición en módulos.
Programación estructurada.
Búsqueda de soluciones parciales.
Ensamblaje de soluciones finales.
Un algoritmo tiene las siguientes características: es preciso, es definido y es finito.
Preciso. Se indica el orden en que deben seguirse los pasos.
Definido. Si se sigue el algoritmo varias veces proporcionandole los mismos datos, debemos
obtener siempre los mismos resultados.
Finito. El algoritmo debe terminar.
Ejemplos de algoritmos.
Ejemplo: Calcular las posibles raíces para una ecuación de segundo grado: ax2+bx+c=0
+-Algoritmo raíces
|
variables reales a,b,c,x,y
|
| Escribir "Introduzca los coeficientes de mayor a menor grado."
| Leer a,b,c
|
| +-Si sqr(b)>= 4*a*c entonces
| | x=(-b+sqrt(b^2-4*a*c))/2a
| +-Sino
| | Escribir "No existen raíces reales."
| +-Finsi
|
+-Final
Ejercicios.
1. Dados 3 números x,y,z devolver el mayor de los 3.
2. Explique como resolvería un problema en que dado cualquier valor entero calcule siempre el
valor absoluto de dicho valor
3. Como resolvería un problema en que dado un valor real cualquier, redondee dicho valor.
Diseño de algoritmos
En todo algoritmo se deben considerar tres partes:
Entrada. Información dada al algoritmo.
Proceso. Operaciones o cálculos para encontrar la solución al problema.
Salida. Respuestas dadas por el algoritmo o resultados finales de los cálculos.
Ejemplo. Calcular el área de un triángulo.
Datos de entrada. Base, altura.
Proceso. Calcular el area, multiplicando la base por la altura y dividiendo entre dos.
Salida. Salida en pantalla de la base, la altura y el área.
Ejemplo. Hacer un algoritmo para Ir al cine.
Datos de salida. Ver la película.
Datos de entrada. Nombre de la película, dirección de la sala, hora de proyección.
Datos Auxiliares. Entrada, número de asiento.
Descripción.
Debe seleccionarse la película de la cartelera, ir a la sala y comprar la entrada para finalmente
ver la película.
Algoritmo.
Inicio
tomar el periódico
mientras no lleguemos a la cartelera
pasar a la siguiente página
fin mientras
mientras todavía halla películas en la cartelera
leer película
si nos gusta
leer el título
recordar el título
fin si
fin mientras
Elegir una de las películas seleccionadas
Leer la dirección de la sala y la hora de proyección
si no hay entradas
terminar el algoritmo
si hay cola
ponerse al último de la cola
mientras no lleguemos a la taquilla
avanzar
si no hay entradas
terminar algoritmo
fin mientras
comprar boleto
leer el número de asiento
buscar el asiento
sentarse
ver la película
Fin
Ejercicios
1.
2.
3.
4.
5.
6.
Hacer un algoritmo para hacer una taza de cafe.
Hacer un algoritmo para poner la mesa de la cena.
Hacer un algoritmo para lavar los platos de la comida.
Hacer un algoritmo para cambiar una llanta ponchada.
Hacer un algoritmo para pagar una multa de tráfico.
Hacer un algoritmo para realizar una llamada telefónica (tomar en cuenta si es llamada por
cobrar o llamada normal por minuto)
La función módulo
Devuelve el resto de dividir un número por un divisor. Ejemplo mod(13,5)=3, mod(15,6)=3.
Ejercicio.
Como utilizarías la función mod para determinar si un entero dado es par o es impar. Discutir con
tus compañeros.
Algoritmo de euclides
El m.c.d de dos números es el mayor divisor entre ellos. Ejemplo m.c.d(10,32) = 2, m.c.d(81,15)=3,
y así sucesivamente.
Algoritmo de Euclides
Entrada: Valores a y b
Salida: Máximo Común Múltiplo
r0=a,
r1=b;
i=1
while (ri <>0)
ri+1= ri-1 mod ri
i=i+1
end while
return ri+1
Ejercicio.
El mínimo común múltiplo, es el menor múltiplo entre dos números m.c.m(10,5)=5,
mcm(6,20)=60. Explique como calcularía el mínimo común múltiplo dados dos enteros a y b.
Representación de algoritmos
Uno de los métodos más interesantes y más utilizados para la representación de algoritmos, son los
diagramas de flujo.
Un diagrama de flujo utiliza unos símbolos normalizados, con los pasos del algoritmo escritos en el
símbolo adecuado y los símbolos unidos por flechas, denominadas líneas de flujo, que indican el
orden en que los pasos deben ser ejecutados. En la siguiente tabla se especifican los principales
símbolos en un diagrama de flujo.
Inicio y fin del algoritmo
Proceso
Entrada / Salida
Decisión
Comentario
Símbolo
Función
Ejemplo: Para convertir de celcius a kelvin la fórmula es Kelvin= Celcius + 273.15. Hacer un
diagrama de flujo que cambie la temperatura de grados Celcius a kelvin.
Ejercicios
1. Hacer un algoritmo que reciba una cantidad en pesos e imprima su equivalente en dolares.
2. Hacer un algoritmo que diga si una palabra es un palíndromo. Un palíndromo es una palabra
que se lee igual tanto al derecho como al revés.
3. Hacer un algoritmo que calcule el M.C. D de dos números enteros.
4. Hacer un algoritmo que calcule el M.C. M de dos números enteros.
5. Hacer un algoritmo que lea un número entero, e imprima si dicho número es o no es primo.
Tipos de datos
Un dato es la expresión general que describe los objetos con los cuales opera el programa. En este
momento vamos a enfocarnos a trabajar con los datos estáticos, más adelante en el curso
hablaremos de los tipos de datos dinámicos.
Existen datos que pueden ser predefinidos como los enteros, los reales, lógicos y los caracteres.
Dependiendo del lenguaje de programación, un usuario tiene también la opción de definir sus
propios tipos de datos, y generalmente se definen agrupando tipos de datos primitivos.
Constantes
Las constantes son datos cuyo valor no cambia durante todo el transcurso del algoritmo. Los tipos
de constantes incluyen: numéricas enteras (int Dimension=5), numéricas reales (float PI=3.14),
lógicas (Verdadero=True), caracter (char Enter='c').
Variables
A diferencia de las constantes, las variables son datos que pueden cambiar su valor durante el
desarrollo del programa. Se identifican por su nombre y por su tipo. En el caso de C y Pascal las
variables deben ser declaradas al inicio del programa.
Expresiones
Es posible crear expresiones en base a los datos que el programa contiene. En la siguiente tabla se
describen los principales operadores en el lenguaje de programación C:
!
Operadores unarios
*,/,%, and
Operadores multiplicativos
+,-, or
Operadores aditivos
Operadores de compración
==.>,<,>=,<=
Ejemplo. Haga un programa que lea dos números, los sume, los múltiplique e imprima el
resultado.
#include <stdio.h>
int main()
{
int a,b;
int suma,mult;
printf("Dame el valor de a\n");
scanf("%d",&a);
printf("Dame el valor de b\n");
scanf("%d",&b);
suma=a+b;
mult=a*b;
printf("El valor de la suma es %d y de la multiplicación es %d\n",suma,mult);
return 0;
}
Ejemplo 2. Hacer un programa que lea el radio de un círculo y calcule su area:
#include "stdio.h"
int main()
{
const PI=3.14;
float radio,area;
printf("Dame el valor del radio\n");
scanf("%f",&radio);
area=PI*radio/2;
printf("El valor del area del circulo es %f \n",area);
return 0;
}
Ejercicios:
1.
2.
3.
4.
Hace un programa que lea 5 valores reales e imprima la media.
Hacer un programa que lea un valor en pesos y lo transforme a dolares. Utilice constantes
Hacer un programa que convierta de kilos a libras (1 libra=0.453592 kilos) utilice constantes
Hacer un programa que reciba como entrada un entero y calcule su valor elevado al
cuadrado.
5. Hacer un programa que resuelva una ecuación de segundo grado ax2+bx+c utilizando la
fórmula general. El programa solicita los valores de los coeficientes y calcula las raíces que
solucionan la ecuación. En caso de que no exista solución, imprimir un mensaje de error.
Estructuras de Control
En general, las instrucciones dentro de un programa se ejecutan una a una en el orden en que están
escritas. A esto se le conoce como ejecución secuencial. En los lenguajes de programación
estructurales permiten especificar que la siguiente instrucción a ejecutar es otra distinta de la que
sigue secuencialmente; a esto se le conoce como transferencia de control.
Estructuras selectivas
Se ejecutan las acciones según se cumpla determinada condición. La siguiente tabla nos ilustra la
sintaxis de dichas estructuras.
Tipo
Sintáxis
Ejemplo
Simples
If (expresion)
{
}
If (calificacion>60)
printf(“Aprobado”)
Dobles
If (expresion)
{
}
else
{
}
If (calificacion>60)
{
printf(“Aprobado”)
}
else
{
printf(“Reprobado”)
}
Múltiples
Switch (caso)
{
case caso1:
accion 1
accion 1
break;
case caso2:
accion 1
accion 1
break;
.
.
.
case cason:
accion 1
accion 1
break;
}
Switch (calificacion)
{
case 60: printf(“apenas”);
break;
case 70: printf(“Dos tres”)
break;
.
.
.
}
Ejercicio
1. Hacer un programa que pida 10 números enteros y al final imprima cuantos de dichos números
enteros fueron pares, y cuantos fueron impares.
Estructuras Repetitivas
Las estructuras de control repetitivas, son estructuras que se repiten siempre y cuando se cumpla
determinada condición.
La más común de este tipo de estructuras es la instrucción mientras (while) y la sintaxis es como
sigue:
while (expresion)
{
acciones
}
ejemplo
producto=2;
while (producto<100)
producto=2*producto;
Ejercicio:
1. Un grupo de 10 estudiantes realizó un examen. Usted tiene a su disposición las
calificaciones (enteros del 0 al 100). Determine el promedio de las calificaciones del grupo.
TAREA:
1. Diseñar un programa que a partir de una fecha intruducida en el teclado (dia, mes, año)
todos enteros, se obtenga la fecha del día siguiente: (ejemplo dime el día 29, dime el mes 08,
dime el año 2008, entonces el programa imprimirá la fecha del día siguiente es 30 de 08 de
2008.
2. Diseñar un programa que capture un número arbitrario de calificaciones, y calcule el
promedio de dichas calificaciones.
AYUDA: Utilice un ciclo while con centinelas.
3. Hacer un programa que dados dos enteros, calcule el máximo común divisor de ambos
números.
4. Utilice un programa que utilice un ciclo while para imprimir los enteros del 1 al 10
separados cada uno de ellos por 3 espacios en blanco. EJ. 1 2 3 4 5 ... 10
5. Escriba un programa que lea la longitud (en enteros de un cuadrado) y que dibuje el
cuadrado con asteriscos.
Ejemplo si el programa lee 5, deberá imprimir algo como lo siguiente:
*****
*
*
*
*
*
*
*****
6. Escriba un programa que lea números de 5 dígitos y determine si esos dígitos forman un
palíndromo (ejemplo 12321 si es palindromo, 11333 no es palindromo ).
1. Pista Utiliza los operadores de división y residuo para separar el número en dígitos
individuales.
7. Escriba un programa utilizando un ciclo while que dado un número entero n imprima el
factorial de dicho número.
Ciclo DO WHILE
El cliclo do while es una estructura repetitiva muy parecida al while y su formato es el siguiente:
do {
<sent 1>
<sent 2>
.
.
.
<sent N>
}while
Ejemplo
#include <stdio.h>
void main() {
int digito = 0;
int suma = 0, n = 7;
printf("Suma desde 0 hasta 7.\n");
do{
suma = suma + digito;
printf("Suma parcial hasta %d es: %d\n",digito++,suma);
} while (digito <= n);
printf("El resultado final es: %d\n",suma);
Como implementaría el mismo programa con un ciclo while? Qué diferencias puede observar?
Ciclo FOR
El ciclo for es una estructura repetitiva que nos permite establecer los límites inferiores y los límites
superiores. La estructura del mismo es:
for (x=limInf; x <= limSup; x++)
{
<sent 1>
<sent 2>
.
.
.
<sent N>
}
for (x=limSup; x >= limInf x--)
{
<sent 1>
<sent 2>
.
.
.
<sent N>
}
Ejemplo:
#include <stdio.h>
void main() {
int digito = 0;
int suma = 0;
printf("Suma desde 0 hasta 7.\n");
for (digito=0,digito<=7,digito++){
suma = suma + digito;
printf("Suma parcial hasta %d es: %d\n",digito,suma);
digito++;
}
printf("El resultado final es: %d\n",suma);
Ejercicios
1. Hacer un programa que calcule la suma 1 + 1/2+1/3+...+1/n donde el valor de n es
especificado por el usuario.
2. Se desea leer el valor de las calificaciones de 3 asignaturas de 10 estudiantes, y al final hacer
un promedio para cada una de las asignaturas.
(Ejemplo promedio calculo 7.4. Hint. Utilizar ciclos anidados)