Informática y programación - mozart.dis.ulpgc.esmozart.dis.ulpgc.es/Gias/LibroIyP_Site/Mod2-Tema4.pdf · Ejercicios. 3 Grupo Docente IyP ... datos de entrada y los procesaparagenerar

Informática y Programación

Escuela de Ingenierías Industriales y Civiles

Curso 2010/2011

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

1

Módulo 2.Fundamentos de Programación

• Tema 1. Conceptos generales de algorítmica

• Tema 2. Sentencias de control

• Tema 3. Conjuntos dimensionados

• Tema 4. Programación modular

• Tema 5. Ficheros

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

2

CONTENIDO

PROGRAMACIÓN MODULAR

IntroducciónDefinicionesParámetros y variablesRecursividadVentajas de la programación modularAnálisis/Diseño modularEjercicios

3

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

• La solución de un problema complejo puede obtenerse amenudo a partir de la resolución de subproblemas mássimples (estrategia “divide y vencerás”).

• Análogamente, un algoritmo que resuelve un problemacomplejo puede expresarse en términos de subalgoritmosque resuelven problemas simples.

4

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Problema

Subproblemas

Subalgoritmos

Algoritmo

Introducción

Ejemplo: Cálculo del número combinatorio

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

5

Algoritmo Combinatorio_NoModularvariable entera n, k, i, num, denA , denB

Leer(n, k)num = 1, denA = 1, denB = 1

para i desde 1 hasta n hacernum = num*i

fin parapara i desde 1 hasta n-k hacer

denA = denA*ifin parapara i desde 1 hasta k hacer

denB = denB*ifin para

Escribir("Resultado: " , num/( denA*denB ) )fin Algoritmo

Solución no modular: Código redundante para realizar la misma tarea, en este caso el factorial de un número. Observa que sólo cambia la condición de parada.

