JAVA - Sentencias Básicas (Condicionales, Aritmeticas y Contadores) - 2 de 3

4. Dado un número entero que se introduce por teclado, determinar si es negativo o superior a 100.

EXPLICACION DEL PROGRAMA: el programa en principio define la clase aa4 que contiene la función principal main. Primero se lee un numero, que es introducido por teclado y se hacen comparaciones para verificar si es negativo, mayor a 100 o en el intervalo 0-100. Finalmente se despliega por pantalla la condición de dicho numero.

//Programa realizado por Freddy Valda
import java.io.*;
public class aa4
{
public static void main(String args[])throws IOException
{BufferedReader in;
in=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Introduzca un numero");
int a=Integer.parseInt(in.readLine());
if(a<0)
System.out.println("El numero es negativo");
else
if (a>100)
System.out.println("El numero es mayor a 100");
else
System.out.println("El numero esta en el intervalo de 0 a 100");
}}

5. Dado un número que se introduce por teclado, si es positivo verificar si se encuentra en el intervalo abierto 60 – 90, de lo contrario emitir un mensaje de error.

EXPLICACION DEL PROGRAMA: Este programa verifica si un numero ingresado por el teclado es positivo y si se encuentra en un intervalo predeterminado utilizando sentencias if.

//Programa realizado por Freddy Valda
import java.io.*;
public class a5
{
public static void main(String args[])throws IOException
{BufferedReader in;
in=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Introduzca un numero");
int a=Integer.parseInt(in.readLine());
if(a<61)
System.out.println("ERROR");
else
if (a>89)
System.out.println("ERROR");
else
System.out.println("El numero esta en el intervalo abierto 60-90");
}
}

6. Una fuente de datos registra varias edades, la edad 0 indica el final del ingreso de datos, realice un programa para determinar el promedio de las edades ingresadas y además el porcentaje de personas mayores a los 50 años.

EXPLICACIÓN DEL PROGRAMA: Este programa nos permite registrar varias edades con la información que una ves ingresada la edad 0 esta nos indica el final del ingreso de edades, calculando le promedio de las edades y además el porcentaje de edades mayores a los 50 años.

// Programa realizado por Sergio W. Ossio Marin
import java.io.*;
public class B_1
{
public static void main (String args []) throws IOException
{
BufferedReader in;
in = new BufferedReader (new InputStreamReader (System.in));
double m = 1, aux = 0, n = 0, o = 0;
System.out.println ("La edad 0 indica el final de ingreso de edades");
while (m != 0)
{
System.out.print ("Ingrese una edad ");
m = Integer.parseInt (in.readLine ());
n++;
aux = aux + m;
if (m > 50)
{
o++;
}
}
double s = (o * 100) / (n - 1);
double aux2 = aux / (n - 1);
System.out.println ("El promedio es " + aux2 );
System.out.println ("El porcentaje de personas mayores a los 50 a*os es de: " + s );}}

Espero haber ayudado en algo. Hasta la próxima oportunidad!

Twittear

  

JAVA - Sentencias Básicas (Condicionales, Aritmeticas y Contadores) - 1 de 3

En los siguientes ejercicios, se utilizan las sentencias condicionales if- else, además de sentencias aritméticas como % (modulo), comparativas (<,>,==,etc) y tambien se hace uso de contadores y sentinelas.

1. Dado un número entero y positivo que se introduce por teclado, determinar si es par o impar.

EXPLICACION DEL PROGRAMA: Este programa lee un numero introducido por teclado y verifica si el numero es par o impar, verificando si el modulo del numero entre 2 es 0 o no.

//programa realizado por Freddy Valda Sanchez
import java.io.*;
public class a1
{
public static void main(String args[])throws IOException
{BufferedReader in;
in=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Introduzca un numero entero y positivo");
int a=Integer.parseInt(in.readLine());
if(a%2==0)
System.out.println("El numero es par");
else
System.out.println("El numero es impar");
}
}

2. Dado un número entero que se introduce por teclado, determinar si es positivo, negativo o nulo.

EXPLICACION DEL PROGRAMA: El usuario ingresa un numero entero y el programa determina si es positivo, negativo o cero(nulo). Utiliza simples comparaciones y sale el mensaje correspondiente.

//Programa realizado por Andrés Prudencio R.
import java.io.*;
public class a2
{
public static void main (String args[])throws IOException
{
BufferedReader in;
in = new BufferedReader (new InputStreamReader (System.in));
System.out.println("Ingrese un numero entero: ");
int d = Integer.parseInt(in.readLine());
if (d==0)
System.out.print(" el numero es nulo ");
else
{if (d<0)
System.out.print("El numero es negativo");
else
System.out.print("El numero es positivo");}
}}

3. Dado un número entero que se introduce por teclado, determinar si se encuentra en el intervalo cerrado 51 - 100.

EXPLICACIÓN DEL PROGRAMA: Este programa nos permite Verificar que un número ingresado por teclado se encuentre en el intervalo cerrado [51,100]

// Programa realizado por Sergio W. Ossio Marin
import java.io.*;
public class A_3
{
public static void main (String args[])throws IOException
{
BufferedReader in;
in = new BufferedReader (new InputStreamReader (System.in));
int n;
System.out.println("Ingrese el numero a verificar: ");
n = Integer.parseInt(in.readLine());
if(n>=51&n<=100)
System.out.println("El numero se encuentra en el intervalo cerrado [51-100]");
else
System.out.println("El numero no se encuentra en el intervalo cerrado [51-100]");
}}

