17.1.1: Introducción a los Algoritmos

La mayoría de los algoritmos de este libro contendrán una combinación de tres tipos de pasos: el paso de asignación, el paso condicional y el bucle.

Asignaciones

Para asignar un valor a una variable, utilizamos un paso de asignación, que toma la forma:

\ begin {ecuación*}\ textrm {Variable = Expresión a calcular}\ end {ecuación*}

El signo igual en la mayoría de los idiomas se usa para la asignación, pero algunos idiomas pueden usar variaciones como: = o una flecha que apunta hacia la izquierda. La igualdad lógica, que produce un resultado booleano y se usaría en pasos condicionales o de bucle, se expresa más comúnmente con un doble-igual, ==.

Un ejemplo de una asignación es k = n - 1 que nos dice que restemos 1 del valor de n y asignemos ese valor a la variable k. Durante la ejecución de un algoritmo, una variable puede tomar solo un valor a la vez. Otro ejemplo de una asignación es k = k - 1. Esta es una instrucción para restar uno del valor de k y luego reasignar ese valor a k.

Pasos condicionales

Frecuentemente hay pasos que se deben realizar en un algoritmo si y sólo si se cumple una determinada condición. Entonces se emplea el paso condicional o “si... entonces”. Por ejemplo, supongamos que en el paso 2 de un algoritmo queremos asegurar que los valores de las variables x e y satisfacen la condición x <= y. El siguiente paso lograría este objetivo.

2. If x > y:
    2.1 t = x
    2.2 x = y
    2.3 y = t

Listado\(\PageIndex{1}\)

Los pasos 2.1 a 2.3 se pasarían por alto si la condición x > y fuera falsa antes del paso 2.

Una ligera variación es el paso “si... entonces... else”, que nos permite prescribir un paso a tomar si la condición es falsa. Por ejemplo, si quisieras hacer ejercicio hoy, podrías mirar por la ventana y ejecutar el siguiente algoritmo.

1. If it is cold or raining:
        exercise indoors
    else:
        go outside and run
2. Rest

Listado\(\PageIndex{2}\)

17 Bucles

El paso condicional nos dice que hagamos algo una vez si una condición lógica es verdadera. Un bucle nos dice repetir uno o más pasos, llamados el cuerpo del bucle, mientras que la condición lógica es verdadera. Antes de cada ejecución del cuerpo, se prueba la condición. El siguiente diagrama de flujo sirve para ilustrar los pasos en un bucle While.

Figura\(\PageIndex{1}\): Diagrama de flujo para un bucle while

Supongamos que quería resolver\(f(x) = 0\text{.}\) la ecuación Se podría emplear la siguiente asignación inicial y bucle.

1. c = your first guess
2. While f(c) != 0:
        c = another guess

Listado\(\PageIndex{3}\)

Nota

Siempre se debe proteger contra la posibilidad de que la condición de un bucle While nunca se vuelva falsa. Tales “bucles infinitos” son la ruina de los programadores principiantes. El bucle anterior muy bien podría ser tal situación, particularmente si la ecuación no tiene solución, o si la variable toma valores reales

En los casos en que se van a asignar valores enteros consecutivos a una variable, a menudo se emplea una construcción de bucle diferente, un bucle For. Por ejemplo, supongamos que quisiéramos asignar a la variable k cada uno de los valores enteros de m a n y para cada uno de estos valores realizar algunos pasos indefinidos. Podríamos lograr esto con un bucle While:

1. k := m
2. While k <= n:
    2.1 execute some steps
    2.2 k = k + l

Listado\(\PageIndex{4}\)

Alternativamente, podemos realizar estos pasos con un bucle For.

For k = m to n:
    execute some  steps

Listado\(\PageIndex{5}\)

Para bucles como este tienen la ventaja de ser más cortos que el bucle While equivalente. La construcción de bucle While tiene la ventaja de poder manejar situaciones más diferentes que el bucle For.

Ejercicios

Ejercicio\(\PageIndex{1}\)

¿Cuáles son las entradas y salidas de los algoritmos enumerados en la primera oración de esta sección?

Ejercicio\(\PageIndex{2}\)

¿Qué tiene de malo este algoritmo?

Input: a and b, integers
Output: the value of c will be a - b
(1) c = 0
(2) While a > b:
        (2.1) a := a - l
        (2.2) c := c + l

Listado\(\PageIndex{6}\)

Contestar

El algoritmo sólo funciona cuando a > b.

Ejercicio\(\PageIndex{3}\)

Describa, en palabras, lo que hace el siguiente algoritmo:

Input: k, a positive integer
Output: s = ?
(1) s = 0
(2) While k > 0:
    (2.1) s = s + k
    (2.2) k = k - 1

Listado\(\PageIndex{7}\)

Ejercicio\(\PageIndex{4}\)

Escriba bucles While para reemplazar los bucles For en los siguientes algoritmos parciales:

1. 1. S = 0
   2. para k = 1 a 5: S = S + k^2
2. El piso de un número es el mayor entero menor o igual que ese número.
   1. m = un número entero positivo mayor que 1
   2. B = piso (sqrt (m))
   3. para i = 2 a B: si i divide uniformemente en m, salta al paso 5
   4. print “m is a prime” y sale
   5. imprimir “m es compuesto” y salida

Ejercicio\(\PageIndex{5}\)

Describa en palabras lo que hace el siguiente algoritmo:

Input: n, a positive integer
Output: k?
(1) f= 0
(2) k=n
(3) While k is even:
    (3.1) f = f+ 1
    (3.2) k = k div 2

Listado\(\PageIndex{8}\)

Ejercicio\(\PageIndex{6}\)

Arreglar el algoritmo en Ejercicio\(\PageIndex{2}\).