programacio´n estructurada - wordpress.com › 2012 › 10 › tema-7-inform...bifurcacion´...

Tema 7

Programacion estructurada

Antes de comenzar a programar es preciso saber desarrollar algoritmos. Como se ha visto en eltema anterior, un algoritmo es una descripcion detallada de los pasos a seguir para resolver unatarea. Los pasos han de ser operaciones capaces de ser llevadas a cabo por el operador al cualva dirigido el algoritmo.

A fin de poder abordar problemas complejos es preciso aprender a disenar correctamentealgoritmos y sus diagramas respetando las reglas de la programacion estructurada. Para ellose presentan en este tema una serie de algoritmos basicos los cuales se han dividido en variosgrupos.

7.1 Fundamentos de la programacion estructurada

Es difıcil hacer un resumen de las ideas de la programacion estructurada a lectores que no tienencierta experiencia en programacion. Esto sucede porque la programacion estructurada pretendeevitar cierto tipo de situaciones que aparecen en programas grandes y medianos, pero que nose advierten en los ejemplos dados a principiantes. Una de estas situaciones es la siguiente: unprogramador escribe un diagrama de flujo tal y como aparece en la parte derecha de la figura 7.1.Transcurrido cierto tiempo, el mismo programador es requerido para realizar una modificacionen el mismo. Este intenta modificar el diagrama, pero la tarea le resulta ardua. Analizando losmotivos por los que el trabajo no avanza con rapidez se puede observar que:

• Es difıcil hallar el punto en el cual hay que eliminar un bloque o insertar uno nuevo, puestodo esta enmaranado.

• Incluso aunque el diagrama tuviera una mejor disposicion grafica, cuesta trabajo ver si

121

122 TEMA 7. PROGRAMACION ESTRUCTURADA

Figura 7.1: Diagrama de flujo estructurado (izquierda) y no estructurado (derecha).

una modificacion de una parte dara resultados indeseables en otra, debido al gran numerode interconexiones que hay.

Y los problemas no acaban ahı. Tras realizar los cambios, el programador debera probar elnuevo programa para comprobar su correcto funcionamiento. Cada vez que se detecte un errordebera volver a repetir el tedioso proceso de modificacion. Los problemas descritos no serıantales si el programador hubiera podido escribir el diagrama de flujo de forma parecida a la dela figura 7.1 (izquierda), en la que se aprecia que no existen cruces de lıneas y que cada modulotiene una entrada y una salida. Sobre estos dos aspectos se insistira mas adelante, por ahora noes necesario comentar mas las ventajas que para cualquier proyecto supone el tener programaslegibles y comprensibles.

7.1.1 Flujo lineal

Los diagramas se dice que tienen flujo lineal cuando no existen conexiones de vuelta atras olaterales. El flujo lineal se puede conseguir restringiendo las uniones entre bloques constructivosa estructuras de entrada unica y salida unica. Es decir, usando para la confeccion del diagramade flujo grupos de bloques a los cuales llega solo una flecha y de los cuales parte solo una flecha.La secuencia, la seleccion entre alternativas y la iteracion forman un conjunto suficiente demodulos constructivos para describir cualquier algoritmo. Es decir, es posible siempre realizar

c� MRA & JAAR 2010 DISA. ESI. US. 123

un diagrama de flujo que contiene solo las estructuras citadas. En la figura 7.2 se tienen talesestructuras; se puede ver que son de entrada unica y salida unica.

módulo 1

módulo 2 condición

cuerpo del bucle

sí

no

preguntasí no

opción 2opción 1

pregunta

cuerpo del bucle

sí

no

secuencia disyunción repetición con salidaen cola

repetición con salidaen cabeza

Figura 7.2: Construcciones o uniones de bloques permitidaspara programas estructurados.

Estas estructuras permitidas reciben los nombres que se indican a continuacion. De izquierdaa derecha en la citada figura 7.2 se tiene un par de bloques formando una secuencia, una bi-furcacion y bloques articulados en una estructura disyuntiva, una bifurcacion con conexionhacia atras formando un blucle o estructura repetitiva con salida en cola y, finalmente, unabifurcacion formando una estructura repetitiva con salida en cabeza.

En lo sucesivo se usaran estas estructuras (y ninguna otra) para realizar los diagramasde flujo, pero antes de pasar a los ejemplos es preciso comentar como se va a producir ladescomposicion del problema global en modulos.

7.1.2 Analisis descendente