Espero haber ayudado en algo. Hasta la próxima oportunidad!

Twittear

  

Algoritmos - 5 de 5

Regresar al índice

5.5.2 Algoritmos recursivos de prueba y error

Ejemplo 15. Método de Newton-Rapshon de manera recursiva

A continuación se va a rehacer el método de Newton-Raphson de manera recursiva. La manera en la que se plantea es haciendo llamadas sucesivas a la subrutina en la que se realizan las aproximaciones sucesivas pasando el nuevo valor de X que se quiere chequear.

Este valor irá estando cada vez más cerca de la solución f(x)=0 por lo que se añade una bifurcación al comiendo de la subrutina para chequear si se está suficientemente cerca de la solución. Esta bifurcación establece si debe realizarse una nueva llamada a la propia subrutina o bien si debe finalizar el programa.

Resulta imposible describir todos los algoritmos recursivos de prueba y error. De hecho, tampoco es la intención de este libro, sino que es más bien la de familiarizarse con la computación. Sin embargo un par de algoritmos van a ser descritos para desarrollar el conocimiento en esta disciplina. Un tipo de algoritmos dentro de los algoritmos recursivos de prueba y error son los algoritmos recursivos de búsqueda "hacia delante y hacia atrás". A continuación veremos el ejemplo del "viaje del caballo" y el "problema de las 8 reinas". Son dos jemplos situados en el entorno del juego del ajedrez.

Este juego ha sido objeto de estudio para buscar maneras de programar siguiendo el razonamiento que sigue la inteligencia humana ya que, la manera de pensar que se sigue en este juego es abordable siguiendo métodos mecanicistas. 

Ejemplo 16. El viaje del caballo

En ciertos casos se puede plantear un esquema recursivo de prueba y error donde las pruebas que realiza el ordenador construyen una serie caminos de búsqueda de soluciones. Estos caminos de búsqueda dan como resultado un árbol de subtareas, donde algunos caminos no llegan a la solución mientras que otros sí. En muchos problemas, este árbol crece muy rápidamente, normalmente de manera exponencial, con la subsiguiente carga computacional.

Vamos a introducirnos en la técnica descrita mediante el conocido ejemplo del "viaje del caballo". Dado un tablero de ajedrez de NxN casillas, un caballo situado en una determinada casilla debe recorrer todo el tablero -de acuerdo a los movimientos permitidos según el juego del ajedrez- visitando todas las casillas sin situarse dos veces en ninguna de ellas. De forma que el problema consiste en encontrar un camino, si es que existe alguno, que recorra todo el tablero siguiendo la ruta mas corta, y por lo tanto realizando N2-1 movimientos, siguiendo los movimientos del caballo de ajedrez.

Considerando que el caballo puede realizar 8 movimientos posibles, la manera lógica para resolver este problema es la de construir el camino mediante una sucesión de búsquedas parciales, siendo ésta la búsqueda parcial de una nueva casilla que puede ser visitada. En el caso de encontrarse una nueva casilla, se procede a buscar la siguiente (se avanza hacia delante) y, en caso de no encontrase, se vuelve a la casilla de la que se había partido (se avanza hacia atrás), para probar una nueva casilla que pueda ser visitada distinta a la que se acababa de probar.

De manera que el procedimiento consistirá en inicializar las variables necesarias y proceder a dar el primer paso. La resolución del problema la realizaremos para un tablero con un número cualquiera de casillas y comenzando en una fila (f) y columna (c) cualquiera.

Siendo Casillas, el número de casillas del tablero, las variables que se inicializan son:

Tablero: es una matriz llena de ceros con un número de celdas igual a CasillasxCasillas. Según vaya el caballo pasando por cada celda se llenará la celda en cuestión con el número que indica en qué paso ha accedido el caballo a ella.

a: es un vector de ocho elementos con los desplazamientos permitidos en las filas del tablero para un caballo de ajedrez.

b: es un vector de ocho elementos con los desplazamientos permitidos en las columnas del tablero para un caballo de ajedrez. Los vectores a y b están coordinados entre sí, de manera que a(1) y b(1) representan el desplazamiento en la fila y la columna para el primero de los movimientos y así sucesivamente.

N: se corresponde con el número de movimientos realizados por el caballo. Será una variable auxiliar para determinar si con el movimiento que se acaba de realizar se ha llegado a alguna solución, ya que cuando N adquiera el valor de CasillasxCasillas significará que el caballo a pasado por todas las casillas.

La inicialización se realizará en la función principal, a la que llamaremos El_viaje_del_Caballo(f,c,Casillas). Las variables que se pasan por ventanilla son la fila de la que parte el caballo, f, la columna, c, y el número de filas o columnas que tiene el tablero, Casillas. Después de la inicialización se procede a dar el primer paso. Para ello se utilizará la función nuevo_paso(Tablero,f,c,a,b,N).

La función nuevo_paso será una función recursiva en la que se irá probando cada uno de los 8 movimientos que puede dar el caballo. Para determinar cuál de los ocho movimientos se está probando utilizaremos una variable auxiliar a la que llamaremos movimiento.

