Página 5. Estructura de datos en C++

• 1.4. ALGORITMOS

El término resolución de un problema se refiere al proceso completo que abarca desde la descripción inicial del problema hasta el desarrollo de un programa de computadora que lo resuelva. La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto. Los pasos para la resolución de un problema son:

1. Diseño del algoritmo que describe la secuencia ordenada de pasos --sin ambigüedades-- que conducen a la solución de un problema dado. (Análisis del problema y desarrollo del algoritmo).
2. Expresar el algoritmo como un programa en un lenguaje de programación adecuado. (Fase de codificación).
3. Ejecución y validación del programa por la computadora.

Para llegar a la realización de un programa es necesario el diseño previo de un algoritmo indicando cómo hace el algoritmo la tarea solicitada, y eso se traduce en la construcción de un algoritmo. El resultado final del diseño es una solución que debe ser fácil de traducir a estructura de datos y estructuras de control de un lenguaje de programación específico.

Las dos herramientas más comúnmente utilizadas para diseñar algoritmos son: diagramas de flujo y pseudocódigos.

Diagrama de flujo (flowchart)

Es una representación gráfica de un algoritmo.

EJEMPLO 1.1. Diagrama de flujo que representa un algoritmo que lea el radio de un círculo, calcule su perímetro y su área.

Se declaran las variables reales r, longitud, y area, así como la constante pi.

constantes pi = 3.14

variables real: r, longitud, area

Pseudocódigo

En esencia el pseudocódigo se puede definir como un lenguaje de especificación de algoritmos.

------------------------------------------------------------------------------------------------------------------------------------------------------------------
EJEMPLO 1.2. Realizar un algoritmo que lea tres números; si el primero es positivo calcule el producto de los tres números, y en otro caso calcule la suma.

Se usan tres variables enteras Numero1, Numero2, Numero3, en las que se leen los datos, y otras dos variables Producto y Suma en la que se calcula, o bien el producto, o bien la suma. El algoritmo que resuelve el problema es el siguiente.

Entrada Numero1, Numero2 y Numero3
Salida Suma o el Producto

inicio
1 leer los tres números Numero1, Numero2, Numero3
2 si el Numero1 es positivo
     calcular el producto de los tres números
     escribir el producto
3 si el número no es positivo
     calcular la suma de los tres números
     escribir la suma
fin


El algoritmo en pseudocódigo es:

algoritmo Producto_suma
variables
     entero: Numero1, Numero2, Numero3, Producto, Suma
inicio
     Leer (Numero1, Numero2, Numero3)
     si (Numero1 > 0) entonces
          Producto ← Numero1 * Numweo2 * Numero3
          Escribe ('El producto de los números es: ', Producto)
     sino
          Suma ← Numero1 + Numero2 + Numero3
          Escribe ('La suma de los números es: ', Suma)
     fin si
fin


El algoritmo escrito en C++ es:

#include <cstdlib>
#include <iostream>
using namespacestd;

int main(int argc, char *argv[])
{
     int Numero1, Numero2, Numero3, Prodcuto, Suma;
     cin >> Numero1 >> Numero2 >> Numero3;
     if (Numero1 > 0)
     {
          Producto = Numero1 * Numero2 *Numero3;
          cout << " El producto de los numeros es: " << Producto;
     }
     else
     {
          Suma = Numero1 + Numero2 + Numero3;
          cout << " La sumas de los numeros es: " << Suma;
     }
     return 0;
}


El algoritmo es la especificación concisa del método para resolver un problema con indicación de las acciones a realizar. Un algoritmo es un conjunto finito de reglas que dan una secuencia de operaciones para resolver un determinado problema. Es, por consiguiente, un método para resolver un problema que tiene en general una entrada  y una salida. Las características fundamentales que debe cumplir todo algoritmo son:

• Un algoritmo debe de ser preciso e indicar el orden de realización de cada paso.
• Un algoritmo debe de estar bien definido. Si se sigue un algoritmo dos veces, se debe de obtener el mismo resultado cada vez.
• Un algoritmo debe de ser finito. Si se sigue un algoritmo, se debe terminar en algún momento; es decir, debe de tener un número finito de pasos .

La definición de algoritmo debe de describir tres partes: Entrada, Proceso, Salida.

------------------------------------------------------------------------------------------------------------------------------------------------------------------
EJEMPLO 1.3. Diseñar un algoritmo que permita saber si un número entero positivo es primo o no. Un número es primo si sólo puede dividirse por si mismo y por la unidad (es decir, no tiene mas divisores que él mismo y la unidad). Por ejemplo 9, 8, 6, 4, 12, 16, 20, etc., no son primos ya que son divisibles por números distintos a ellos mismos y a la unidad. Así 9 es divisible por 3, 8 lo es por 2, etc. El algoritmo de resolución del problema pasa por dividir sucesivamente el número por 2, 3, 4, etc.