En ocasiones se presenta la programacion estructurada como un conjunto de reglas a seguir. Enrealidad no hay una definicion exacta de programacion estructurada, por lo que las reglas sonsolo una aproximacion. Una idea importante de la programacion estructurada es el analisis

descendente o jerarquizado. Consiste este en identificar las funciones o tareas a cumplir porel programa desde un punto de vista global y proceder luego a descomponer estas funciones enotras menores. Estas a su vez se vuelven a descomponer en un proceso que termina cuando sealcanza el nivel del lenguaje o codigo usado. De este modo, el diseno del programa se realizapor niveles. Se comienza por el nivel mas general y se termina por lo particular o concreto.

El resultado del analisis descendente es un conjunto de diagramas que describen el algoritmocon un nivel de detalle creciente. En un primer nivel el diagrama de flujo puede tomar la formadada en la figura 7.3 en la parte superior. En un segundo nivel, cada uno de los modulos esdetallado en un diagrama aparte. El proceso continua mientras existan bloques que necesitenexplicaciones adicionales.


Inicio de lectura

de datos

Fin de lectura de

datos

...

Inicio de cálculo

de resultados

Fin de cálculo de

resultados

...

Inicio de

escritura de

resultados

Fin de escritura

de resultados

...

Inicio

Fin

Lectura de datos

Cálculo de

resultados

Escritura de

resultados

Figura 7.3: El analisis descendente aplicado a la confeccion de diagramas de flujo.


Es importante que antes de pasar al siguiente nivel se compruebe la validez del diagramaactual. Para ello se ha de comprobar que las construcciones utilizadas pertenecen al conjuntode las estructuras permitidas.

7.2 Calculos en secuencia

Los calculos en secuencia no presentan dificultad alguna desde el punto de vista algorıtmico.Los diagramas de flujo resultantes son lineales, sin bifurcaciones ni ciclos o repeticiones, y portanto de facil creacion.

Un programa evoluciona de modo lineal cuando realiza toda la secuencia de instrucciones deforma continua, sin saltos en la ejecucion. Este es el caso presentado en el ejemplo de la sumade dos numeros (ver figura 7.4). La realizacion y representacion en diagrama de flujo de estosprogramas es muy simple.

a Variable realprimer dato

b Variable realsegundo dato

c Variable realresultado, suma de a

y b

Escribir c

Leer a

Inicio

c a+b

Fin

Leer b

Figura 7.4: Diagrama de flujo de un algoritmo para sumar dos numeros.

7.2.1 Ejercicios

Se propone realizar el diagrama de flujo de algoritmos que resuelvan las tareas siguientes:

1. Leer dos valores reales p y q del teclado y escribir media aritmetica.

2. Leer un valor real x del teclado. Calcular y escribir r = x2 − 2x3.


3. Leer los coeficientes de un polinomio de grado tres de la forma P (x) = x3 + ax2 + bx + c.Leer a continuacion un cierto valor para la variable independiente x y calcular y escribiry = P (x).

4. Convertir a radianes un valor de angulo medido en grados sexagesimales.

5. Calcular y escribir la temperatura T que corresponde a un mol de gas ideal sometidoa una presion P cuando ocupa un volumen V . Se supone que los valores de P y V seproporcionan por teclado.

7.3 Estructuras selectivas

Las disyunciones o estructuras selectivas se construyen mediante un bloque bifurcacion conectadodos modulos que despues vuelven a unirse. En el interior de cada modulo puede haber otrasestructuras permitidas: secuencias, iteraciones, etc.

Las bifurcaciones permiten tomar un camino o su alternativa, permitiendo que el programadiscurra por uno de dos caminos posibles en funcion de condiciones. Un ejemplo muy simple esel siguiente: leer un numero real por teclado y escribir el valor absoluto del mismo. Una formade resolver el programa es mediante el diagrama de flujo de la figura 7.5. La idea es hacer quela secuencia de ejecucion pase por la escritura del numero o del numero cambiado de signo enfuncion de que sea positivo o negativo.

Nota importante: en este libro la palabra positivo se ha de entender como ”mayor que cero”quiere esto decir que el numero cero no forma parte del conjunto de los numeros positivos.

x Variable realdato

r Variable realresultado, valor

absoluto de x

Escribir

r

Leer x

Inicio

Fin

¿ x < 0 ?sí no

r -x r x

Figura 7.5: Diagrama de flujo con ruptura de secuencia.


