Números primos

Empiezo un nuevo curso y revisando el material que debo tratar con una de mis alumnas de este semestre me encuentro con un problema clásico, un enunciado que se repite mucho ya que mezcla conceptos de estructuras de control (condicionales e iterativas) y aplica conceptos matemáticos, este post va de los números primos.

El problema busca determinar si un número es primo o no, por lo tanto, preparamos la información del problema:

¿Qué tengo?
Tengo un número entero positivo mayor que 1

¿Que quiero?
Determinar si dicho número es primo o no

¿Cómo lo hago?
Primero debemos tener claro lo que es un número primo, dejamos el enlace a wikipedia, en el que dice: un número primo es un número natural mayor que 1 que tiene únicamente dos divisores distintos: él mismo y el 1. 
Para que quede más claro:
5 es primo, porque sólo es divisible entre 1 y 5, no es divisible entre 2, ni 3 ni 4 y no consideramos evaluar si es divisible entre 6, 7 o más porque el divisor de un número debe ser siempre menor o igual a él.
6 no es primo, porque es divisible entre 2 y 3.

Generalizando, basta con encontrar un número entre 1 y N que sea divisor de N, para decir que N no es primo.

Analizamos, todo lo que hemos dicho hasta ahora:
1. Basta con encontrar un número: esto se traduce en una iteración con condicionante booleana que se detendrá cuando encuentre un divisor.
2. Entre 1 y N: esto se traduce como que la iteración tendrá el condicionante que el divisor buscado debe iterar entre 1 y N.

Planteamos el pseudocódigo:
//asumimos que tenemos una función con parámetro N que es un entero mayor a 1
//definimos la condicionante booleana
bool esPrimo = true; //asumimos que es primo a menos que encontremos un divisor
//definimos variable que itera entre 1 y N buscando un divisor
int iDivisor = 2;
//iteración
mientras(esPrimo AND iDivisor < N)
{
    //condicionante que puede hacer que esPrimo cambie: cuando encuentra un divisor
    SI (N % iDivisor == 0) //la operación % indica que calcula el residuo de la división de N entre iDivisor
    {
      esPrimo = false;
    }fin_SI
    iDivisor++; //incrementa el iDivisor para continuar la búsqueda
}fin_mientras
//puede salir de la iteración porque encontró un divisor, en ese caso esPrimo será falso
//puede salir de la iteración porque no encontró divisor, en ese caso iDivisor es igual a N
//condicionante
SI(esPrimo)
{
   imprime("Es Primo")
}
Caso contrario
{
  imprime("No es primo")
}

Este problema, como todos, se puede resolver de distintas formas, si revisáis el enlace de wikipedia por ejemplo, podréis ver que los números primos cumplen muchas propiedades que pueden aplicarse al programa para mejorar el rendimiento (por ejemplo reducir el número de iteraciones), sobretodo si se quieren evaluar números muy grandes.

Vectores: Ordenamiento por Intercambio

En este post veremos paso a paso cómo ordenar un vector de números de 5 elementos de forma ascendente. Luego generalizaremos la solución a un vector de N elementos.

Planteamiento del Problema

¿Qué tengo?
Un vector de 5 números

¿Qué quiero?
Ordenar el vector de forma ascendente

¿Cómo lo hago?

- Tenemos 5 elementos, de los cuales iremos ordenando posición a posición (empezando por la posición 0)

- Una posición está ordenada cuando todos los elementos de las posiciones posteriores son mayores que el elemento de la posición que se está ordenando.

<imagen de posición i ordenada>

- Si ordenamos posición a posición, vemos que si ordenamos de la posición 0 a la 3, la cuarta quedará ordenada automáticamente (no hay posiciones posteriores con la cual compararla)

Siguiendo estas pautas, haremos el procedimiento para el vector de 5 elementos, razonando a cámara lenta:
(ver enlace)

Ahora que hemos visto poco a poco cómo sería la ejecución del algoritmo, planteamos el pseudocódigo para el vector de 5 elementos:

/***Método de Ordenamiento General***/

iPos = 0; //representa cada posición del vector

Para cada elemento del Vector hasta la posición 3

  OrdenarDesde(iPos); //Ordena el vector a partir de la posición iPos

Fin Para

/***Método OrdenarDesde***/

iPosCompara = iPos + 1; //esta variable es la que recorre las posiciones posteriores a iPos para comparar

elemento1 = Vector[iPos];