( )!!!),(

knkn

kn

knC−

=

=

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

6

Algoritmo Combinatorio_Modular

Función entera Fact(n)variable entera n, i, ff=1para i desde 1 hasta n hacer

f=f*ifin paradevolver f

fin Función

variable entera n, kLeer(n, k)

Escribir("Resultado: " , Fact(n)/ (Fact(n-k)*Fact(k))fin Algoritmo

Solución modular: Subalgoritmo

La parte principal es mucho más compacta y simple en su lectura

( )!!!),(

knkn

kn

knC−

=

=

Definiciones• Un subalgoritmo es un conjunto de instrucciones

identificadas con un nombre único que toma una serie dedatos de entrada y los procesa para generar un resultado.

• Puede ser llamado o invocado desde un algoritmo o desde otros subalgoritmos (estructura jerárquica).

• Su uso reduce el algoritmo, simplificándolo ya que hace innecesaria la repetición de código para realizar una misma tarea.

• Dos tipos:• Funciones: retornan un valor.

• Procedimientos: no devuelven nada.

7

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

8

Función <tipo> <nombre> (<param>)<declaración_variables>

<cuerpo>devolver valor<cuerpo>

fin Función

Procedimiento <nombre> (<param>)<declaración_variables>

<cuerpo>retornar<cuerpo>

fin Procedimiento

• Estructura similar a un algoritmo: cabecera, declaración de variables y constantes, cuerpo y cierre.• Diferencias: la cabecera incluye una lista de parámetros y el

cuerpo contiene instrucciones de retorno, indicando además el valor a retornar en el caso de las funciones.

Sintaxis Función Sintaxis Procedimiento

Ejemplos

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

9

Algoritmo Prueba_Función

Función real Cuadrado (x)variable real x

devolver x*xfin Función

variable real y, z

Leer(z)y = Cuadrado(z)Escribir(“El cuadrado de ”, z, “es”, y)

fin Algoritmo

Algoritmo Prueba_Procedimiento

Procedimiento Escribe_Pot_23(x)variable real x

Escribir(“Cuadrado=”, x*x, “cubo=“, x*x*x)

retornarfin Procedimiento

variable real y

Leer(y)Escribe_Pot_23(y)

fin AlgoritmoInvocación

Declaración

Retorno

Ejemplos – ejecución 1

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

10




variable real y, z


fin Algoritmo

Se inicia la ejecución en el algoritmo principal


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

11




variable real y, z


fin Algoritmo

Continúa la ejecución en el algoritmo principal


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

12




variable real y, z


fin Algoritmo

Se produce la llamada a la función desde el algoritmo principal


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

13




variable real y, z


fin Algoritmo

Se suspende la ejecución en el algoritmo principal

La ejecución salta a la función


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

14




variable real y, z


fin Algoritmo

Algoritmo principal a la espera

Termina la ejecución en la función


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

15




variable real y, z


fin Algoritmo

Se reanuda la ejecución en el algoritmo principal, a la variable y se le asigna el valor retornado por la función

Parámetros y variables• En la declaración de un subalgoritmo se incluyen los

parámetros a través de los cuales se le suministran los datosde entrada.

• En el momento de la llamada se produce un intercambio deinformación entre los parámetros del subalgoritmo(parámetros formales) y las variables del algoritmo principal(parámetros reales).

• Además de los parámetros, pueden existir variables internasque son de ámbito local al subalgoritmo.

16

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Ejemplo

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

17


Función real Cuadrado (x)variable real xvariable real y

y=x*x;devolver y

fin Función

variable real y, z


fin Algoritmo

Parámetro real

Parámetro formal

Variable local a la función

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

18

• Existen dos modos de paso de parámetros:• Por valor: el contenido de los parámetros reales se copia a los

parámetros formales. Las modificaciones internas al subalgoritmono afectan a la variable externa. Pueden verse como parámetrosde entrada.

• Por referencia: se pasa una referencia a la dirección de memoriadel parámetro real. Si se modifica el parámetro formal semodifica la variable externa. Pueden verse como parámetros desalida o de entrada/salida.

• En la lista de parámetros, el paso por referencia se indicaanteponiendo ref al parámetro.

Paso de parámetros

Ejemplo

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

19


Procedimiento Pot_23(x, ref x2, ref x3)variable real x, x2, x3

x2 = x*x, x3 = x2*xx = 0retornar

fin Procedimiento

variablesreal y, y2, y3y = 7, y2 = 0, y3 = 0

Pot_23(y, y2, y3)Escribir(“V=”, y, “V^2=“, y2, “V^3=“, y3)

fin Algoritmo

Paso por valor

Paso por referencia

Modificación de variables interna al procedimiento

Inicialización

Ejemplo - continuación

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

20




fin Procedimiento



fin Algoritmo

Paso por valor

Paso por referencia

y 7

y2 0

y3 0

Estado de la memoria antes de la llamada


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

21




fin Procedimiento



fin Algoritmo

Paso por valor

Paso por referencia

y 7

y2, x2 0

y3, x3 0

x 7

Estado de la memoria al entrar en el procedimiento

x2 y x3 hacen referencia a la misma dirección que y2 e y3, respectivamente

x es una variable distinta sobre la que se copia el valor de y

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

22

• NOTA:• En realidad, el programa principal y las funciones

poseen espacios de memoria separados.

• Aquí se utiliza una representación simplificada a fin de facilitar la exposición.



Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

23




fin Procedimiento



fin Algoritmo

Paso por valor

Paso por referencia

y 7

y2, x2 49

y3, x3 343

x 0

Estado de la memoria tras ejecutar el cuerpo del procedimiento


Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

24




fin Procedimiento



fin Algoritmo

Paso por valor

Paso por referencia

y 7

y2 49

y3 343

Estado de la memoria al volver al programa principaly no ha

cambiado

y2 e y3 se han modificado

Recursividad• Una función recursiva es aquella que se llama a sí misma.

• Permite soluciones compactas para algunos problemas.

• La estructura de una función recursiva incluye siempre al menos una condición de salida o caso base y una o más llamadas recursivas.

25

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Función <tipo> FunRec(param)si <condición_sobre_param>

devolver <valor>si no

<modificar_param>resultado=<depende_de> FunRec(param)devolver resultado

fin sifin Función

Caso base

Llamada recursiva

Ejemplo: obtener el factorial de un número. n! = n*(n-1)*(n-2)…*1

0!=1

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

26

Función entera FactorialNoRec(n)variable entera n, i, fsi n<=1 entonces

devolver 1si no

f=1para i desde 1 hasta n hacer

f=f*ifin paradevolver f

fin sifin Función

Función entera FactorialRec(n)si n<=1 entonces

devolver 1si no

devolver n*FactorialRec(n-1)fin si

fin Función

Solución no recursiva

Solución recursiva

Ventajas de la programación modular• Facilita la programación: Es más sencillo resolver varios

problemas simples que uno complejo.

• Mayor claridad: Programación estructurada en bloques y código más compacto.

• Ahorro de tiempo: Cada parte de la solución puede desarrollarse independientemente en paralelo.

• Facilita la modificación/mantenimiento.

• Permite la reutilización del código: Empaquetado de funciones y procedimientos en librerías o bibliotecas reutilizables.

27

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

• Una librería es un conjunto de funciones y procedimientos con un nexo común que se empaquetan para su reutilización.• Ejemplos: funciones gráficas, entrada/salida, matemáticas, etc.

28

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Librería genérica

Problema A

Problema B

Problema C

Librerías

Análisis/Diseño modular• Aspectos específicos a considerar:

• Identificación de subproblemas: ¿puede el problema descomponerse en problemas más simples? ¿Pueden, a su vez, dichos subproblemas descomponerse? (estructura jerárquica)

• Planteamiento de la solución: ¿cómo se obtiene la solución global a partir de las particulares?

• Identificación de funciones/procedimientos y sus parámetros.

• Generación de librerías: ¿son los subalgoritmos de utilidad para otros problemas?

29

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

• Características deseables de los subalgoritmos:• Caja negra: la salida solo depende de los parámetros de entrada.

• Número reducido de parámetros de entrada.

• Pocas líneas de código y simplicidad.

• Evitar demasiados niveles de jerarquía en la solución (hay que llegar a un compromiso con la anterior).

30

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1Características deseables

Estudio de casos: Ejemplo 1• Estamos diseñando el software para una empresa de ámbito

nacional. El precio final de cada uno de los productos que comercializa se obtiene añadiendo al precio de partida los impuesto locales de la región de venta. Analizar este aspecto desde la perspectiva de la programación modular.

31

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

FacturaciónContabilidad

Publicidad

Ejemplo 1 - continuación• A) Subproblemas y solución

• El cálculo del precio es una operación que con total seguridad se requerirá en múltiples puntos del software.

• Si no se usase un subalgoritmo para realizarla, cualquier cambio en la forma en que se computa el precio sería costoso de aplicar, ya que requiere modificar todos y cada uno de los puntos donde se aplica el cálculo del precio.

32

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Cálculo precio


Publicidad

CPrecio

CPrecioCPrecio

Ejemplo 1 - continuación• B) Funciones/Procedimientos y parámetros