Las bifurcaciones se pueden encadenar para dar solucion a situaciones mas complejas. Porejemplo considerese la funcion: NC(x, y), con (x, y) ∈ IR2 �→ c ∈ {1, 2, 3, 4}. Esta funcion calculael numero de cuadrante en que se encuentra el punto (x, y) de IR2. Se desea desarrollar unalgoritmo que lea las coordenadas x e y de un punto del plano (suponiendo que x �= 0 y quey �= 0) y calcule y escriba r =NC(x, y).

El diagrama de la figura 7.6 presenta una posible solucion mediante el uso de bifurcacionesen cascada.

Figura 7.6: Programa que escribe el cuadrante en el cual se situa el punto en el plano (x, y).

7.3.1 Ejercicios

Utilizando las ideas que se han presentado en los puntos anteriores desarrolle algoritmos queden solucion a los problemas siguientes:

1. Leer un numero real x y calcular y escribir r =| x |3.

2. Calcular el coste de una llamada telefonica que ha durado t minutos sabiendo que si t < 1el coste es de 0.4 euros mientras que para duraciones superiores el coste es 0.4 + (t− 1)/4euros.

3. Leer un numero real del teclado. Calcular el valor de p sabiendo que si x esta en elintervalo (2, 8] el resultado p toma el valor uno, en caso contrario toma el valor cero.Escribir posteriormente el valor de p.

4. Leer un valor x del teclado. Calcular y escribir el valor y = f(x) siendo f una funciondefinida a trozos del siguiente modo:


x f(x)x ∈ [−1, 3) 10− x

x > 50 1resto 0

5. Leer las componentes de un vector de IR2 (x e y). Calcule el valor de r que se define comor =NC(x, y) si x �= 0, y �= 0 y r = 0 si x = 0 o si y = 0.

7.4 Estructuras cıclicas

Muchos algoritmos requieren la repeticion de operaciones cierto numero de veces. Al conjunto deoperaciones que se repite se le llama cuerpo del proceso repetitivo. Un ciclo (o proceso repetitivoo bucle) queda completamente definido por el cuerpo y la condicion de parada o salida. Cadavez que el programa en ejecucion pasa por el cuerpo del bucle se dice que ha realizado unaiteracion.

La estructura denominada proceso repetitivo o bucle permite plasmar en diagramas de flujoeste tipo de procesos. La bifurcacion al final del bloque hace las veces de control de salida.En ocasiones es conveniente poner el control de salida en la cabeza del bucle, de este modo sepuede salir del bucle sin haber realizado ninguna operacion. Ambos tipos de proceso iterativosse muestran en la figura 7.7.

condición

cuerpo

sí

no

condición

cuerpo

sí

no

Figura 7.7: Estructuras repetitivas con control de salida en la cola (diagrama de la izquierda) ycontrol de salida en la cabeza (diagrama de la derecha).

A modo de ejemplo considerese la tarea de construir un vector v de dimension n de forma quela componente k−esima tenga el valor vk = k2−4. Por ejemplo, para n = 2 el vector resulta serv = [−3, 0], para n = 3 se obtiene v = [−3, 0, 5]. El problema que se quiere resolver es calcularlas componentes de v para un valor concreto de la dimension n que se proporcione. Dicho deotro modo, el algoritmo tendra que requerir un valor concreto de n y calcular las componentesv1 a vn. Se supondra que n es entero y positivo.


El diagrama de la figura 7.8 presenta una posible solucion al problema haciendo uso deuna estructura repetitiva con salida en la cola. Es muy conveniente dedicar unos minutos acomprobar que el algoritmo resuelve el problema. Para ello pruebe a seguir mediante calculosa mano los pasos indicados en el diagrama para n = 1, n = 2, n = 3. Una vez realizado esteejercicio no le resultara difıcil determinar que el algoritmo ha de funcionar necesariamente paratodo n > 0.

kVariableentera

Índice para recorrer v.Variable auxiliar

Leer n

Inicio

Fin

¿ k > n ?

sí

no

vk k·k -4

nVariableentera

Dato, dimensión de v

k 1

k k+1

vkVariableentera

Componente k-ésima de vcalculada mediante laexpresión k 2-4

vVariablevector deenteros

Resultado, vector v

Figura 7.8: Construccion de un vector mediante proceso iterativo con salida en la cola.

En el diagrama de la figura 7.9 se muestra otro diagrama que utiliza un bucle con salida enla cabeza. Compruebe tambien mediante pruebas a mano que este diagrama realiza la mismatarea que el del ejemplo anterior.

Debido a la sencillez de este ejemplo puede parecer que ambas maneras de realizar unaestructura cıclica son equivalentes de un modo trivial. Aunque es cierto que se puede pasarde una a otra esto no siempre se logra con facilidad. Ademas hay que tener en cuenta quealgunos lenguajes de programacion estan orientados a usar una de ellas, por ejemplo en el casode MATLAB siempre se prefiere la comprobacion de salida en cabeza.

