Algoritmos

1 Noción elemental sobre qué es un algoritmo

2 Un algoritmo puede implementarse como un programa en un dispositivo digital

3. La ejecución de un programa consiste en la ejecución precisa de instrucciones

4. Las computadoras son programables, y los programas son elaborados por seres humanos que al hacerlo definen el comportamiento de estas máquinas

Algoritmos con variables de acumulación

Suma de una secuencia

Queremos calcular la suma siguiente: 1 + 2 + ... + 200.

Escribir un algoritmo que calcule esta suma. La única operación que podemos usar en este algoritmo es la suma de dos enteros, Este algoritmo puede usar variables y estructuras de repeticion (de tipo while o for).

Escribir este algoritmo usando el lenguaje informal llamado pseudocódigo. Leer la intro y el ejemplo "Pseudocódigo estilo C" de la página Wikipedia acerca del pseudocódigo.

El algoritmo tiene que ser escrito de manera que se pueda modificar fácilemente para calcular otras sumas de secuencias: 1 + ... + 200 + 201, o 5 + 6 + ... + 150, etc.

Explicar un algoritmo

En el algoritmo anterior, tenemos dos tipos de variables:

Producto de una secuencia

Misma pregunta para calcular: 1 * 2 * ... * 10.

Algoritmo para calcular el Máximo Común Divisor

Sean a y b dos enteros positivos tales que a >= b.

El máximo común divisor de a y b es el mayor entero que divide a y b sin dejar resto.

Lo escribimos MCD(a,b).

Observaciones I

Dado un solo entero positivo a:

  1. ¿Qué tan grande puede ser un divisor de a?
  2. ¿Qué tan chiquito puede ser un divisor de a?
  3. ¿En qué rango de valores posibles se encuentran los divisores de a?

Proponer un algoritmo para el problema siguiente:

Observaciones II

Dados dos enteros positivos a y b, con a ≥ b:

  1. ¿Qué tan grandes pueden ser los divisores comunes de a y b?
  2. ¿Qué tan chiquitos pueden ser?
  3. ¿En qué rango de valores posibles se encuentran?

Proponer un algoritmo para el problema siguiente:

Observaciones III

Dados dos enteros positivos a y b, con a ≥ b:

  1. ¿Qué tan grande puede ser MCD(a,b)?
  2. ¿Qué tan chiquito puede ser?
  3. ¿En qué rango de valores posibles se encuentra MCD(a,b)?

Algoritmo de MCD(a,b)

Escribir un algoritmo para calcular MCD(a,b) dados a ≥ b ≥ 1.

La consigna es:

Pueden comprobar su algoritmo implementándolo en un programa que declare dos variables a y b, con valores iniciales tales que a ≥ b ≥ 1, que calcule su MCD y que lo muestre en la salida.

Entrega para la próxima semana

Escribir un algoritmo que calcule MCD(a,b) dados a ≥ b ≥ 1, siguiendo el método descrito arriba.

Facultativo:

Escribir un segundo algoritmo que haga el recorrido de valores posibles en el otro sentido (de manera decreciente). ¿Qué ventaja tiene este algoritmo con respecto al primero?