Mientras (iPosCompara <= 4)

   elemento2 = Vector[iPosCompara];

   //Se comparan: elemento1 y elemento2

   Si elemento1<= elemento2 //no tiene que cambiar de posición

      iPosCompara++

   Caso Contrario

      Intercambia(iPos, iPosCompara) //intercambia los elementos

      iPosCompara =  iPos + 1; //vuelve a empezar el ordenamiento desde la posición iPos

      elemento1 = Vector[iPos];

   Fin Si

Fin Mientras

/***Método Intercambia***/

aux = Vector[iPos]; //guarda temporalmente el valor de la posición iPos

Vector[iPos] = Vector[iPosCompara];

Vector[iPosCompara] = aux; //utiliza el valor guardado en aux para el intercambio

Para terminar, os dejo el mismo código como un proyecto de consola en c# generalizado para vectores de N elementos.
- Programa Principal
- Clase con Algortimo de Ordenamiento

Sumatorio de valores de un vector

En esta ocasión, trabajaremos con un ejemplo práctico para explicar cómo hacer la sumatoria de valores de un vector.
En este ejemplo tenemos una factura de este estilo:

Descripción	Precio unitario	Cantidad	Total
Boligrafo	1,50	2	3,00
Papel A4 (pack. 100)	4,75	1	4,75
		Total	7,75

Si tenemos una clase que representa cada linea del detalle de la factura, seria de este estilo:

Class Detalle{
  private String descripción;
  private float precioUnitario;
  private int cantidad;
  private float totalLinea;

  //y los respectivos métodos gets y sets para cada atributo
}

Por otra parte tenemos una clase que representa la factura y que tiene varias lineas en el detalle (array de Detalle)

Class Factura{
  private Detalle[100] lineas; //como máximo tiene 100 líneas de detalle
  private int numLineas; //esta variable indica el número de líneas que tiene la factura, siempre <= 100
  private float totalFactura; //esta variable contendrá el total de la factura
}

Desde nuestro programa principal suponemos que la se han cargado los datos de la factura, por tanto tendríamos:

Factura miFactura = new Factura(); //instanciamos el objeto miFactura de tipo Factura
//...
//aquí rellenamos la información en cada linea de detalle
//...
//ahora calculamos el total de la factura
//recorremos todas las lineas de la factura
int numLineasFactura = miFactura.getNumLineas();
float totalCalculoFactura = 0; //inicializamos a 0
for(int i = 0; i < numLineasFactura; i++)
{
   totalCalculoFactura += miFactura.getDetalle()[i].getTotalLinea();
}
//al terminar el for, la variable totalCalculoFactura contiene el total
//guardamos el total en la factura
miFactura.setTotalFactura(totalCalculoFactura);

La clave de este ejemplo está en dos líneas:
1. Sumar el total de cada linea:
    totalCalculoFactura += miFactura.getDetalle()[i].getTotalLinea();

En cada iteración se va incrementando la variable totalCalculoFactura con el valor del total de cada linea. Para acceder al total de cada linea se hace a través de método getDetalle() que retorna el vector de Detalles de la factura, utilizamos el índice i para posicionarnos linea a linea en cada iteración y estando en la linea accedemos al total de la linea mediante el método getTotalLinea().

2. Inicialización de la variable acumuladora:
    float totalCalculoFactura = 0;

La variable totalCalculoFactura es la que va acumulando el total de la suma de cada linea, es muy importante que esté inicializada a 0, debido a que no todos los lenguajes de programación inicializan a 0 cuando se define la variable, es decir, si sólo la definimos y no la inicializamos nada nos garantiza que esa variable contenga el valor 0.

Finalmente, hacemos una variación al problema y suponemos que las lineas de la factura contienen la descripción, el precio unitario, la cantidad pero no tienen calculado el total por linea, en ese caso se podría modificar el programa para realice el cálculo del total en cada línea y a la vez el total de la factura:

int numLineasFactura = miFactura.getNumLineas();
float totalCalculoFactura = 0; //inicializamos a 0
float precioUnitarioLinea;
int cantidadLinea;
for(int i = 0; i < numLineasFactura; i++)
{
   //obtiene el precio unitario y la cantidad por linea
   precioUnitarioLinea = miFactura.getDetalle()[i].getPrecioUnitario();
   cantidadLinea = miFactura.getDetalle()[i].getCantidad();
   //calcula el total de linea y lo guarda en la linea
   miFactura.getDetalle()[i].setTotalLinea(precioUnitarioLinea  * cantidadLinea );
 
   //como el total de linea ya está calculado y guardado se puede utilizar para calcular el total de la factura
   totalCalculoFactura += miFactura.getDetalle()[i].getTotalLinea();
}
//al terminar el for, la variable totalCalculoFactura contiene el total
//guardamos el total en la factura
miFactura.setTotalFactura(totalCalculoFactura);