El bloque constructivo llamado modulo puede usarse para mejorar el aspecto visual de losdiagramas de flujo. En particular si un diagrama consta de varias estructuras repetitivas puedeser interesante dedicar un modulo a cada uno de ellos. Para ilustrar esta idea considere elproblema cuyo enunciado es ”Se ha de leer una lista de n numeros reales, siendo n un enteroque ha de leerse previamente. Posteriormente se escribira la lista en orden inverso. Se supondraque n > 0”. La figura 7.10 muestra el diagrama de flujo de una posible solucion. Dicho diagramaincluye dos modulos que se detallan en diagramas separados. La tabla de objetos es unica pues


kVariableentera

Índice para recorrer v.Variable auxiliar

Leer n

Inicio

Fin

¿ k > n ?

non

Variableentera

Dato, dimensión de v

k 1

vkVariableentera

Componente k-ésima de vcalculada mediante laexpresión k 2-4

vVariablevector deenteros

Resultado, vector v

sí

vk k·k -4

k k+1

Figura 7.9: Construccion de un vector mediante proceso iterativo con salida en cabeza.

los diagramas correspondientes a los modulos se interpretan como parte del diagrama general.A todos los efectos se trata por tanto de un unico diagrama con la particularidad de que algunaspartes (los modulos) se detallan de forma separada.

Puede verse que los modulos ayudan a comprender mejor el algoritmo. Cada parte deldiagrama puede abarcarse de un golpe de vista, facilitando su comprension y el analisis de suvalidez.

7.4.1 Ejercicios

Los siguientes ejercicios se pueden resolver con ayuda de estructuras cıclicas. Utilice modulos enaquellos casos en que el diagrama resultante sea demasiado largo. Recuerde que los diagramasno pueden cortarse.

1. Leer las componentes de un vector de numeros reales de dimension 10. Escribirlo luego enla pantalla.

2. Leer un entero n supuesto n > 0 y un vector v ∈ IRn×1, calcular y escribir el productoescalar m = vtv, m ∈ IR, donde vt simboliza el vector transpuesto de v.

3. Leer n (suponiendo que es entero y > 0). Leer a continuacion las n componentes de un


k Variable enteraÍndice para recorrer vVariable auxiliar

n Variable enteraDato, dimensión de v

vk Variable realComponente k-ésima de v

vVariable vector de nreales

Dato, vector v

Inicio

Fin

Lectura devector v

Leer n

Escriturainversa devector v

Leer vk

Inicio de lectura devector v

Fin de lectura devector v

¿ k n ?no

k 1

sí

k k+1

!

Escribir vk

Inicio de escriturainversa de vector v

Fin de escriturainversa de vector v

¿ k 1 ?

k n

k k-1

"

no

sí

1 Constante enteraConstante para dar valorinicial y modificar k

Figura 7.10: Diagrama de flujo con modulos para el problema de la escritura inversa.


vector de numeros reales dimension n. Calcular y escribir luego la media aritmetica de suscomponentes.

4. Leer un numero real x y otro entero z. Calcular y escribir y = xz suponiendo que z ≥ 0.

5. Leer n (suponiendo que es entero y ≥ 0). Calcular y escribir f = n!.

6. Leer n (suponiendo que es entero y > 0) y un vector de dimension n. Calcular y escribirla componente de mayor valor.

7. Leer n (suponiendo que es entero y > 0) y un vector de dimension n. Calcular y escribirla componente de mayor valor y su ındice dentro del vector.

8. Leer n (suponiendo que es entero y mayor que uno). Construir un vector v ∈ IRn×1 talque vk = vk−1/3 + 0.5 para k = 2, ..., n y siendo v1 = 1.

9. Leer n (suponiendo que es entero y mayor que dos). Construir un vector v ∈ IRn×1 tal quesus componentes sean los terminos de la sucesion de Fibonacci1.

10. Se han medido las longitudes de tornillos procedentes de un mismo lote de fabricacion.Se han dispuesto en un vector v de dimension n > 2. Se dispone de v y n. Disene unalgoritmo para calcular la media y la varianza de las longitudes. La varianza se calculacomo var = 1

n

�nk=1 (vk − µ)2, siendo µ la media aritmetica de las componentes de v.

7.5 Ciclos dobles