En primer lugar, la función nuevo_paso probará a dar el primero de los 8 movimientos. Si es correcto lo guarda y vuelve a llamarse a sí misma volviendo a repetir el proceso, con lo que se da un paso adelante. Si el movimiento probado no es correcto (esto es, se sale del tablero o accede a una casilla por donde ya ha pasado) pasa a probar el siguiente movimiento. Cuando ha probado los 8 movimientos, la función termina y con ella termina también ese camino de búsqueda, con lo que se da un paso hacia atrás.

El diagrama de flujo con el algoritmo descrito anteriormente es el siguiente:

La variable N es una variable que contabiliza el número de movimientos realizados. 

No aparece en el diagrama de flujo, pero si en el código del programa. Gracias a esta variable, se soluciona la casuística que aparece cuando se ha cumplido el objetivo de recorrer todas las casillas del tablero y, en consecuencia, no es posible realizar ningún movimiento más. Se puede identificar que el programa ha llegado a este momento porque el valor de N coincide con size(Tablero,1)^2. Ahora lo que se hace es sacar por pantalla el tablero con los pasos realizados (Tablero(f1,c1)=N -observe que no se ha puesto ’;’ al final de la instrucción).

Es interesante el recurso empleado para poder utilizar los vectores con los movimientos a y b. Al ser dos vectores con los valores constantes, se ha definido como variables globales tanto en la función de inicialización (backtraking) como en la de búsqueda (nuevo_paso). Con esto se evita tener que pasar los valores de a y b por ventanilla en cada una de las llamadas, con lo que la velocidad del proceso mejora.

A continuación se presenta la primera de las múltiples soluciones que se obtienen cuando se le pide al programa que determine el camino a seguir para un tablero de 8x8 situando al caballo inicialmente en la casilla 1,1.

Puede observarse (con un poco de paciencia) como los movimientos realizados tienen una correspondencia con el orden en el que se han definido los 8 movimientos en los vecotres a y b.

Ejemplo 17. El problema de los emparejamientos estables

Imaginemos dos grupos de personas A y B con un mismo número de componentes N. 

Se trata de encontrar el conjunto de N parejas a,b siendo a del grupo A y b del grupo B, que satisfagan ciertas restricciones. Se pueden utilizar muchos criterios para establecer estos emparejamientos. Uno de ellos es conocido como la "regla de los emparejamientos estables", el cual se explica a continuación:

Supongamos que A es un conjunto de motoristas y B un conjunto de cámaras de televisión. El objetivo es tratar de emparejar a los motoristas con los cámaras de televisión para cubrir la retrasmisión de una carrera ciclista. Cada motorista y cada cámara tienen distintas preferencias a la hora de elegir una pareja del otro grupo. Si las N parejas se establecen de forma que existe un motorista y un cámara de televisión que se prefieren mutuamente frente a la pareja que les ha tocado respectivamente, entonces el emparejamiento resulta inestable. Si, por el contrario, este tipo de sinergias no existen, se dice entonces que el emparejamiento es estable. Esta situación caracteriza muchos problemas que se presentan cuando hay que realizar emparejamientos de acuerdo a ciertas preferencias.

Supongamos que acaban de nombrar a un nuevo jefe para cubrir la actualidad deportiva en ese canal de televisión. Este jefe quiere que todas las personas que están a su cargo estén lo más contestas posible. Va a intentar que todas las órdenes que se den estén consensuadas por todos los afectados. Se va a cubrir la retransmisión de una maratón con 8 parejas de motoristas y de cámaras. Para establecer los emparejamientos se ha decidido que cada motorista pase el orden de preferencia que tiene sobre los cámaras y que cada cámara pase el orden de preferencia que tiene sobre los motoristas. 

Con ello se ha elaborado la siguiente lista con la que hay que establecer los emparejamientos:

De forma que el motorista 1 prefiere estar en primer lugar con el cámara 7, en segundo lugar con el cámara 2 y así sucesivamente.

Un camino para dar con la solución es probar todos los pares de miembros de los dos grupos, uno detrás de otro, localizando las soluciones. Se establece, en este caso, una búsqueda de prueba y error hacia delante y hacia atrás sobre las distintas pruebas que se van haciendo. Este es el método seguido en el caso del problema de las 8 reinas, presentado en el libro "Aprenda a programar...". Llamando Prueba a la función para buscar la pareja al motorista M según el orden establecido mediante su ranking R, podemos escribir el siguiente diagrama de flujo que es completamente coincidente al del problema de las 8 reinas, salvando las pequeñas diferencias debidas a la casuística:

En el diagrama de flujo propuesto, se busca a un cámara que pueda ser pareja de un motorista. De manera que comenzamos buscando pareja al motorista 1, luego al motorista 2 y así sucesivamente; sin embargo observe que podría realizarse al revés, buscando primero pareja al cámara 1, luego al 2 etc.

Dentro de la Figura 5.9, la pregunta ¿Es válido? tiene dos partes. Para que la respuesta sea sí, hay que comprobar en primer lugar que el cámara no haya sido ya asignado. Y en segundo lugar hay que comprobar que el emparejamiento es estable.

Para ello hay que decidir cómo agrupar la información. En primer lugar vamos a guardar los datos iniciales que aparecen en la Tabla 5.1 en dos matrices:

MR: Matriz de 8x8 con el ranking establecido por los motoristas.

CR: Matriz de 8x8 con el ranking establecido por los cámaras.