Búsqueda del valor máximo

Uno de los problemas académicos más comunes es el de la búsqueda del valor máximo o mínimo dentro de una lista. Una aplicación que podríamos darle a este problema sería por ejemplo con fines estadísticos, calcular para una muestra de datos: el máximo, el mínimo y el valor medio.

Antes de plantear el problema vamos a intentar "pensar en cámara lenta" y preguntarnos qué haría nuestra cabeza si tuviésemos que encontrar el valor máximo de una muestra de datos. Suponemos la siguiente muestra de datos:

2, 5, 10, 1, 7

A simple vista diríamos que el máximo es 10, pero ¿Cómo es que lo hemos determinado? si lo vemos en cámara lenta nos daríamos cuenta que:

1. Comparamos el 2 y el 5, como el 5 es mayor, nos quedamos con el 5 y descartamos el 2.
2. Comparamos el 5 con el 10, como el 10 es mayor, nos quedamos con el 10 y descartamos el 5.
3. Comparamos el 10 con el 1, como el 10 es mayor, nos quedamos con el 10 y descartamos el 1.
4. Comparamos el 10 con el 7, como el 10 es mayor, nos quedamos con el 10 y descartamos el 7.

Finalmente el último con el que nos quedamos fue el 10, por tanto, es el 10 el valor máximo.

Si analizamos cada uno de los pasos, vemos que en cada uno de ellos se compara un elemento de la lista con el valor con el que nos hemos quedado en el paso anterior. Si llevamos esto a lenguaje de programación  se puede plantear como un recorrido por todos los elementos de una lista en la que cada iteración realza una comparación entre el valor actual con el máximo de la iteración anterior, por tanto sabemos que debemos tener una estructura así:

//creamos la muestra de datos
int listaNumeros [5]; 
listaNumeros[0] = 2;
listaNumeros[1] = 5;
listaNumeros[2] = 10;
listaNumeros[3] = 1;
listaNumeros[4] = 7;