El cuerpo de una estructura repetitiva no es necesariamente un modulo simple sino que puedecontener otras estructuras. En el punto anterior se han expuesto diversos ejemplos en los cualesel cuerpo contiene exclusivamente estructuras en secuencia. No existe ningun impedimento paraque el cuerpo contenga estructuras selectivas o incluso otros ciclos.

Cuando un ciclo contiene a otro se obtiene una estructura doblemente repetitiva2. En cadaiteracion del ciclo externo se realizan varias repeticiones del cuerpo del ciclo interno.

Las repeticiones dobles son especialmente apropiadas para trabajar con matrices A ∈ IRm×n.En muchas situaciones es preciso recorrer los elementos de la matriz para realizar de este modola lectura, escritura o cualquier otro calculo. Se plantea en estos casos el problema de considerartodos los posibles elementos akj de la matriz. Conviene recordar que el elemento generico akj

tiene dos subındices: k (filas) y j (columnas) que varıan en los intervalos: k = 1, 2, ...,m yj = 1, 2, ..., n.

1La sucesion de Fibonacci comienza con a1 = 1, a2 = 1 y posteriormente cada termino ak es la suma de los

dos anteriores ak−1 + ak−2 para k > 2.2Llamada frecuentemente bucles anidados por ser estas palabras la traduccion literal de nested loops.


Para trabajar con matrices se puede emplear un ciclo dentro de otro. Normalmente el cicloexterno recorre el ındice de filas y el interno el ındice de columnas. En la figura 7.11 se presentaun diagrama de flujo que puede utilizarse para recorrer la matriz.

iniciar j a 1

Incrementar j

Incrementar k

iniciar k a 1

Operar con el

elemento akj

¿ k > m ?sí

no

¿ j > n ?sí

no

Figura 7.11: Diagrama de flujo que permite recorrer una matriz gracias a dos estructuras repet-itivas.

7.5.1 Ejercicios

Los ejercicios que se proponen a continuacion se pueden resolver con la estructura de esta figura7.11 (aunque alguno de ellos puede resolverse con estructuras mas simples).

1. Lectura/escritura de una matriz m× n. Se han de leer del teclado las dimensiones m y n

(suponga que son numeros enteros positivos). A continuacion se han de leer los elementos


akj de una matriz A de m filas y n columnas. Finalmente se presentara en la pantalla lamatriz leıda.

2. Construir una matriz A ∈ IRm×n cuyo elemento generico akj viene dado por akj = k2 − j.

3. Dada una matriz (se supone ya leıda) A de dimensiones m× n, se quiere anular (poner acero) los elementos de su diagonal principal y escribir la matriz resultante.

4. Traza de una matriz. Dada una matriz cuadrada A ∈ IRn×n dada siendo n > 0 un enterotambien dado se ha de disenar un algoritmo que permita obtener la traza de A (suma delos elementos de la diagonal).

5. Suma de matrices. Dadas (suponga que ya han sido leıdas) dos matrices A ∈ IRm×n yB ∈ IRm×n se quiere calcular y escribir la matriz C obtenida como suma de las anterioresC = A + B.

6. Matriz traspuesta. Dada una matriz A ∈ IRm×n calcular su traspuesta B = At.

7. Submatriz triangular. Dada una matriz A ∈ IRm×n se desea calcular otra matriz B ∈ IRm×n

cuyos elementos son todos cero excepto los de la submatriz triangular inferior que soniguales a los elementos de igual posicion de A. Es decir, los elementos que estan por de-bajo de la diagonal principal de A se copian en B, el resto de elementos de B valen cero.Se supone que tanto m como n son numeros enteros mayores que uno ya leıdos.

8. Maximo de una matriz. Dada una matriz A ∈ IRm×n calcular el elemento mayor.

9. Maximo de cada fila. Dada una matriz A ∈ IRm×n con m > 1 y n > 1 dados se deseacalcular un vector v ∈ IRm cuya componente generica vk es el mayor valor de la filak−esima de A.

10. Crear matriz de ”1” y ”0” al tresbolillo.

7.6 Ejercicios tematicos

En este punto se presenta una serie de problemas que pueden ser resueltos con algoritmos quecombinan algunas de las estructuras explicadas en este tema.

7.6.1 Sucesiones y series

1. Se quiere construir y escribir un vector v de dimension n cuyas componentes siguen la leyvk = 3 ·vk−1−k para k ≥ 2. Tanto n como v1 son cantidades que han de leerse del teclado.

2. Dado n > 0 hallar la suma s =�n

k=1 1/k.


3. Se desea calcular la suma s =�n

