programacion c ejercicios resueltos-85

Vista previa del material en texto

Ahora se puede escribir el algoritmo:
Leer starCount
MIENTRAS NO SE LLEGUE AL FINAL DEL ARCHIVO
 Establecer loopCount = 1
 MIENTRAS loopCount <= starCount
 Imprimir ‘*’
 Incrementar loopCount
 Producir una nueva línea
 Leer starCount
Imprimir “Hasta luego”
Por supuesto, los ciclos anidados por sí mismos pueden contener ciclos anidados (llamados ciclos
doblemente anidados), que pueden contener ciclos anidados (ciclos triplemente anidados), etcétera. 
Este diseño de proceso se puede usar para cualquier número de niveles de anidación. El truco es di-
ferir detalles por medio de la metodología de descomposición funcional, es decir, centrar la atención 
primero en el ciclo externo y tratar cada nuevo nivel de ciclo anidado como un módulo dentro del 
ciclo que lo contiene.
También es posible que el proceso dentro de un ciclo incluya más de un ciclo. Por ejemplo, aquí 
está un algoritmo que lee e imprime los nombres de personas desde un archivo, omitiendo el apellido 
paterno en la salida:
Leer e imprimir el nombre (termina con una coma)
MIENTRAS NO SE LLEGUE AL FINAL DEL ARCHIVO
 Leer y eliminar los caracteres del segundo nombre (termina con una coma)
 Leer e imprimir el apellido (termina en una nueva línea)
 Producir una nueva línea
 Leer e imprimir un nombre (termina con una coma)
Los pasos para leer nombre, segundo nombre y apellido requiere diseñar tres ciclos separados. 
Todos estos ciclos son controlados por centinela.
Esta clase de estructura de control compleja sería difícil de leer si se escribiera completa. Hay 
simplemente muchas variables, condiciones y pasos qué recordar en un momento. En los dos capítu-
los siguientes se examina la estructura de control que descompone los programas en trozos más 
manejables: el subprograma.
Bases teóricas
Análisis de algoritmos
Si para limpiar una habitación tiene que elegir entre un cepillo de dientes y una escoba, es probable que 
elija la escoba. Usar una escoba representa menos trabajo que usar un cepillo de dientes. Cierto, si la 
habitación fuese una casa de muñecas, podría ser más fácil usar el cepillo de dientes, pero en general usar 
una escoba es la forma más fácil de limpiar. Si se le diera a elegir entre lápiz y papel y una calculadora para 
sumar números, es probable que elija la calculadora porque de ordinario representa menos trabajo. Si tu-
viera que elegir entre caminar o manejar para llegar a una reunión, tal vez elegiría conducir; al parecer es 
más fácil.
 6.5 Lógica anidada | 225
▼(continúa)
DALE06.indd 225DALE06.indd 225 4/12/06 19:03:284/12/06 19:03:28
 www.FreeLibros.me