//tenemos un recorrido de la muestra
for(int i=0; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Hasta aquí tenemos la estructura básica del algoritmo, ahora le hacemos algunos ajustes, teniendo en cuenta que la variable valor_maximo no la hemos inicializado.
Si la inicializaramos con 0, nos corremos el riesgo de que para otra muestra tengamos valores negativos y en ese caso el máximo siempre sería 0, lo mejor es tomar como máximo algún valor de la muestra, por ejemplo el primero.

//inicializamos el valor máximo con el primer elemento de la muestra
int valor_maximo = listaNumeros[0];

//tenemos un recorrido de la muestra
for(int i=0; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Ahora que nos aseguramos que el valor_maximo de la muestra sea uno de los elementos de la muestra, vemos que la primera iteración comparará listaNumeros[0] y valor_maximo y que siempre serán iguales en la primera iteración, por tanto el código que está dentro del if núnca se ejecutará en la primera iteración, así que podemos aplicar una optimización haciendo que empiece la iteración a partir del segundo elemento, de la siguiente forma.


//inicializamos el valor máximo con el primer elemento de la muestra
int valor_maximo = listaNumeros[0];

//el recorrido se inicia en el segundo elemento
for(int i=1; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Finalmente, aprovecharemos el mismo recorrido para calcular el máximo, el mínimo y la media:

//creamos la muestra de datos
int listaNumeros [5]; 
listaNumeros[0] = 2;
listaNumeros[1] = 5;
listaNumeros[2] = 10;
listaNumeros[3] = 1;
listaNumeros[4] = 7;

int valor_maximo = listaNumeros[0];
int valor_minimo = listaNumeros[0];
int media = listaNumeros[0];

for(int i=1; i<5;i++)
{
  //Búsqueda del máximo
  if (listaNumeros[i] > valor_maximo)
  {
    valor_maximo = listaNumeros[i];
  }

  
  //Búsqueda del mínimo
  if (listaNumeros[i] < valor_minimo)
  {
    valor_minimo = listaNumeros[i] ;
  }

  //cálculo de media

  media +=  listaNumeros[i] ;

}

//al terminar el recorrido la variable media contiene la suma de todos los elementos
//dividimos entre el número de elementos para calcular la media
media = media/5;

//En este punto tenemos calculado los tres valores estadísticos de la muestra, los imprimimos en pantalla
printf("valor_maximo: ", valor_maximo);
printf("valor_minimo: ", valor_minimo);
printf("media: ", media);

Búsqueda con recorrido secuencial

Uno de los problemas más frecuentes es el tratamiento de vectores (Array), para esto es necesario tener claros los siguientes conceptos:

- El vector es una lista de elementos, donde todos los elementos son del mismo tipo.

- El vector tiene un número de elementos fijos, cuando se crea, se reserva memoria para todos esos elementos. Por ejemplo, definimos un vector de 15 elementos de tipo unsigned char (1 byte), entonces estaremos reservando 15 bytes en la memoria.

- Es muy importante tener clara la diferencia entre posición y valor. Si el vector tiene N elementos, entonces tendremos posiciones que variarán entre 0 y N-1, y los valores en cada posición dependerán del tipo de elementos del vector.

Para el vector:

int listaNumeros [5]; //vector de 5 elementos de tipo int

Se ha reservado memoria para 5 variables de tipo int, para acceder a los valores de esas variables lo hacemos de la siguiente forma:

listaNumeros[0] = 2; //el valor en la posición 0 es 2

listaNumeros[1] = 5; //el valor en la posición 0 es 5

listaNumeros[2] = 4; //el valor en la posición 0 es 4

listaNumeros[3] = 3; //el valor en la posición 0 es 3

listaNumeros[4] = 1; //el valor en la posición 0 es 1

Se comete mucho el error de acceder a listaNumeros[5], esto dará un error de fuera de rango del vector, porque las posiciones varían entre 0 y 4, por tanto:

listaNumeros[5] = 3; //ERROR!!! no se puede realizar esta asignación porque se encuentra fuera de rango

Para buscar un elemento en un vector que cumpla ciertas características, debemos recorrer uno a uno cada elemento y determinar si el valor en cada posición cumple con las características que estamos buscando. Este recorrido uno a uno de los elementos se le denomina recorrido secuencial.

Por ejemplo, si queremos imprimir por pantalla los números del vector listaNumeros que son pares, haremos:

int N = 5;
for(int i=0; i<N; i++)
{
    //listaNumeros[i] contiene el valor en la posición i
    if(listaNumeros[i] % 2 == 0) //verifica si el valor es par, en ese caso imprime
       printf(listaNumeros[i]);
}

la variable i nos ayuda a recorrer las posiciones del vector (i varía desde 0 hasta N-1).

la variable N representa el número de elementos del vector, notar que las iteraciones del for sólo se ejecutan si i<N
La característica que buscamos es que el valor sea par, para eso utilizamos la operación % que calcula el resto de dividir listaNumeros[i] entre 2, en el caso que sea par ese resto es 0 y en ese caso imprimimos.

Si modificamos el problema y ahora sólo nos interesa mostrar el primer valor par, ¿Qué modificación tendríamos que hacer a programa anterior?

Ahora la característica no es sólo que sea par sino que además sea el primero, por tanto introducimos una variable booleana que nos indique si es el primero en encontrarse o no.

int N = 5;
boolean bPrimerPar = false
for(int i=0; i<N && !bPrimerPar; i++)
{
    //listaNumeros[i] contiene el valor en la posición i
    if(listaNumeros[i] % 2 == 0) //verifica si el valor es par, en ese caso imprime
    {   printf(listaNumeros[i]);
         bPrimerPar = true;
    }
}

Cuando se encuentra el primer valor par, la variable se vuelve true y la validación !bPrimerPar se hace falsa por tanto termina de ejecutar el bucle.

Hemos visto que se pueden realizar búsquedas en las que es necesario recorrer todos los elementos del vector y otras en las que sólo lo recorreremos hasta que encontremos el valor que estamos buscando.

Lo que no debemos olvidar en una iteración

Este post intenta dar las 3 claves principales que no debemos olvidar nunca al realizar iteraciones:

1. Definir e inicializar la variable que itera: Esta variable será la que determine en qué iteración nos encontramos y servirá para terminar la iteración.

2. La condición tope para que termine la iteración: Esta condición evalúa la variable itera y determina si debe continuar iterando o no.

3. La variación de la variable que itera: Esta variación se debe realizar en cada iteración para asegurar que la variable en algún momento cumplirá la condición tope.

Un ejemplo sencillo: Sumar los 10 primeros números enteros positivos:

//variable que acumula la suma
int Suma = 0;
//variable que itera: se inicializa con el primer entero positivo
int i = 1;

//la condición es que la variable iteradora no supere 10, así asegura que se suman los 10 primeros números
while (i <= 10)
{
    suma += i;
    //variación de la variable i, se incrementa en 1
    i++;
}

//cuando salimos del while la variable i vale 11 y la variable suma contiene la suma desde 1 hasta 10

Ahora haremos un ejemplo un poco más complejo, haremos una función que calcule la integral entre 0 y 1 de la función f(x) = x^2

El método que utilizaremos será discretizar la función en incrementos de h = 0.001

float inicio = 0;
float final = 1;
float h = 0.001; //variaciones 
float integral = 0; //en esta variable se guarda el valor calculado de la integral
int it = 0; //esta variable guarda el número de iteraciones que se realicen

float i = inicio; //variable que itera y que se evalúa en la condición tope
//la condición que marca el tope es que no sobrepase el final = 1
while (i <= final)
{
    integral += i * i ; //la evaluación de la función f(x)=x^2 en el punto i es f(i) = i^2 = i*i
    i += h; //incremento de la variable iteradora
    it++;
}
//cuando termina el bucle la variable i contiene un número > a final
//la variable integral contiene la suma de la evaluación de la función en todos los puntos i
//la variable it contiene el número total de iteraciones que se realizaron, que es igual al número de veces que //se evaluó f(i)

//para terminar de calcular la integral se divide entre el número de iteraciones
integral = integral / it;

Las variables booleanas

Nos referimos a variables booleanas a aquellas que utilizamos para indicar que algo es verdadero o falso.

Lo importante de estas variables es que sólo pueden tomar dos valores: verdadero o falso, no hay más posibilidades y esta propiedad la utilizaremos para tomar decisiones, por ejemplo: tengo una variable que se llama bTarifaMenor y que es verdadera si tengo una variable edad de tipo entero <= 12 y en caso contrario será falsa. Podríamos decir que si la variable bTarifa Menor es verdadera aplicaremos un descuento del 20% en el precio de un producto.

La definición de estas variables dependerá del lenguaje de programación que estemos utilizando. No podemos encontrar con los tipos: booblean, bool, Boolean, Bool. En cuanto tengamos claro cual de los tipos es el que utiliza el lenguaje con el que estamos programando definiremos la variable:

Para c# definiríamos así:
bool bTarifaMenor; //definimos la variable booleana
bTarifaMenor = False; //inicializamos la variable con valor falso

int edadCliente = 13; //definimos e inicializamos la variable edad en 13

Para aplicar la lógica de decisión que evalúa el valor de la variable edadCliente utilizamos la instrucción if que sigue la siguiente sintaxis:

if (condición que se evalúa)
{
  //Entre estas llaves va el conjunto de instrucciones que se ejecutan si se cumple
  //la condición que se evalúa
}

aplicando la instrucción de evaluación if en el ejemplo:

//la condición de evaluación es que la edad del cliente sea menor o igual que 12
//dejamos la referencia de los operadores disponibles que iremos aplicando en los ejemplos
if (edadCliente <= 12)
{
  bTarifaMenor = True; //asignamos el valor de verdadero a la variable booleana
}

Las llaves “{“ y “}” contienen un conjunto de instrucciones que sólo se ejecutarán si se cumple la condición que se evalúa dentro del paréntesis, si ese conjunto de instrucciones consta de una sola instrucción como es el caso del ejemplo, se pueden obviar las llaves:

if (edadCliente <= 12)
  bTarifaMenor = True; //asignamos el valor de verdadero a la variable booleana

Sin embargo, si Ud. está empezando a programar le recomiendo que utilice siempre las llaves,  así podrá distinguir claramente cuáles son las instrucciones que se ejecutarán en el caso que se cumpla la condición del if.

Para terminar el ejemplo, aplicaremos el descuento a los menores utilizando como condicional a la variable booleana:

if (bTarifaMenor)
{
 //aquí hace las instrucciones necesarias para aplicar el 20% de descuento en el precio
}

En el caso de este if la condición que se evalúa es simplemente una variable booleana, por que en sí esta variable es True o False, en el caso que su valor sea True se ejecutará el bloque de instrucciones que se encuentra entre las llaves (descuento en el precio).

Aquí más información sobre la instrucción if