k=1 1/ak siendo los valores ak los elementos de la sucesiondada por ak = ak−1 + ak−2 para k > 2, con a1 = 1 y a2 = 1. El lımite n ha de leerse delteclado y se supone mayor que dos.

4. Se desea calcular la suma s =�n

k=1 1/km siendo m y n dos numeros enteros positivos quese suponen dados.

5. Escriba los n primeros terminos de la sucesion dada por an = (1 + 1n)n, siendo n un numero

entero positivo dado.

7.6.2 Ordenaciones

1. Dado un vector v de dimension n cuyas componentes son todas positivas o cero se deseareordenar sus componentes de mayor a menor. Por ejemplo, si

v = [2 3 8 5 4]

el resultado ha de ser un nuevo vector:

w = [8 5 4 3 2]

2. Repetir el ejercicio anterior pero sin usar un vector auxiliar como w. El resultado que sepretende conseguir es que el propio vector v tenga sus componentes ordenadas.

3. Igual que el anterior pero suponiendo que v contiene cantidades positivas y negativas, porejemplo:

v = [−7 3 8 − 9 5 4 0 − 1]

ha de dar como resultado el propio vector reordenado ası:

v = [8 5 4 3 0 − 1 − 7 − 9]

4. Un fabricante de automoviles dispone de un modelo de vehıculo en cinco colores. Parasaber la aceptacion de cada color realiza una encuesta usando un programa en su ordenadorportatil. El programa ha de ayudarle a contar los votos de los encuestados. El encuestadortecleara el numero del color elegido (de uno a cinco) cada vez que pregunte a una personanueva. Cuando no quiera preguntar a nadie mas introducira el valor -1. En ese momentoel programa le indicara el numero de votos que cada color ha obtenido. Posteriormente sehan de ordenar los colores segun los resultados de la votacion.

5. Se desea calcular la mediana de los valores contenidos en un vector T ∈ IRn. Si n es imparla mediana es el valor central del vector ordenado, en caso contrario la mediana es la mediade los dos elementos que estan mas al centro. En ambos casos el paso previo para calcularla mediana es ordenar el vector.

Un ejemplo con n par es T = [10 23 11 15]. La ordenacion produce T o = [23 15 11 10]y la mediana es (15 + 11)/2 = 13. Un ejemplo con n impar es T = [11.8 12 28 11.5 14].


En este caso la ordenacion produce un nuevo vector T o = [11.5 11.8 12 14 28], de dondese obtiene la mediana que es el valor central 12.

Puede comprobar con los ejemplos anteriores que la mediana no coincide con la mediaaritmetica.

7.6.3 Calculos con enteros

Para poder disenar los algoritmos que resuelven algunos de los problemas propuestos a contin-uacion puede necesitar una funcion que elimine los decimales de numeros reales y obtener deeste modo numeros enteros. Esta funcion recibe el nombre de parte entera y puede denotarsematematicamente como ParteEntera(). De este modo x← ParteEntera(3.14) es equivalente ax← 3.

1. Dado un numero entero x mayor que uno se ha de escribir un uno si el numero es par yun cero en caso contrario.

2. Dados dos numeros enteros positivos p y q, p > q, se ha de escribir un uno si son divisiblesy cero si no lo son.

3. Dado un numero entero x mayor que uno se ha de escribir la lista de sus divisores com-prendidos en el intervalo (1, x).

4. Dado un numero entero x mayor que uno se ha de escribir un uno si es primo y un cero encaso contrario. Para ello ha de comprobar si x es divisible por algun entero en el intervalo(1, x).

5. Dada una cantidad N > 1 calcular la raız cuadrada entera aproximada r. Se ha de cumplirque r · r ≤ N < (r + 1) · (r + 1).

Por ejemplo, si N = 24 se tiene que r = 4 pues 4 · 4 = 16 ≤ 24 < 25 = 5 · 5.

6. Se ha de escribir un uno en el caso de que exista un trıo (x, y, z)de numeros enteros positivostales que x2 + y2 = z2. Limite la busqueda a x ∈ (0, 100], y ∈ (0, 100]. En caso de que nose encuentre solucion se ha de escribir un cero.

7. Repita el ejercicio anterior pero escribiendo todas las soluciones que encuentre en el inter-valo x ∈ (0, 1000], y ∈ (0, 1000].

8. Dados dos numeros enteros positivos p y q escriba un algoritmo que permita hallar elmaximo comun divisor de los mismos.

9. Como aplicacion del ejercicio anterior disene un algoritmo que permita descubrir si dosenteros positivos son primos entre sı, es decir si su maximo comun divisor es uno.