Por ejemplo, MR(3,2) se corresponde con el cámara preferido en segundo lugar por el motorista 3, que es el cámara 2, según la Tabla 5.1.

Vamos a guardar el resultado de la búsqueda en un vector llamado X de 8 elementos en el que se indiquen ordenadamente el cámara elegido por el motorista de cada casilla. Así por ejemplo, X(3) se correspondería con el cámara asignado al motorista 3.

Además, va a ser conveniente establecer un segundo vector Y de otros 8 elementos donde guardaremos ordenadamente a los motoristas asignados a los distintos cámaras. Lógicamente, no es necesario crear Y, ya que es en realidad una información redundante. En realidad se puede crear Y a partir de X, y viceversa, según la relación:

Sin embargo, el disponer de Y va a mejorar sensiblemente la eficiencia del algoritmo.

Con esto, el diagrama de flujo de la Figura 5.9 puede ser reescrito de la siguiente manera:

Una parte fundamental en el diagrama de la Figura 5.10 es determinar si es estable la nueva pareja M-C establecida. Desgraciadamente no es posible establecer si es estable la pareja con una simple comprobación como en el caso del problema de las 8 reinas. Lo primero que tenemos que tener en cuenta es que la estabilidad o no de una pareja se determina según el ranking establecido en las matrices MR y CR. Sin embargo, éste ranking no está expresado de manera explícita en estas dos matrices. Lo interesante sería disponer de matrices en las que sí estuviera explicito de manera que se pudiera acceder directamente al ranking que tiene el motorista M sobre el cámara C y viceversa.

Para ello vamos a establecer dos matrices auxiliares que son función directa de MR y CR. Estas matrices son RMC y RCM. La primera matriz (RMC) contiene el ranking establecido por los motoristas sobre los cámaras. De manera que RMC(3,1) es el ranking que ocupa el cámara 1 según el orden de preferencia del motorista 3 (que es 4, según el ejemplo propuesto en la Tabla 5.1). Así mismo la segunda matriz, RCM, contiene el ranking establecido por los cámaras sobre los motoristas. Con estas dos matrices auxiliares se facilita muchísimo la determinación de la estabilidad o no de una nueva pareja.

El proceso para saber si es o no estable un emparejamiento se construye directamente aplicando la definición de la estabilidad. Un emparejamiento <M,C> no es estable por dos posibilidades:

1º Existe un cámara, distinto a C, que prefiere a M, frente al motorista que le han asignado y, a su vez, M le prefiere a él frente a C.
2º Existe un motorista distinto a M, que prefiere a C, frente al cámara que le han asignado y, a su vez, C le prefiere a él frente a M.

Lo que ahora toca es realizar una función cuyo encabezado sea:

function [XM,YM]=EmparejamientoEstable(MR,CR)

Donde MR y CR son las matrices anteriormente descritas que contienen el ranking, XM es una matriz cuyas filas se corresponden con cada una de las soluciones estables con los emparejamientos que se hacen a los motoristas e YM es el homólogo a XM pero con los cámaras.

Está función realizará la inicialización del proceso recursivo de prueba y error y lanzará la búsqueda de la pareja para el primer motorista. Según lo que se ha comentado, en la inicialización del proceso debe:

1º Inicializar los vectores X e Y
2º Crear las matrices RMC y RCM.
3º Lanzar la función Prueba para el motorista 1.

Por otra parte hay que, lógicamente, programar la función Prueba, cuyo encabezado será:

function Prueba(M,X,Y)

Siendo M el motorista al que se le busca pareja, X son los cámaras asignados a los motoristas e Y son los motoristas asignados a las cámaras.

Por último será necesario programar una tercera función que devuelva si un emparejamiento es o no estable. El encabezado será:

function E=Estable(M,C,X,Y)

Donde X, Y y M coinciden con los valores de entrada de la función Prueba. C es el cámara que se prueba a emparejar con el motorista M y E es 1 si el emparejamiento es estable y 0 si no lo es.

El resto de datos que necesitan las funciones (MR, CR, RMC o RCM), como no van a variar una vez definidos, deben guardarse como variables globales, tal y como se hace con los vectores que contienen los movimientos en el "viaje del caballo". Hay que observar que en el caso de la función de inicialización - EmparejamientoEstable(MR,CR)- no pueden definirse como variables globales MR y CR, ya que son los propios valores de entrada a la función, así que deberá utilizar otro nombre alternativo para estas dos matrices.

También se deben definir como variables globales las dos matrices de retorno XM e YM, para añadir una nueva fila cada vez que se encuentre alguna solución.

Espero haber ayudado en algo. Hasta la próxima oportunidad!

Regresar al índice

Twittear

  

Algoritmos - 4 de 5

Regresar al índice

5.5 Algoritmos de prueba y error

Un área de la programación particularmente intrigante es la referente a la resolución general de problemas. Esta tarea consiste en dar con algoritmos para encontrar soluciones a problemas específicos sin seguir una regla fija para la computación, sino mediante "prueba y error". La manera más común para ello es descomponer el proceso de "prueba y error" en subtareas. A menudo, estas subtareas se expresan de manera natural en forma recursiva probando un número finito de veces las propias subtareas hasta dar con la solución al problema. En este caso se estaría planteando un esquema recursivo de prueba y error.