• Se puede emplear una función que tome como datos de entrada el precio y la región de venta y devuelva el precio final.

33

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Función real CalculaPrecioFinal(precio, región)variable real preciovariable entera regiónvariable real impuesto

según región hacercaso 1, impuesto = 4.5 // Canariascaso 2, impuesto = 5.5 // Andalucía…otro caso, impuesto = 5.0

fin segúndevolver precio*(1+impuesto/100)

fin Función

Ejemplo 1 - continuación• Si el cálculo de los impuestos fuese necesario para otros algoritmos,

podría codificarse también como una función independiente.

34

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Función real CalculaImpuesto(región)

variable entera regiónvariable real impuesto

según región hacercaso 1, impuesto = 4.5 // Canariascaso 2, impuesto = 5.5 // Andalucía…otro caso, impuesto = 5.0

fin segúndevolver impuesto

fin Función

• Jerarquía:

35

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Cálculo precio


Publicidad

Cálculo impuesto

Ejemplo 1 - continuación

Estudio de casos: Ejemplo 2• Tenemos que escribir diferentes algoritmos para realizar

operaciones con vectores y matrices, pidiendo los datos por teclado y mostrando el resultado por pantalla: sumas, restas, multiplicaciones, divisiones, producto escalar, etc.

36

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Algoritmo SumaM

Algoritmo ProductoM

Algoritmo RestaM

Algoritmo PEscalarV

Algoritmo SumaV

Algoritmo DivisiónM

Estudio de casos: Ejemplo 2• A) Subproblemas y solución

• Todos los algoritmos requieren tres fases: lectura de datos, operación y escritura de resultados.

• La solución se obtiene encadenando secuencialmente las tres fases.

• Las fases de lectura y escritura son similares en muchos algoritmos.

37

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Lectura de matrices

Suma matricial

Escritura de matriz

Lectura de matrices

Producto matricial

Escritura de matriz

…

Algoritmo SumaM

Algoritmo ProductoM

Ejemplo 2 - continuación• B) Funciones/Procedimientos

• La fase de lectura pide datos al usuario y los devuelve en forma de vector o matriz → funciones o procedimientos con parámetros de entrada/salida para leer vectores y matrices (lee_vector, lee_matriz).

• La fase de escritura muestra resultados por pantalla → procedimientos para escribir vectores y matrices (escribe_vector, escribe_matriz).

• Las operaciones toman los datos para generar resultados, son comunes y seguramente las volvamos a necesitar → funciones o procedimientos diferentes para cada operación (suma_vectores, multiplica_matrices, etc).