7.6.4 Matrices

1. Multiplicacion de matrices. Suponga ya leıdas A ∈ IRm×n y B ∈ IRn×p, calcule C = A ·B.

2. Matriz al cubo. Disene un algoritmo que permita obtener B = A3, siendo A ∈ IRn×n unamatriz cuadrada que se supone ya leıda.

3. Exponenciacion de matrices. Disene un algoritmo que permita obtener B = Ap, siendoA ∈ IRn×n una matriz dada y p > 0 un entero tambien dado.

4. Dados dos enteros positivos m y n se desea construir la matriz S ∈ IRm×n cuyo elementogenerico viene dado por skj =

�kh=1 1/hj

7.6.5 Leyes

La evolucion de ciertas magnitudes del mundo real puede en ocasiones acomodarse a simplesleyes expresables de un modo similar a las sucesiones. En este apartado se proporcionan algunosejemplos que ilustran la forma en que el calculo por ordenador ayuda a la Ciencia y la Ingenierıa.

1. La cantidad de un cierto isotopo radioactivo presente en una mezcla varıa con el tiempopues el isotopo se descompone emitiendo radiacion. Se denota mediante y(k) la cantidaden gramos de isotopo en el instante de tiempo t = k medido en anos. Unos cientıficos handescubierto que se cumple que y(k) = 0.99 · y(k− 1). Si un barril de desechos radioactivoscontiene 1000 gramos de isotopo, ¿cual sera la cantidad de isotopo presente al cabo de 500anos?

2. La velocidad de un paracaidista en su descenso al suelo una vez que ha abierto el paracaıdasse denota mediante v(k) (m/s), siendo k el tiempo que lleva cayendo medido en segundos,k > 1. Se ha especulado con la idea de que dicha velocidad sigue la ley: v(k) = v(k −1) + 10 − 0.4(v(k − 1))2. Sabiendo que una caıda tıpica puede durar 5 minutos y queel paracaıdas se suele abrir con una velocidad de 100 Km/h, ¿con que velocidad llega alsuelo?

3. Se sabe que la cantidad de bacterias de cierta especie en un cultivo es x(k) = 1.1x(k −1) siendo k el tiempo medido en horas, k > 1. Si al cabo de la primera hora x(1) secontabilizaron 100 unidades, ¿cuantas habra al cabo de un dıa?

7.7 Comprobacion del funcionamiento de algoritmos

La comprobacion del buen funcionamiento de un algoritmo es una tarea difıcil y para la cualno existen reglas generales. En muchos casos sin embargo el sentido comun y el razonamiento


logico permiten realizar pruebas que permiten asegurar la correccion.

Existen dos formas de enfrentarse a la tarea de decidir si un algoritmo dado es verdadera-mente una solucion al problema planteado: la prueba del algoritmo con un conjunto de datoscontrolado y la prueba mediante razonamiento logico-matematico.

7.7.1 Pruebas con datos controlados

La prueba del algoritmo con datos controlados consiste en preparar una serie de valores de losdatos para los cuales se conoce el resultado correcto. Posteriormente se siguen los pasos delalgoritmo y se comprueba si los resultados que el algoritmo produce coinciden con los resultadosconocidos de antemano.

Como ejemplo considere el problema de escribir un uno en caso de que cierto entero x seaprimo y cero en otro caso. Si se desea comprobar si cierto algoritmo A es correcto puede serbuena idea probar A con x = 2 y comprobar que el resultado es que se escribe un uno. Si elresultado no es este no hace falta comprobar mas, pues un solo fallo sirve para invalidar A. Siel resultado es correcto se puede pasar a probar A con x = 3 y repetir el proceso.

Es facil ver que este metodo tiene el grave inconveniente de que hacen falta tantas pruebascomo posibles valores distintos puede tomar el dato x. En muchas ocasiones se recurre al metodode probar el algoritmo solo en algunos valores elegidos. Por ejemplo con varios numeros primosy otros no primos tanto grandes como pequenos. Hay que resaltar que este tipo de pruebasno permite validar el algoritmo completamente. Esto es ası porque un algoritmo puede darresultados correctos en muchas situaciones y sin embargo no ser correcto universalmente puespuede que contenga errores que no se han manifestado con esos datos.

No existe un procedimiento general para seleccionar valores de prueba para algoritmos, sinembargo es posible dar algunos consejos como:

• probar valores particulares que puedan dar problemas como el cero (en el caso de que hayadivisiones), o los numeros negativos (si hay raıces cuadradas).