Otras veces, la manera de establecer el esquema para encontrar la solución no se plantea de manera recursiva, sino que se establece una condición que, mientras ésta se cumpla, el programa sigue actuando hasta dar con la solución mediante la repetición sistemática de una serie de pasos. En este caso se estaría planteando un esquema iterativo de prueba y error.

5.5.1 Algoritmos iterativos de prueba y error

Ejemplo 13. Método de Newton Rapshon de manera iterativa

El método de Newton-Raphson o simplemente el método de Newton, es uno de los métodos numéricos más poderosos para resolver el problema de búsqueda de raíces de una función matemática expresada en la forma f(x)=0. La base del método reside en el concepto de derivada de una función.

Esta figura muestra como se obtienen las raíces de una función f(x) mediante tangentes sucesivas. Comenzando con una aproximación inicial x₀, la aproximación x₁ es la intersección con el eje x de la línea tangente a la gráfica de f(x) en (x₀,f(x₀)). La aproximación x₂ es la intersección con el eje x de la línea tangente a la gráfica de f(x) en (x₁,f(x₁)) y así sucesivamente.

Observa que:

De manera que para un valor x_i se determina un nuevo valor x_i+1 más próximo a f(x)=0.

De lo que se trata ahora es de hacer una función que ejecute iterativamente la operación señalada en la ecuación (5.8). Con esto nunca llegaremos a la solución f(x)=0, pero nos iremos aproximando sucesivamente, de manera que, después de realizar un número suficiente de iteraciones, habremos conseguido un valor de x muy próximo a la raíz. Generalmente no se programa un número concreto de iteraciones, sino que se establece un criterio para decidir cuando debe detenerse el proceso iterativo.

Como el objetivo es buscar un valor de x en el que f(x)=0, lo que se establece es que el proceso iterativo continúe mientras que f(x) supere un valor próximo a cero. 

Para el ejemplo concreto realizaremos un programa para determinar las raíces de la siguiente función:

Para ello realizaremos una función de Matlab cuyo encabezado sea: 

function raiz=Newton_Raphson(xo,error)

Donde los argumentos de entrada son:

xo: punto de inicio del método.

error: se utilizará para determinar la condición de parada del algoritmo.

Es la diferencia entre el valor de f(xi) y 0 y cuando se cumpla que |f(xi)|<|error| se para el método iterativo.

Los argumentos de salida son:

raiz: es el valor que tiene xi en el momento en el que se decide parar el algoritmo.

La función Newton_Raphson deberá realizar la iteración:

Para calcular la derivada utilizaremos una constante de derivación de 1e-10.

Además le agregaremos al programa un contador que indique cuántas iteraciones ha efectuado antes de pararse. En concreto dibujará unos 20 puntos de la función a lo largo del intervalor [raiz-1,raiz+1], siendo raiz el valor de retorno de la función. Incluiremos la función grid para dibujar un mayado a la gráfica.

El diagrama de flujo y el programa son los siguientes:

Ejemplo 14. Cálculo de las dimensiones óptimas de un cilindro.

Supongamos el caso de un jeque árabe que pide que se realice un programa para determinar las dimensiones que debe tener un barril de petróleo para que, albergando un determinado volumen, presente el mínimo área. El problema es que el jeque en cuestión quiere exportar el petróleo en bidones de distinto volumen, por lo que necesita un programa que sea capaz de dimensionar el barril en función del volumen solicitado. 

Para solucionar esto vamos a realizar un algoritmo de prueba y error en el que estableceremos un proceso iterativo con el que nos acercaremos sucesivamente a la solución óptima. El algoritmo seguirá los siguientes tres pasos: 

1º Se determina la altura h que debe tener un barril inicial que tenga un radio muy pequeño (por ejemplo r=0.001) para albergar el volumen Vc solicitado. Esta altura se encontrará lejos de la altura que de unas proporciones óptimas y sabemos que habrá que reducirla para dar con la geometría del barril óptimo.

2º Calcularemos el área que presenta este barril inicial.

3º Esta área inicial será muy grande. De lo que se tratará ahora es de implementar un sistema iterativo en el que se vaya incrementando el radio con un paso pequeño (por ejemplo paso=0.01) hasta dar con las dimensiones del barril (r y h) que presentan el mínimo área. El criterio para detener las iteraciones es que se lleguemos a aquella iteración en la que demos con un área lateral superior al área lateral que se había obtenido en el paso anterior.

Esto es, después del 2º paso se dispondrá de un primer área (llamémosle Area). 

Ya dentro del proceso iterativo, al incrementar el radio, se podrá calcular un nuevo área para ese radio (llamémosle Area_nueva) que podrá compararse con el anterior área. Si resulta que se ha reducido el área, el proceso iterativo debe continuar. Si, por el contrario, el área nueva es peor, debe detenerse el proceso. 

Vamos a programarlo en una función de Matlab cuyo encabezado sea:

function [r,h]=Area_optima(Vc)

Donde Vc es el volumen que debe albergar el barril y r y h son el radio y la altura -calculados por la función- que minimizan el área del barril de volumen Vc.

Las fórmulas que hay que considerar son:

Área de la circunferencia: πr²

Área de un cilindro: 2πr² +2πrh

Volumen de un cilindro: πr²h

El diagrama de flujo para el 3^er paso es el siguiente:

Espero haber ayudado en algo. Hasta la próxima oportunidad!

Regresar al índice

Twittear

  

Algoritmos - 3 de 5