38

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Funciones de lectura

Algoritmos

Funciones de

operación

Procedimientos de escritura

Ejemplo 2 - continuación• Podríamos pensar en una función de lectura genérica que

llamara a la función lee_matriz, que llamara a lee_vector por cada fila, esta a su vez a lee_elemento para cada posición y esta finalmente a lee_número.• Mala solución, demasiados niveles jerárquicos no justificados

pueden complicar el código.

39

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Funciones de lectura de números


de vectores


de matrices

Funciones de lectura de elementos

Función de lectura

Ejemplo 2 - continuación• Sí podría estar justificada la siguiente jerarquía:

• La división de matrices es un producto de una matriz por la inversa de la otra -> puede llamarse a la función producto matricial.

• La multiplicación de matrices consiste en una serie de productos escalares de vectores fila y columna -> puede llamarse a la función producto escalar.

40

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Función Producto Escalar

Función Producto Matricial

Función División Matricial

Ejemplo 2 - continuación• C) Parámetros – caso lee_matriz

• Este subalgoritmo de lectura necesita conocer las dimensiones de la matriz a leer, por lo que tomará dos parámetros de entrada: el número de filas y el número de columnas.

• Si se programa como función podría devolver un puntero a la matriz leída o bien un dato tipo matriz.

41

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Función ref entera lee_matriz (filas, columnas)...

• Si se programa como procedimiento se le pasa por referencia una matriz que luego se rellena con los datos introducidos por el usuario.

Procedimiento lee_matriz (filas, columnas, ref M)...

Ejercicios1. Escribir un algoritmo que realice la conversión de pulgadas a

centímetros utilizando una función. El factor de conversión es: 1pulgada = 2,54 cm.

2. Diseñar un algoritmo, que haciendo uso de una función, evalúe lasiguiente fórmula:

3. Escribir un algoritmo que use una función para convertir las letras de una cadena de caracteres de minúscula a mayúscula. Asumir por simplicidad que la cadena no contiene tildes, y que además de los caracteres solo contiene espacios en blanco.

4. Escribir un algoritmo que guarde en un vector los elementos de una matriz ordenados por filas, utilizando para ello subprogramas.

1 2 34 5 67 8 9

El vector resultante contendría : 1 2 3 4 5 6 7 8 9.42

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

( )( ) ( )( )

( )!2!2!2

!!!

nmnm

knknx

⋅−⋅⋅

+−

=

Ejercicios5. Escribir, usando subalgoritmos reutilizables,

A. Un algoritmo que lea una matriz e imprima los elementos sobre la diagonal principal. Ejemplo, para la matriz:

1 2 34 5 67 8 9

El resultado sería: 1 2 3 5 6 9.B. Un algoritmo que lea una matriz e imprima los elementos bajo la

diagonal secundaria. Para el ejemplo anterior el resultado sería: 3 5 6 7 8

6. Realizar un algoritmo que devuelva como resultado la traspuesta de una matriz de m filas y n columnas, considerando que m y n pueden no ser iguales. Utilizar subprogramas en la solución.

7. Escribir un algoritmo, haciendo uso de subprogramas, que sustituya una fila i de una matriz por la resta de esa fila con el producto de otra fila j por un factor c.

43

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Ejercicios8. Escribir un algoritmo que calcule el sumatorio de los n primeros

números enteros, haciendo uso de una función recursiva.

9. Escribir un algoritmo que dado un número x calcule su potencia p, utilizando para ello una función recursiva.

10. Escribir un algoritmo que calcule para dos números enteros n elevado a m, haciendo uso de una función recursiva.

11. Desarrollar un algoritmo recursivo que devuelva el enésimo número de la serie de Fibonacci.

44

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Bibliografía• Fundamentos de Informática y Programación para

Ingeniería. Ejercicios Resueltos para C y Matlab.Modesto Castrillón et al, Paraninfo, 2011.

• Introducción a la informática, A. Prieto Espinosa, A. LlorisRuiz, J.C. Torres Cantero, McGraw-Hill, Madrid, 1989.

45

Gru

po D

ocen

te Iy

P –

Dep

arta

men

to d

e In

form

átic

a y

Sist

emas

-20

10/1

1

Documents

Informática y programación - mozart.dis.ulpgc.esmozart.dis.ulpgc.es/Gias/LibroIyP_Site/Mod2-Tema4.pdf · Ejercicios. 3 Grupo Docente IyP ... datos de entrada y los procesaparagenerar