• probar los valores extremos de los datos, por ejemplo si se sabe que el dato x ∈ IR cumpleque x ∈ [5, 3] entonces merece la pena probar con los valores x = 3 y x = 5.

7.7.2 Razonamientos por induccion

En muchos casos es posible aplicar el metodo matematico de prueba inductiva. Por ejemplocuando el dato de un algoritmo puede tomar cualquier valor n ∈ IN.


El razonamiento inductivo se lleva a cabo probando (en el sentido matematico) que si elalgoritmo funciona para un valor n cualquiera entonces debe funcionar tambien para el valorsiguiente n + 1. La prueba se completa utilizando el algoritmo con n = 1 y comprobandoque el resultado es satisfactorio. Mediante induccion se obtiene que entonces el algoritmo debefuncionar correctamente para n = 2 y de aquı que tambien sea correcto para n = 3, etc.

Este tipo de razonamiento permite decidir la correccion de algoritmos que contienen estruc-turas iterativas. En estos casos los puntos que causan mayores problemas son las entradas ysalidas de los ciclos de repeticion. Por este motivo hay que prestar mucha atencion a los valoresiniciales asignados a ındices y contadores antes de entrar en el ciclo, a la actualizacion de losmismos dentro del cuerpo que se repite y finalmente a la condicion de salida del ciclo.

El principal inconveniente de este metodo de correccion es que es posible que la pruebamatematica contenga errores, proporcionando como resultado que se etiquete como correcto unalgoritmo que no lo es. Por este motivo es conveniente siempre realizar la prueba por ambosmetodos.

7.7.3 Modularidad

Si el diseno del algoritmo se ha llevado a cabo de forma adecuada el diagrama ha de consistiren una serie de modulos (o funciones) de pequeno tamano que se unen para formar modulosmayores.

El analisis de algoritmos se realiza entonces de una forma comoda pues basta con probarcada modulo de forma independiente. Cuando se han comprobado los modulos de un ciertonivel puede pasarse al nivel superior. Las comprobaciones de un nivel superior pueden llevarsea cabo sin necesidad de volver a utilizar o analizar los modulos de niveles inferiores. En lugarde ello es posible sustituir mentalmente dichos modulos por mecanismos que automaticamenteproporcionan los resultados correctos. De este modo el analisis se lleva a cabo de forma jerarquicalo cual permite avanzar con mayor rapidez y confianza.

7.8 Analisis de la estructura

Es posible ahora poner un par de ejemplos para aclarar las ideas sobre la programacion estruc-turada. Considere en primer lugar el diagrama que aparece en la parte izquierda de la figura7.12. A la vista como estan unidos los bloques ¿sabrıa decir si es un diagrama bien estructurado?.

Para responder a esta cuestion resulta conveniente agrupar los bloques que forman secuenciasen modulos, de forma que la estructura subyacente quede expuesta con mayor claridad. Esto


se ha realizado en el diagrama del centro. Finalmente, en el diagrama de la derecha se hansustituido las secuencias por modulos, quedando al descubierto una estructura que coincide conuna de las estructuras permitidas (vease de nuevo la figura 7.2). Esta estructura es un bucle consalida en cola y aparece aquı combinado en secuencia por arriba y abajo con otros dos modulos.

Figura 7.12: Analisis de la estructura de un diagrama.

Este sencillo analisis permite determinar que la estructura del diagrama esta de acuerdo conlas normas establecidas en este capıtulo. Observe que para discutir sobre la estructura de undiagrama no es preciso conocer las operaciones que se realizan en cada bloque. En efecto, laestructura depende exclusivamente de las uniones entre bloques y no de su contenido.

Considere ahora el diagrama que se muestra en la parte izquierda de la figura 7.13. A primeravista no parece haber nada que indique que el diagrama no sea estructurado (al menos no loparece para el principiante en esta materia). En la parte central y derecha de la figura se pone demanifiesto que esto es un error. En efecto, el recuadro a trazos intenta encerrar una estructuradel tipo repeticion o bucle con salida en cola. Sin embargo el recuadro no tiene solamente unaentrada y una salida como se requiere. De hecho, el recuadro es cortado por dos flechas deentrada y por una de salida. Si uno intenta encerrar la estructura inferior mediante un recuadro(vease parte derecha de la figura) ocurre nuevamente que no se cumple la regla de una unicaentrada y una unica salida. En este caso hay dos salidas y una sola entrada.


Figura 7.13: Analisis de la estructura de un diagrama.

programacio´n estructurada - wordpress.com › 2012 › 10 › tema-7-inform...bifurcacion´...

Documents