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))?
martes, 24 de noviembre de 2015
jueves, 5 de noviembre de 2015
Asignación (=) VS. Comparación (==)
Un error típico es confundir la operación lógica de comparación IGUAL con la de asignación, lo peor de este error es que no se detecta en la compilación ni en la ejecución, sino que genera que el programa realice un flujo diferente al esperado.
La operación de asignación (=) cuando se realiza correctamente devuelve un 1 como resultado indicando que todo ha ido bien, por ejemplo:
int a; //definición de variable a de tipo int
if( a = 3) //si la operación de asignación se realiza correctamente realiza lo que está dentro del if
{
...
}
Podría ocurrir que por un error físico o lógico de memoria la operación a=3 se realice mal, en ese caso no se realizaría lo que está dentro del if.
Un ejemplo típico es utilizar variables para determinar el fin de una iteración, como ejemplo tenemos un programa que realiza una operativa siempre que el usuario pulse 1, cuando el usuario marca una tecla distinta termina la ejecución del programa. La estructura del algoritmo sería la siguiente:
int fin_ejecucion = 1; //variable que determina el fin de la ejecución del programa
while (fin_ejecucion == 1)
{
//aquí realiza la función del programa
//cuando termina la ejecución pregunta si quiere continuar
write("Pulse 1 si desea continuar");
read(fin_ejecucion); //lee del teclado lo que el usuario quiere
}
Si por error, cambiásemos la comparación por la asignación, la consecuencia sería que la operación fin_ejecucion = 1 siempre sería TRUE y por tanto nunca dejará de ejecutar el bucle.
Parece trivial, cuando en resolución de ejercicios (sobretodo los que se hacen en papel), se insiste mucho sobre este tema, pero es muy importante tenerlo en cuenta debido a que el compilador no lo puede detectar (no es un error de sintaxis) y tampoco lanza error en tiempo de ejecución, simplemente el programa hace algo que no le hemos pedido.
En otros lenguajes de programación como el PLSQL es más difícil caer en este error porque la instrucción de asignación se representa con := y la de comparación con =, por esto es importante conocer el set de instrucciones básicas (lógicas y aritméticas) antes de empezar a programar.
La operación de asignación (=) cuando se realiza correctamente devuelve un 1 como resultado indicando que todo ha ido bien, por ejemplo:
int a; //definición de variable a de tipo int
if( a = 3) //si la operación de asignación se realiza correctamente realiza lo que está dentro del if
{
...
}
Podría ocurrir que por un error físico o lógico de memoria la operación a=3 se realice mal, en ese caso no se realizaría lo que está dentro del if.
Un ejemplo típico es utilizar variables para determinar el fin de una iteración, como ejemplo tenemos un programa que realiza una operativa siempre que el usuario pulse 1, cuando el usuario marca una tecla distinta termina la ejecución del programa. La estructura del algoritmo sería la siguiente:
int fin_ejecucion = 1; //variable que determina el fin de la ejecución del programa
while (fin_ejecucion == 1)
{
//aquí realiza la función del programa
//cuando termina la ejecución pregunta si quiere continuar
write("Pulse 1 si desea continuar");
read(fin_ejecucion); //lee del teclado lo que el usuario quiere
}
Si por error, cambiásemos la comparación por la asignación, la consecuencia sería que la operación fin_ejecucion = 1 siempre sería TRUE y por tanto nunca dejará de ejecutar el bucle.
Parece trivial, cuando en resolución de ejercicios (sobretodo los que se hacen en papel), se insiste mucho sobre este tema, pero es muy importante tenerlo en cuenta debido a que el compilador no lo puede detectar (no es un error de sintaxis) y tampoco lanza error en tiempo de ejecución, simplemente el programa hace algo que no le hemos pedido.
En otros lenguajes de programación como el PLSQL es más difícil caer en este error porque la instrucción de asignación se representa con := y la de comparación con =, por esto es importante conocer el set de instrucciones básicas (lógicas y aritméticas) antes de empezar a programar.
domingo, 25 de octubre de 2015
Operación Residuo (MOD)
El set de instrucciones de
cada lenguaje de programación puede llegar a ser tan amplio que no
llegamos a aprenderlo todo y mucho menos saber en qué casos podemos
sacar ventaja de utilizar una instrucción determinada.
En este post quiero
hablar de la instrucción de Residuo,
conocida como % en C, C++, php,
java o MOD en COBOL, PLSQL,
Pascal.
Recordando un poco de
matemáticas, sabemos que:
Dividendo = Cociente *
Divisor + Residuo
Ejm. 7 = 3 * 2 + 1
Si despejamos el residuo
sería:
Residuo = Dividendo -
(Cociente * Divisor)
La operación Residuo se
calcula utilizando el Dividendo y el cociente o el dividendo y el
divisor. La sintaxis sería:
Residuo = Dividendo %
Cociente (1 = 7 % 3)
Residuo = Dividendo %
Divisor (1 = 7 % 2)
¿En qué casos podemos
utilizar esta operación?
Sólo os daré dos casos típicos:
Realizar
una acción cuando un número es múltiplo de otro
Imprimir
los 30 primeros múltiplos de 3
int
numerosImpresos = 0 //controla el número de números impresos
int
contador = 1; //Es el número que hace de Dividendo en la operación
while(numerosImpresos
< 30)
{
if (contador % 3 == 0) //si el residuo es 0, es una división exacta por tanto es múltiplo
{
Console.write(contador);
}
contador ++;
}
Realizar
un cambio de base
Cambiar
el número 5 de base decimal a binario.
Como
se cambia a sistema binario de utiliza el divisor = 2 (Base N,
implica divisor N)
int
dividendo = 5;
int
divisor = 2;
string
cambioBase = “”;
while(dividendo
/ divisor >1)
{
residuo = dividendo % divisor;
dividendo = dividendo / divisor;
cambioBase = residuo + cambioBase; //se va concatenando a la izquierda
}
cambioBase
= dividendo + cambioBase; //en esta variable está el resultado "101"
¿Se os ocurre otro ejemplo?
martes, 1 de septiembre de 2015
El mejor algoritmo
Este post está dedicado a una persona que quiero mucho y que a pesar que cambió la informática por la economía, aún tiene un bichito informático dentro que se pregunta: ¿cómo saber si un algoritmo es mejor que otro?
La respuesta es el clásico "depende":
- Depende de los datos, en algunos casos a medida que se evalúan más datos el algoritmo se va degradando, porque la función del rendimiento es exponencial por ejemplo.
- Depende de la arquitectura, en algunos casos el procesador está preparado para soportar operaciones más complejas en menor número de instrucciones.
- Depende del objetivo, en algunos casos se puede hacer un algoritmo muy complejo y casi ininteligible, con lo que a otro programador le costaría mucho entenderlo como para probarlo o modificarlo, se debe tener siempre en consideración que además de apoyarnos en buenos comentarios en el código y nombres de variables que ayuden a la comprensión, el código en sí, si es para uso masivo y cualquiera puede modificarlo no debería ser tan complejo, sin embargo si es un código cerrado, se puede elevar la complejidad.
Existen más variables que hacen que un algoritmo sea mejor o peor que otro, pero en este post quería centrarme estrictamente en la función de rendimiento que nos puede ayudar a hacer comparaciones entre diferentes soluciones.
Para entender mejor esto del rendimiento, trataremos el cálculo del factorial de un número:
Problema: Calcular el Factorial de N, donde N es un numero Natural >= 1
Supuestos:
1) Cada instrucción tarda una unidad de tiempo T
2) No consideraremos el tiempo en que se reserva memoria en la función recursiva
Propuesta 1 de Factorial
Función FactorialIterativa(N)
F = N; --> T
//la variable i va desde N-1 hasta 1 y es la que se va multiplicando
i = N - 1; --> T
Mientras (i > 1) --> La comparación se realiza N-1 veces: T * (N-1)
F = F * i; --> La comparación se realiza N-2 veces: T * (N-2)
i = i - 1; --> La comparación se realiza N-2 veces: T * (N-2)
Fin_Para
Return F; --> T
Fin_Función
Tiempo Total = T + T + T * (N-1) + T * (N-2) + T * (N-2) + T = (3N - 2) T
Propuesta 2 de Factorial
Funcion FactorialRecursiva (N)
Si N = 1 --> Cada vez que se llama a la recursiva se hace la comparación, por tanto se hace N veces. N * T
Return N --> Esta se hace sólo una vez, la última. T
Caso Contrario
Return N * FactorialRecursiva(N-1) --> Se ejecuta N - 1 veces. (N - 1) * T
Fin_Si
Fin_Funcion
Tiempo Total = N * T + T + (N-1) * T = 2N * T
Con estas funciones de rendimiento, podríamos decir que para los supuestos considerados y para N > 2, la propuesta 2 tiene mejor rendimiento que la propuesta 1.
Con esto logramos tener una herramienta simple para comparar algoritmos, siempre bajo supuestos.
Sería muy difícil contemplar todas las variables que intervienen, pero podemos aproximarnos y nos puede servir para optar por algún algoritmo u otro.
sábado, 4 de julio de 2015
Juego: Tres en raya
Esta vez repasaremos matrices, funciones, condicionales e iteraciones, todo esto aplicado en el clásico juego del tres en raya, las reglas del juego son muy conocidas, sólo haré unos cuantos razonamientos previos antes de empezar a programar:
Sobre los turnos
Sabemos que son 2 jugadores que juegan
por turnos hasta que alguno gana o el tablero se llena
sin ganador (situación de empate).
Vemos que debe existir una iteración que finalice cuando el juego termina:
var fin_juego = false;
var turno = 0; //los jugadores son 0 y
1
while(!fin_juego)
{
//se hace la jugada
//si se gana en este turno fin_juego
= true;
//si el tablero se llena sin ganador
fin_juego = true;
turno = (turno + 1) % 2; //esto es
para cambiar el turno de 0 a 1 y de 1 a 0
}
Sabemos que es un tablero de 9 casillas
(3 filas y 3 columnas). En principio todas las casillas están vacías
y en cada turno se va llenando alguna de las casillas con la jugada
hecha en el turno.
Si todas las casillas están llenas y
no hay ganador, entonces es un empate.
Para controlar que el juego termine en
empate creamos un condicional en cada iteración que controle
si se llenó el tablero o no.
var fin_juego = false;
var turno = 0; //los jugadores son 0 y
1
var casillas_vacias = 9;
while(!fin_juego)
{
//se hace la jugada
casillas_vacias = casillas_vacias -
1; //al hacer la jugada disminuye en 1 las casillas vacías
//si se gana en este turno fin_juego
= true;
//si el tablero se llena sin ganador
fin_juego = true;
if(!fin_juego &&
casillas_vacias == 0) fin_juego = true;
turno = (turno + 1) % 2; //esto es
para cambiar el turno de 0 a 1 y de 1 a 0
}
Sobre la jugada
El jugador debe seleccionar la casilla
que quiere marcar, para esto utilizaremos las filas y las columnas de
la matriz que representa al tablero.
var boolean fin_juego = false;
var int turno = 0; //los jugadores son
0 y 1
var int casillas_vacias = 9;
var char tablero [3][3];//matriz de 3 x
3 que representa al tablero
var int fila_jugada;
var int columna_jugada;
var char ficha='0'; //será 'X' cuando
el turno sea 1
while(!fin_juego)
{
//se hace la jugada
fila_jugada = leer(); //lee de
consola la fila (de 0 a 2) que selecciona el jugador en ese turno
columna_jugada = leer(); //lee de
consola la columna (de 0 a 2) que selecciona el jugador en ese turno
if(turno == 0) ficha = '0'; //escoge
ficha
else ficha = 'X';
tablero[fila_jugada][columna_jugada]
= ficha;
casillas_vacias = casillas_vacias -
1; //al hacer la jugada disminuye en 1 las casillas vacías
//si se gana en este turno fin_juego
= true;
//si el tablero se llena sin ganador
fin_juego = true;
if(!fin_juego &&
casillas_vacias == 0) fin_juego = true;
turno = (turno + 1) % 2; //esto es
para cambiar el turno de 0 a 1 y de 1 a 0
}
Sobre el control de la jugada ganadora
Cuando se coloca la ficha se hace
control en vertical, horizontal y diagonales a ver si es una jugada
ganadora.
Para el control horizontal, todas las
fichas de la fila_jugada deben ser iguales, por tanto haremos una
validación iterando las columnas.
Para el control vertical, todas las
fichas de la columna_jugada deben ser iguales, por tanto haremos una
validación iterando las filas.
Para el control diagonal, no es
necesario realizarlo siempre, sólo cuando la jugada esté en alguna
diagonal. Y sólo si está en el medio del tablero la comprobación
debe ser de la doble diagonal.
Comprobar diagonal 1
fila_jugada: 0 y columna_jugada:0,
fila_jugada: 2 y columna_jugada:2
Comprobar diagonal 2
fila_jugada: 2 y columna_jugada:0,
fila_jugada: 0 y columna_jugada:2
Comprobar ambas diagonales.
fila_jugada: 1 y columna_jugada:1
Como esta lógica es un poco larga, la
encapsularemos en una función y la utilizaremos en cada
jugada para comprobar si la jugada es ganadora:
Entrada: ¿Qué necesito?
Tablero, fila_jugada, columna_jugada
Salida: ¿Qué quiero?
Booleano que indique si es una jugada
ganadora o no
Función: ¿Cómo lo hago?
Comprobando la Horizontal, Vertical y
cuando toque las diagonales.
Boolean esGanador(tablero, fila_jugada,
columna_jugada)
{
Boolean jugada_ganadora = false;
//validación horizontal
if(Tablero[fila_jugada][0] ==
Tablero[fila_jugada][1] &&
Tablero[fila_jugada][0] ==
Tablero[fila_jugada][2])
{
return true; //jugada ganadora en
la horizontal, termina la ejecución
}
//validación vertical
if(Tablero[0][columna_jugada] ==
Tablero[1][columna_jugada] &&
Tablero[0][columna_jugada] ==
Tablero[2][columna_jugada])
{
return true; //jugada ganadora en
la vertical, termina la ejecución
}
//verifica la diagonal 1 (sólo si es
necesario)
if( (fila_jugada == 0 &&
columna_jugada == 0) || (fila_jugada == 2 && columna_jugada
== 2))
{
if(Tablero[0][0] == Tablero[1][1] &&
Tablero[0][0] == Tablero[2][2])
{
return true; //jugada ganadora en
la diagonal 1, termina la ejecución
}
}
//verifica la diagonal 2 (sólo si es
necesario)
if( (fila_jugada == 0 &&
columna_jugada == 2) || (fila_jugada == 2 && columna_jugada
== 0))
{
if(Tablero[0][2] == Tablero[1][1] &&
Tablero[0][2] == Tablero[2][0])
{
return true; //jugada ganadora en
la diagonal 2, termina la ejecución
}
}
//verifica la doble diagonal(sólo si
es necesario)
if( fila_jugada == 1 &&
columna_jugada == 1)
{
if((Tablero[0][2] == Tablero[1][1] &&
Tablero[0][2] == Tablero[2][0])
||
(Tablero[0][0] == Tablero[1][1] &&
Tablero[0][0] == Tablero[2][2]))
{
return true; //jugada ganadora en
alguna de las diagonales, termina la ejecución
}
}
return jugada_ganadora; //sólo llega
a esta línea de código cuando no es jugada ganadora
}
Incorporamos la llamada a la función
en el programa principal
var boolean fin_juego = false;
var int turno = 0; //los jugadores son
0 y 1
var int casillas_vacias = 9;
var char tablero [3][3];//matriz de 3 x
3 que representa al tablero
var int fila_jugada;
var int columna_jugada;
var char ficha='0'; //será 'X' cuando
el turno sea 1
while(!fin_juego)
{
//se hace la jugada
fila_jugada = leer(); //lee de
consola la fila (de 0 a 2) que selecciona el jugador en ese turno
columna_jugada = leer(); //lee de
consola la columna (de 0 a 2) que selecciona el jugador en ese turno
if(turno == 0) ficha = '0'; //escoge
ficha
else ficha = 'X';
tablero[fila_jugada][columna_jugada]
= ficha;
casillas_vacias = casillas_vacias -
1; //al hacer la jugada disminuye en 1 las casillas vacías
//si se gana en este turno fin_juego
= true;
fin_juego = esGanador(tablero,
fila_jugada, columna_jugada);
//si el tablero se llena sin ganador
fin_juego = true;
if(!fin_juego &&
casillas_vacias == 0) fin_juego = true;
turno = (turno + 1) % 2; //esto es
para cambiar el turno de 0 a 1 y de 1 a 0
}
Con esto tendríamos lo básico para el
tres en raya, pero ¿qué pasaría si el jugador pusiera la ficha en
un lugar ocupado? ¿qué pasaría si inicialmente el tablero está
ocupado?¿No vendría bien agregar una impresión del tablero para
que jugador sepa en cada jugada cuáles son sus opciones de juego?
¿Cómo modificaríais el programa para
agregar estas funcionalidades?
Enlaces
domingo, 8 de marzo de 2015
Instancia de un objeto
A veces nos resulta complicado controlar que todos los atributos de todas las clases queden bien instanciados, para tener todo esto mejor controlado lo mejor es tener un diagrama de clases para saber qué clases deben instanciar a qué otras.
A continuación os mostraré lo que puede ocurrir si no tenemos bien controladas todas las instancias.
Tenemos una clase llamada Persona:
using System.IO;
using System;
public class Persona{
string nombre;
int edad;
char sexo;
public Persona()
{ nombre = "";
edad = 0;
sexo = ' ';
}
public Persona(string pNombre, int pEdad, char pSexo)
{ nombre = pNombre;
edad = pEdad;
sexo = pSexo;
}
public void imprimir()
{ Console.WriteLine("Persona-Nombre: "+nombre);
Console.WriteLine("Persona-Edad: "+edad);
Console.WriteLine("Persona-Sexo: "+ sexo);
}
}
Y tenemos una clase llamada Cliente que incluye a un objeto de tipo Persona, en este caso es Cliente el que debe instanciar al objeto de tipo Persona
using System.IO;
using System;
public class Cliente
{
int codigo;
Persona persona;
public Cliente()
{
codigo = 0;
persona = new Persona();//es en el constructor del cliente que instanciamos al objeto de tipo Persona
}
public void imprimir()
{
Console.WriteLine("Cliente-Codigo: "+codigo);
persona.imprimir();
}
}
Si ejecutamos este código:
using System.IO;
using System;
class Program
{
static void Main()
{
Cliente cliente = new Cliente();
cliente.imprimir();
}
}
El resultado de la ejecución es la siguiente:
Cliente-Codigo: 0
Persona-Nombre:
Persona-Edad: 0
Persona-Sexo:
Ahora os mostraré lo que pasaría en el caso que en el constructor de cliente NO se instancie el objeto persona, comentaremos la linea
public Cliente()
{
codigo = 0;
//persona = new Persona();//es en el constructor del cliente que instanciamos al objeto de tipo Persona
}
El compilador no nos avisará, porque no es un error sintáctico, pero el error vendrá en la ejecución:
Cliente-Codigo: 0
Unhandled Exception:
System.NullReferenceException: Object reference not set to an instance of an object
at Cliente.imprimir () [0x00000] in <filename unknown>:0
at Program.Main () [0x00000] in <filename unknown>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.NullReferenceException: Object reference not set to an instance of an object
at Cliente.imprimir () [0x00000] in <filename unknown>:0
at Program.Main () [0x00000] in <filename unknown>:0
Vemos que Cliente-codigo si que lo ha impreso correctamente, pero a partir de allí la impresión del objeto persona dio error por NULLReference, esto es porque no está instanciado el objeto.
Ahora que hemos visto la importancia de tener controladas las instancias os mostraré como instanciar con valores al objeto persona a partir de la clase Cliente.
Vimos que la clase Persona tiene el constructor:
public Persona(string pNombre, int pEdad, char pSexo)
{
nombre = pNombre;
edad = pEdad;
sexo = pSexo;
}
Agregamos ahora un nuevo constructor a la clase Cliente que utilice este constructor de la clase Persona:
public Cliente(int pCodigo, string pNombre, int pEdad, char pSexo)
{
codigo = pCodigo;
persona = new Persona(pNombre, pEdad, pSexo);
}
Y desde el Main le pasamos todos los valores utilizando este nuevo constructor de la clase Cliente:
static void Main()
{
Cliente cliente = new Cliente(1, "Juan", 30, 'H');
cliente.imprimir();
}
Y finalmente vemos la ejecución:
Cliente-Codigo: 1
Persona-Nombre: Juan
Persona-Edad: 30
Persona-Sexo: H
Suscribirse a:
Entradas (Atom)