Palíndromo / Capicúa

El ejercicio de detectar si una secuencia de caracteres (o dígitos) es un palíndromo (capicúa)  es uno de los ejercicios más completos, podemos ver: recorrido de vectores, condicionales, uso de variables booleanas y tratamiento de cadenas.

Un ejemplo de palíndromo es la palabra "Radar", si la leemos de izquierda a derecha o viceversa leeremos lo mismo.

¿Cómo saber si es una palíndromo?
Hacemos la lectura en un sentido y otro y comprobamos que decimos lo mismo, esta sería la versión resumida de lo que realmente hace nuestro cerebro. Pero si nos detenemos a pensar en cómo le diríamos al ordenador (procesador) que lo haga ¿cómo lo haríamos?
Si leemos al mismo tiempo en ambas direcciones y comprobamos que cada letra que vamos leyendo es la misma, diríamos que si todas y cada una de las letras que leemos en ambas direcciones son las mismas es un palíndromo. En complemento a este razonamiento podemos decir también que en la comparación letra a letra que hacemos al leer una misma palabra en sentidos opuestos, basta con que algún par difiera para que la palabra NO ses un palíndromo.

Dicho esto, es mucho más claro verlo en código comentado:


//variable que almacena el texto (máximo 10 caracteres)
char palabra[10]; 

//variables para recorrer la palabra
int indicePrimeraLetra = 0; //índice inicio recorrido de izq. a der.
int indiceUltimaLetra; //índice inicio recorrido de der. a izq.

//variable que determina si la palabra es palíndromo
bool esPalindromo = true;

//llenamos el texto con información desde teclado
printf("Ingresa la palabra: ");
scanf ("%s",palabra);
printf("\nLa palabra ingresada es: %s", palabra);

//tratamiento de la cadena
//inicializamos con la última posición para recorrer de der. a izq.
indiceUltimaLetra = strlen(palabra) - 1;
printf("\nNúmero de elementos de la palabra: %d", strlen(palabra));

//realizamos la lectura en ambas direcciones, termina cuando se cruzan los índices o cuando alguna de las letras no coincide
while(esPalindromo && indicePrimeraLetra < indiceUltimaLetra)
{
   //basta que un par de letras no coincida para que NO sea palíndromo
   if (palabra[indicePrimeraLetra] != palabra[indiceUltimaLetra])
      {esPalindromo = false;}
            
   indicePrimeraLetra++;//incrementa índice lectura izq. a der.
   indiceUltimaLetra--;//decrementa índice lectura der. a izq.
}


printf("\n¿Es palindromo? ");
if(esPalindromo) printf("SI");
else printf("NO");


Importante!!
- La inicialización de la variable indiceUltimaLetra se hace después de leer la palabra a evaluar, porque tiene que posicionarse en la última letra y hasta no leer la palabra no sabemos la longitud.
- La dirección del recorrido de las lecturas se determina al incrementar la variable indicePrimeraLetra y al decrementar la variable indiceUltimaLetra
- La condición de salida del while: Si sale por la primera condición es que la palabra NO es un palíndromo, si sale por la segunda condición ha terminado de comprobar y todas coinciden por tanto SI es palindromo.

Finalmente...
¿Sabéis por qué el recorrido termina a la mitad de la palabra (condición indicePrimeraLetra < indiceUltimaLetra) y por que no cuando indicePrimeraLetra llega hasta el final de la palabra (strlen(palabra))?

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.