226 | Capítulo 6: Ciclos
Análisis de algoritmos
¿Qué tienen en común estos ejemplos? ¿Qué tiene que ver con la computación? En cada una de las 
situaciones mencionadas, una de las elecciones parece requerir menos trabajo. Medir con exactitud la can-
tidad de trabajo es difícil en cada caso porque hay incógnitas. ¿Qué tan grande es la habitación? ¿Cuántos 
números hay? ¿Qué tan lejos es la reunión? En cada caso, la información desconocida se relaciona con el ta-
maño del problema. Si el problema es especialmente pequeño (por ejemplo, sumar 2 más 2), la estimación 
original de cuál método elegir (usar la calculadora) podría ser equivocado. Sin embargo, la intuición suele 
ser correcta porque la mayoría de los problemas son razonablemente grandes.
En computación se requiere una forma de medir la cantidad de trabajo hecho por un algoritmo en 
relación con el tamaño de un problema, porque hay más de un algoritmo que resuelve cualquier problema 
dado. Con frecuencia se debe elegir el algoritmo más efi ciente, el algoritmo que hace el mínimo trabajo 
para un problema de un determinado tamaño.
La cantidad de trabajo requerida para ejecutar un algoritmo en relación con el tamaño del problema 
se denomina complejidad del algoritmo. Sería deseable poder 
examinar un algoritmo y determinar su complejidad. Después 
se podrían tomar dos algoritmos que realizan la misma tarea 
y determinar cuál la completa más rápido (requiere menos 
trabajo).
¿Cómo se mide la cantidad requerida de trabajo para 
ejecutar un algoritmo? Se usa el número total de pasos ejecutados como medida de trabajo. Una sentencia, 
lo mismo que una asignación, podría requerir sólo un paso; otra, como un ciclo, podría necesitar muchos 
pasos. Se defi ne un paso como cualquier operación aproximadamente equivalente en complejidad a una 
comparación, una operación I/O o una asignación.
Dado un algoritmo con sólo una secuencia de sentencias simples (ninguna bifurcación o ciclo), el nú-
mero de pasos llevados a cabo se relaciona de modo directo con el número de sentencias. Cuando se intro-
ducen bifurcaciones, se posibilita omitir algunas sentencias del algoritmo. Las bifurcaciones permiten restar 
pasos sin eliminarlos físicamente del algoritmo porque sólo se ejecuta una rama a la vez. Pero debido a que, 
por lo común, se quiere expresar trabajo en términos del escenario del peor de los casos, se usa el número 
de pasos de la rama más larga.
Ahora considere el efecto de un ciclo. Si el ciclo repite una secuencia de 15 sentencias simples 10 
veces, éste efectúa 150 pasos. Los ciclos permiten multiplicar el trabajo hecho en un algoritmo sin añadir 
sentencias.
Ahora que se tiene una medida para el trabajo hecho en un algoritmo, se pueden comparar algorit-
mos. Por ejemplo, si un algoritmo A ejecuta siempre 3124 pasos y el algoritmo B hace siempre la misma 
tarea en 1321 pasos, entonces se puede decir que el algoritmo B es más efi ciente; es decir, son menos los 
pasos para realizar la misma tarea.
Si un algoritmo, de una ejecución a otra, siempre toma el mismo número de pasos o menos, se dice 
que se ejecuta en una cantidad de tiempo acotada por una constante. Se dice que este tipo de algoritmos 
tiene complejidad de tiempo constante. Tenga cuidado: tiempo constante no signifi ca pequeño; signifi ca 
que la cantidad de trabajo no excede cierta cantidad de una ejecución a otra.
Si un ciclo se ejecuta un número fi jo de veces, el trabajo hecho es mayor que el número físico de sen-
tencias, pero aún es constante. ¿Qué sucede si el número de interacciones de ciclo cambia de una ejecución 
a la siguiente? Suponga que un archivo de datos contiene N valores de datos que serán procesados en un 
ciclo. Si el ciclo lee y procesa un valor durante cada iteración, entonces el ciclo ejecuta N iteraciones. La can-
tidad de trabajo realizado depende de una variable: el número de valores de datos. La variable N determina 
el tamaño del problema en este ejemplo.
Si se tiene un ciclo que se ejecuta N veces, el número de pasos por ejecutar es algún factor multiplica-
do por N. El factor es el número de pasos realizados dentro de una sola iteración del ciclo.
Complejidad Medida del esfuerzo que realiza la compu-
tadora para efectuar un cálculo, en relación con el tamaño 
del mismo.
▼(continúa)
DALE06.indd 226DALE06.indd 226 4/12/06 19:03:314/12/06 19:03:31
 www.FreeLibros.me
Análisis de algoritmos
Específi camente, el trabajo realizado por un algoritmo con un ciclo dependiente de datos está dado 
por la expresión
S N S1 0× +
Pasos que
efectúa el ciclo
Pasos efectuados
fuera del ciclo 
donde S1 es el número de pasos en el cuerpo del ciclo (una constante para un determinado ciclo simple), 
N es el número de iteraciones (una variable que representa el tamaño del problema) y S0 es el número de 
pasos fuera del ciclo. Los matemáticos nombran lineales a esta forma de expresiones; por consiguiente, se 
dice que algoritmos como éste tienen complejidad de tiempo lineal. Observe que si N se hace muy grande, 
el término S1 × N domina al tiempo de ejecución. Es decir, S0 se vuelve una parte insignifi cante del tiempo 
de ejecución total. Por ejemplo, si S0 y S1 constan de 20 pasos cada uno, y N es 1 000 000, entonces el núme-
ro total de pasos es 20 000 020. Los 20 pasos con los que contribuye S0 son una pequeña fracción del total.
¿Qué hay acerca de un ciclo dependiente de datosque contiene un ciclo anidado? El número de pasos 
en el ciclo interno, S2, y el número de iteraciones efectuadas por el ciclo interno, L, se debe multiplicar por el 
número de iteraciones en el ciclo externo:
S L N S N S2 1 0× ×( ) + ×( ) +
Pasos efectuados
por el ciclo anidado
Pasos realizados
por el ciclo externo
Pasos que lleva a cabo
el ciclo externo
 
Por sí mismo, el ciclo interno lleva a cabo S2 × L pasos, pero debido a que el ciclo externo lo repite N 
veces, representa un total de S2 × L × N pasos. Si L es una constante, entonces el algoritmo aún se ejecuta en 
tiempo lineal.
Ahora, suponga que para cada una de las N iteraciones del ciclo externo, el ciclo interno efectúa N 
pasos (L = N). Por consiguiente, la fórmula para el número total de pasos es
S N N S N S2 1 0× ×( ) + ×( ) +
o bien,
Debido a que N2 crece mucho más rápido que N (para valores grandes de N), el término del ciclo in-
terno (S2 × N
2) representa la mayor parte de los pasos ejecutados y del trabajo realizado. Así, el tiempo de 
ejecución correspondiente es en esencia proporcional a N 2. Los matemáticos llaman a este tipo de fórmula 
cuadrática. Si se tiene un ciclo doblemente anidado en el cual cada ciclo depende de N, entonces la expre-
sión es
S N S N S N S3
3
2
2
1 0×( ) + ×( ) + ×( ) +
 
 6.5 Lógica anidada | 227
▼(continúa)
DALE06.indd 227DALE06.indd 227 4/12/06 19:03:394/12/06 19:03:39
 www.FreeLibros.me