Regresar al índice

5.4 Algoritmos recursivos

Se dice que un objeto es recursivo cuando el propio objeto está compuesto parcialmente por sí mismo. Los sistemas recursivos tienen una importancia particular para realizar ciertas definiciones matemáticas. Un ejemplo lo encontramos en la definición del factorial de un número. La función factorial para los números naturales puede ser expresada de la manera siguiente:

Esta es la expresión recursiva del factorial de un número, frente a la iterativa, expresada en la ecuación (5.2)

Los sistemas recursivos no se encuentran sólo en imaginario mundo de las matemáticas, sino que también en la más prosaica realidad, como puede verse al enfrentar dos espejos o al mirar una coliflor o un helecho. Poder establecer una expresión recursiva implica poder definir una serie infinita de objetos mediante la inicialización de un número finito de objetos. Desde el punto de vista informático esto abre posibilidades que dan vértigo, ya que se pueden describir un número infinito de operaciones mediante un programa finito, aunque, al contrario que los programas que contienen bucles, no presente repeticiones de código explícitas. Los algoritmos recursivos, sin embargo, son particularmente adecuados cuando el problema a resolver, o la función matemática a computar o la estructura de datos a ser procesada está definido en términos recursivos. En general un programa recursivo P es función (Π) de una serie de instrucciones Si distintos de P y de P mismo:

La herramienta necesaria y suficiente para poder expresar programas de manera recursiva en un determinado lenguaje de programación es que el lenguaje de programación admita funciones, procedimientos o subrutinas (como prefiera llamarse). 

Cuando una función contiene una llamada explícita a sí misma, se dice entonces que hay una recursividad directa. Cuando, por el contrario, una función no realiza una llamada directa a sí misma, sino que lo hace a través de otra función, se dice que tiene una recursividad indirecta.

Ejemplo 10. Obtención del factorial de un número N recursivamente

Anteriormente se determinó el factorial de un número N de manera iterativa según la fórmula:

Y acabamos de ver cómo también puede expresarse de manera recursiva según esta otra forma:

La cual define el factorial de un número como el producto de ese número con el factorial del número anterior; salvo el factorial de 0, que es 1 por definición. El diagrama de flujo del algoritmo para calcular el factorial de un número de manera recursiva es el siguiente:

Hay que observar que en el diagrama de flujo no hay un retroceso en la línea del programa, sino que lo que aparece es una nueva llamada al propio programa (Factorial) cada vez que se trata de calcular el factorial de un número superior a 0. A su vez, esta llamada pide calcular el factorial del número anterior al que se encuentra en cada momento, por lo que llegará un momento en el que se tratará de calcular el factorial de 0. En este momento, debido a la bifurcación que hay, se determina el primer resultado, que es 1, y finaliza el programa en el que se está calculando el factorial de 0. Al finalizar este programa se continúa con el cálculo del factorial de 1, donde se establece el segundo resultado (1*1) y finaliza este segundo programa. A su vez vuelve a continuar el programa superior, que se corresponde con el cálculo del factorial de 2, y así continúa la ascensión sucesivamente hasta llegar a determinar el valor del factorial del número que se ha solicitado.

Ejemplo 11. Determinar recursivamente si un número N es o no primo 

Recordamos que un número entero N es primo si es mayor o igual a dos y sus únicos factores son el 1 y el propio número. En el Ejemplo 6 y en el Ejemplo 7 se estableció un método iterativo para determinar si un número cumple esta condición. Este método consiste en dividir al número entre todos los números naturales que hay entre el 2 y la raíz cuadrada del número a estudiar, observando si en algún caso la división era exacta.

De lo que ahora se trata es de seguir el mismo razonamiento anterior de manera recursiva. Para ello se va a plantear el diagrama de flujo en dos partes: la inicialización y el cálculo recursivo.

En la inicialización el usuario pasa el número que quiere saber si es primo, el cual queda guardado en la variable N. A continuación se guarda la raíz cuadrada de N en una variable global -K- y por último se inicializa el proceso recursivo en el que se chequea si es divisible N entre algún número natural comprendido entre el 2 y K. Para ello se utiliza una función auxiliar que llamaremos Mirar_si_es_divisible(N,k), la cual se utiliza en la inicialización para k=2. (Nótese que se está diferenciando entre K mayúscula y k minúscula).

Esta función auxiliar contendrá los pasos que hay que dar para determinar si N es divisible entre k. En caso de que no lo sea, realizará otra llamada recursiva a si misma para chequear si N es divisible entre k+1, hasta que suceda que, o bien k es superior a K -en cuyo caso N es primo- o bien N sea divisible por k -en cuyo caso N no es primo. 

El diagrama de flujo queda de la siguiente manera:

Ejemplo 12. El triángulo de Sierpinski

El triángulo de Sierpinski entra en el ámbito de los fractales. Fractal procede del adjetivo latino ’fractus’, que significa "interrumpido" o "irregular". 

La geometría del fractal fue utilizada por Benoît Mandelbrot en 1975 para describir ciertas formas complejas de la naturaleza como nubes, sistemas montañosos, galaxias, flores, ramificaciones arbóreas y bronquiales, rocas, cuencas hidrográficas, el sistema neuronal, las líneas costeras, esponjas,... y objetos matemáticos como el conjunto de Cantor o el triángulo de Sierpinski, cuyo comportamiento caía fuera del marco de la matemática tradicional.