Entrada: dato n entero positivo
Salida: es o no primo

proceso:

1. Inicio.
2. Hacer x igual a 2 (x = 2, x variable que representa a los divisores del número que se                              buscan).
3. Dividir n por x (n/x).
4. Si el resultado de n/x es entero, entonces n no es un número primo y bifurcar (partir) al punto 7; en caso contrario, continuar el proceso.
5. Suma 1 a x (x ← x + 1).
6. Si x es igual n, entonces n es un número primo; en caso contrario bifurcar al punto 3.
7. Fin.

El algoritmo anterior escrito en pseudocódigo y C++ es el siguiente:

Algoritmo en pseudocódigo	Algoritmo en C++
algoritmo primo inicio      variables           entero: n, x;           lógico: primo;      leer(n);      x ← 2;      primo ← verdadero;      mientras primo y (x < n) hacer       si n mod x <> 0 entonces        x ← x + 1;       sino        primo ← falso       fin si      fin mientras      si (primo) entonces       escribe (‘es primo’)      sino       escribe (‘no es primo’)      fin si fin	#include <cstdlib> #include <iostream> using namespace std; int main(int argc, char *argv[]) {    int n, x;    bool primo;    cin >> n;    x = 2;    primo = true;    while (primo && (x < n ))       if (n % x != 0)          x = x + 1;       else          primo = false;    if (primo)       cout << “es primo”;    else       cout << “no es primo”;    return 0; }

------------------------------------------------------------------------------------------------------------------------------------------------------------------
EJEMPLO 1.4.  Calcular la media de una serie de números positivos, suponiendo que los datos se leen desde una terminal. Un valor de cero --como entrada-- indicará que se ha alcanzado el final de la serie de números positivos.

El primer paso a dar en el desarrollo del algoritmo es descomponer el problema en una serie de pasos secuenciales. Para calcular una media se necesita sumar y contar los valores. Por consiguiente, el algoritmo en forma descriptiva es:

inicio
     1. Inicializar contador de números C y variable Suma S a cero (S ← 0, C ← 0).
     2. Leer un número en la variable N (leer (N)).
     3. Si el numero leído es cero: (si (N = 0) entonces).
          3.1 Si se ha leído algún número (Si C > 0).
               - Calcular la media; (media ← S/C)
               - Imprimir la media; (Escribe (media)).
          3.2 Si no se ha leído ningún número (Si C = 0).
               - Escribir no hay datos.
          3.3 Fin del proceso.
     4. Si el número leído no es cero: (Si (N <> 0 )) entonces
          - Calcular la suma; (S ← S + N).
          - Incrementar en uno el contador de números; (C ← C + 1).
          - Ir al paso 2.
fin

El algoritmo anterior escrito en pseudocódigo y en C++ es el siguiente:

Algoritmo escrito en pseudocódigo	Algoritmo escrito en C++
algoritmo media   inicio     variables       entero: N, C, S;       real: media;   C ← 0;   S ← 0;   repetir     leer (N)    si N <> 0 entonces     S ← S + N;     C ← C + 1;    fin si   hasta N = 0   si C > 0 entonces    media S / C    escribe (media)   sino    escribe (“no datos”)   fin si fin	#include <cstdlib> #include <iostream> using namespace std; int main (int argc, char *argv[]) {   int N, C, S;   float media;   C = 0; S = 0;   do   {     cin >> N;     if (N =! 0)     {       S = S + N;       C = C + 1;     }   }while (N != 0)   if (C > 0)     {       media = S / C;       cout << media;     }   else       cout << “no datos”;   return 0; }

------------------------------------------------------------------------------------------------------------------------------------------------------------------
EJEMPLO 1.5 Algoritmo que lee un número entero positivo n, y suma los n primero números naturales.

Inicialmente se asegura la lectura del número natural n positivo. Mediante un contador C se cuentan los números naturales que se suman, y en el acumulador Suma se van obteniendo las sumas parciales. Además del diagrama de flujo se realiza un seguimiento para el caso de la entrada n = 5.

Variables Entero: n, Suma, C

El algoritmo anterior escrito en pseudocódigo es y C++ es el siguiente:

Algoritmo escrito en pseudocódigo	Algoritmo escrito en C++
algoritmo suma_n_naturales   inicio     variables       entero: Suma, C, n;   repetir     leer (n)   hasta n > 0   C ← 0;   Suma ← 0;    fin si   mientras C < n hacer    C ← C + 1;    Suma ← Suma + C;   fin mientras   escribe (Suma) fin	#include <cstdlib> #include <iostream> using namespace std; int main (int argc, char *argv[]) {   int Suma, C, n;   do     cin >> n;   while (n <= 0);   C = 0; Suma = 0;   While (C < n)   {     C = C + 1;     Suma = Suma + C;   }   cout << Suma;   return 0; }