El elemento neutro de la suma y el producto

Hay recuerdos muy lejanos al aprender a sumar o a multiplicar, en el cole (o en la universidad) nos explicaban las propiedades de la suma y del producto: propiedad transitiva, propiedad distributiva, etc. una de las propiedades (generalmente la primera) es la propiedad del elemento neutro que dice:

A todo número que se le sume cero da el mismo número. -> El 0 es el elemento neutro de la suma

A todo número que se le multiplique por uno da el mismo número. -> El 1 es el elemento neutro de la multiplicación.

¿A que viene todo esto del elemento neutro? Esto va relacionado a operaciones que hacemos de forma acumulativa, por ejemplo:

1. Calcule la suma de los N primeros números enteros.

2. Calcula el factorial de un número N.

En ambos casos, una de las soluciones por las que se podría optar es hacer un bucle que acumule la suma o el producto de esta forma:

//ejemplo 1

Para i=1 hasta N hacer

  suma = suma + i;

Fin_Para

//ejemplo 2

Para i=1 hasta N hacer

  factorial = factorial *  i;

Fin_Para

En ambos casos al estar calculando un valor acumulado, reutiliza el valor de la variable en la iteración anterior (suma utiliza a suma para calcularse a si misma, lo mismo con factorial).

¿Pero qué pasa en la primera iteración? En la primera iteración es necesario que suma y factorial simplemente sean igual a "i", por este motivo es necesario (indispensable) inicializar ambas variables con el valor del elemento neutro. Los algoritmos completos quedarían así:

//ejemplo 1

suma = 0: //variable inicializada con el valor del elemento neutro de la operación que haremos

Para i=1 hasta N hacer

  suma = suma + i //la primera iteración: suma = 0 + i;

Fin_Para

//ejemplo 2

factorial = 1 //variable inicializada con el valor del elemento neutro de la operación que haremos

Para i=1 hasta N hacer

  factorial = factorial *  i: //la primera iteración:  factorial = 1 * i

Fin_Para

Para cualquier cálculo en que utilicemos acumuladores es absolutamente necesario inicializarlos correctamente, por lo general con el valor del elemento neutro de la operación de acumulación.

Algo de matrices

Una de las dificultades más comunes son los vectores, sobretodo comprender la diferencia entre el indice de un vector (posición) y el valor contenido en el índice del vector (datos).

Para complicarlo aún más viene el tema de las matrices, que no son más que vectores pero en dos dimensiones, esto es que ahora el índice está formado por dos posiciones.

Sobre teoría de matrices se ha escrito mucho, lo que pretendo en este post es simplemente mostrar como acceder a una matriz y determinar si es una matriz identidad o no (¿Qués es una matriz identidad?). Para este fin utilizaremos el recorrido secuencial de una matriz fila a fila y para cada elemento de la fila veremos si tiene el valor correcto que le corresponde a la matriz identidad (1 en la diagonal y 0 en el resto de campos):

int esIdentidad = 1; //variable que indica si la matriz es identidad o no
int x, y = 0; //indice de filas y columnas
int N=10;//dimensión de la matriz

//se asumen que la matriz es de Identidad hasta que se muestre que tenga un valor incorrecto
while(esidentidad)
{
  //recorre todos los elementos de la fila hasta que encuentre algún error o termine la fila
  for(int y=0; y<N && esIdentidad; y++)
  {
    //la diagonal debe tener el valor 1, en caso contrario no puede ser una matriz Identidad
    if(x==y && Matriz[x][y] !=1) esidentidad = 0;
    //los que no están en la diagonal deben ser 0, en caso contrario no puede ser una matriz identidad
    if(x!=y && Matriz[x][y] !=0) esidentidad = 0;
  }
  x++;//cada iteración del while se corresponde con cada fila de la matriz  
}

//resultado de la evaluación
if(esIdentidad) print("La matriz es identidad");
else print("La matriz no es identidad");


Vemos que el el indice de la  matriz está compuesto por dos posiciones: x e y.
Vemos que el valor en una posición determinada de la matriz se accede a través de las posiciones: Matriz[x][y].
Vemos que cuando encuentra un valor que no se corresponde con la matriz identidad cambia la variable esIdentidad para salir inmediatamente de los bucles for y while, puesto que al primer valor incorrecto no hace falta seguir recorriendo la matriz, ya sabemos que no es de Identidad.
Vemos que para recorrer una matriz hace falta 2 bucles anidados, en este caso el while recorre las filas de la matriz y el for recorre las columnas para cada fila.

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.

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);

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;