El triángulo de Sierpinski es una construcción geométrica realizada mediante una sucesión de triángulos. La base del método está en que un triángulo puede dividirse en tres triángulos exactamente iguales. A su vez, cada uno de estos tres triángulos puede dividirse en otros tres triángulos exactamente iguales y así sucesivamente. De manera que el triángulo de Sierpinski es un triángulo formado a partir de una sucesión sucesiva de sucesivos triángulos que se suceden sucesivamente, formándose a partir de triángulos pequeños otros triángulos cada vez más grandes.

La manera adecuada para realizar esta construcción geométrica es mediante un sistema de dibujo recursivo. En la parte inicial del proceso se indica el orden del triángulo de Sierpinski, donde el orden es el número de subdivisiones triangulares con las que se divide el triángulo mayor. Posteriormente se procede a dibujar los triángulos según el orden indicado.

Para dibujar los triángulos se va a establecer una subrutina propia con la que se dibujará un triángulo mediante tres variables (X,Y,h). La variables X, Y se corresponden con la posición del vértice superior del triángulo y h se corresponde con la altura o la base del triángulo, como puede verse en la Figura 5.3. Obsérvese que en la Figura 5.3, las proporciones no se mantienen, ya que aunque está dibujado como un triángulo equilátero, es un isósceles. La subrutina para dibujarlo recibirá el nombre de Dibujar_triangulo(x,y,h).

La inicialización la realizaremos dentro de una rutina principal a la que llamaremos Triangulo_Sierpinski(N), donde N es el orden del triángulo. En esta rutina se inicializarán las coordenadas X, Y del primero de los triángulos que va a ser dibujado. Por real decreto vamos a hacer que el punto de origen esté en la posición (0,0) -punto A0 de la Figura 5.4-. Siguiendo el mismo criterio, se asigna una longitud inicial a h de una unidad. Por último esta rutina iniciará una subrutina a la que llamaremos triangulo(N,x,y,h). Esta subrutina es quien contendrá las instrucciones para ir dibujando los triángulos recursivamente.

Básicamente la subrutina triangulo(N,X,Y,h) se va a limitar a localizar el lugar en el que ha de ser dibujado cada uno de los triángulos, así como de determinar el tamaño que tendrán los triángulos. Como se ha dicho en la introducción al ejemplo, cada triángulo se compone de otros tres triángulos más pequeños. En concreto, un triángulo de altura h se compone de otros tres triángulos de altura h/2, como puede verse en la Figura 5.5. De forma que el triángulo que tiene su vértice superior en la posición Ai tiene una altura h y está formado por tres triángulos de altura h/2 que tienen su vértice superior en las posiciones A_i+1, B_i+1 y C_i+1. Con este esquema queda planteado el sistema recursivo ya que cada vez que se ejecuta la subrutina triangulo(N,X,Y,h), esta se llama a si misma 3 veces - triangulo(N-1,X,Y,h)- para elaborar un triángulo de orden menor, modificando las posiciones X, Y según el lugar donde debe encontrarse el vértice superior de cada triángulo y reduciendo h a la mitad.

Cuando el orden del triángulo a dibujar es 0, detienen las llamadas recursivas. En ese momento se procede a dibujar el triangulo y finaliza el hilo de esa subrutina. La evolución del dibujo de un triángulo de Sierpinski de orden 3 según el esquema planteado es la siguiente:

Asimismo, el diagrama de flujo para dibujar el triángulo de Sierpinski de la manera que acaba de ser planteada es el siguiente:

Espero haber ayudado en algo. Hasta la próxima oportunidad!

Regresar al índice

Twittear

  

Algoritmos - 2 de 5

Regresar al índice

5.3 Algoritmos iterativos

Un componente básico de los algoritmos es la iteración. Esta palabra implica repetición, ya que iterar significa ejecutar repetidamente algunos pasos elementales de un algoritmo acercándose, paso a paso, a la solución. Para realizar un programa de ordenador es muy conveniente localizar los pasos que se repiten y anidarlos dentro de un sistema iterativo.

En el ejemplo anterior en el que se determinaba si el número 5 era o no primo, se ha seguido un método que funciona para el caso concreto del número 5. Si se quisiera desarrollar un programa más genérico (por ejemplo, un programa que determinara si un número N es o no primo) haría falta identificar la parte repetitiva del algoritmo y anidarla dentro de un proceso iteración en el algoritmo. 

Ejemplo 6. Determinar iterativamente si un número N es o no primo

Vamos a rehacer el algoritmo para calcular si el número 5 es primo de manera que sea un algoritmo válido para un número genérico N. En el diagrama de flujo del ejemplo para el número 5 se observan tres repeticiones:

Se divide el número N entre un número natural.
Se observa si la división es entera.
Se incremento del número natural que va a dividir al número N.

En el caso que estamos tratando hemos localizado tres pasos que se repiten, los cuales se realizan desde el número 2 hasta el número 4 en el ejemplo concreto del número 5. De lo que se trata es de anidar estos tres pasos dentro de un bucle que se ejecute mientras que se cumpla una cierta condición; siendo la condición que el número natural que divide a N sea inferior a N. Vamos a llamar al número que divide i, al resultado de la división D y al número a chequear N. El diagrama de flujo resultante es el siguiente:

En el diagrama de flujo hay tres instrucciones que se repiten iterativamente (la tres que se han descrito anteriormente) y aparece una condición de chequeo para saber si debe detenerse el algoritmo o no (si i ha llegado a obtener el valor de N). La manera elegida para programar el bucle ha sido la de anidarlo dentro de un bucle WHILE con la condición de chequeo en TRUE (while 1). Este bucle resultaría ser un bucle infinito (ya que la condición de chequeo siempre se cumple) si no fuera porque dentro del bucle se han anidado dos bifurcaciones IF que contienen una ruptura del bucle (BREAK). Esta ruptura se produce cuando la condición de alguna de las dos bifurcaciones se cumple, las cuales son:

1ª Si se encuentra una división exacta (N no es primo).

2ª Si resulta que el divisor a probar (i) ha llegado a ser igual a N (N es primo).

Ejemplo 7. Mejora del algoritmo para calcular si un número N es primo 

A continuación se van a presentar dos mejoras del anterior proceso iterativo desde el punto de vista de la computación. Como ya sabemos, para determinar si, por ejemplo, el número 231 es primo, hay que dividirlo entre todos los números naturales entre el 2 y el 230. Pero también es cierto que todos aquellos números naturales superiores al √231 no dividen de forma entera al 231, por lo que la condición de chequeo puede modificarse por comprobar que la variable i no rebase el valor de √231 . Con esto se consigue que, en el caso del número 231, en lugar de repetir el proceso iterativo 229 veces (desde i=2 hasta i=230), se repita solo 14 veces (desde i=2 hasta i=15), ya que por encima del 15 es seguro que no existe ningún número que divida al 231 de manera entera, con lo que se reduce la carga computacional del algoritmo.

Otra mejora sobre el algoritmo anterior consiste en evitar que en cada paso del bucle iterativo se calcule la raíz cuadrada de N, ya que calcular la raíz cuadrada de un número es muy costoso para un ordenador. Para ello basta con calcular una vez la raíz de N, almacenarla en una variable (llamémosle K) y utilizar esta variable en la condición de chequeo, como puede verse en el diagrama de flujo siguiente.

Si se prueba a cronometrar los dos últimos programas presentados (PrimoII y PrimoIII) puede observarse que PrimoIII es mucho más rápido que PrimoII. ¿Cómo cronometrar un programa? Generalmente se utiliza el propio reloj del ordenador para medir el tiempo. Además, cuando son programas cuyo tiempo de ejecución es muy corto, se le suele pedir al ordenador que los ejecute varias veces (por ejemplo 1000) y se establece una media del tiempo que ha tardado, ya que medir lo que tarda el programa una sola vez es muy impreciso.

Ejemplo 8. Obtención del factorial de un número N iterativamente

Un ejemplo claro de un proceso iterativo es el cálculo del factorial de un número N. La regla del factorial de un número expresada matemáticamente es:

De forma que para calcular el factorial del número 5 se siguen los siguientes pasos:

Se multiplica a 2 por 3 y se almacena el resultado.
Se multiplica el resultado anterior por 4 y se almacena de nuevo.
Se multiplica el resultado anterior por 5 y se almacena de nuevo.

Este último resultado es el factorial de 5. Si observamos el proceso se ve necesario utilizar una variable que varíe su valor de uno en uno desde el 2 hasta el 5 (llamémosle a esta variable i) Asimismo se necesita otra variable para almacenar el resultado de la multiplicación (llamémosle a esta variable Resultado).

Los pasos que se repiten son 3:

1º Multiplicación de Resultado por la variable i.
2º Almacenamiento de la operación anterior.
3º Incremento de la variable i en una unidad.

En realidad los pasos 1º y 2º se pueden hacer en una sola operación "informática" (multiplicar Resultado por i) y asignar el resultado de la multiplicación a Resultado).

Por último faltaría la condición de chequeo para continuar o para detener los tres pasos durante el proceso iterativo. La condición de chequeo en este caso es comprobar que la variable i no supera el valor del número del que se calcula el factorial N.

Ejemplo 9. Descomposición factorial de un número N.

Obtener la descomposición factorial de un número natural N consiste en determinar todos aquellos números naturales de menor valor que multiplicados entre si dan como resultado el número N. Para ello hay que probar a dividir el número N entre todos los números naturales que hay entre 2 y N . A continuación se describen los pasos que se repetirán en el proceso iterativo:

Siendo I el número con el que se prueba a dividir N en un momento dado, hay que chequear que el valor de I no supere el valor de √N :

Si lo supera, se termina el proceso iterativo.
Si no lo supera, se comprueba si N es divisible de manera entera entre I:

Si N no es divisible entre I hay que pasar al siguiente número (el I+1).
Si N es divisible entre I hay que:

Almacenar a I como factor del número N
Actualizar el valor de N como N=N/I

Los factores se van a guardar en un vector que llamaremos factores. Para guardar ordenadamente los factores nos valdremos de una variable auxiliar que llamaremos f.

Inicialmente esta variable f valdrá 1 y, cada vez que aparezca un nuevo factor de N, se incrementará en una unidad el valor de f. De esta manera, sirviéndonos de la variable auxiliar f, podremos guardar el primer factor en la primera celda del vector factores, el segundo factor en la segunda celda y así sucesivamente.

Espero haber ayudado en algo. Hasta la próxima oportunidad!

Regresar al índice

Twittear