Algoritmo: Obtener longitud del mayor subarreglo creciente de un arreglo

A falta de tiempo para cosas más profesionales, voy a ir poniendo los algoritmos bonitos que desarrolle en la Universidad. En este caso, la especificación del ejercicio sería: Dado un arreglo de números, determinar la longitud del subarreglo creciente más largo del arreglo.

Ejemplo

Si recibiéramos un arreglo de naturales con los siguientes elementos: 2, 6, 5, 1, 3, 4, 9, 8 el resultado sería 4, puesto que es el subarreglo más largo de elementos crecientes (es decir, la longitud del subarreglo 1, 3, 4, 9)

Solución en palabras

El algoritmo que resuelve este problema debería recorrer el arreglo e ir verificando si el elemento en la posición a la que apunta es menor al de la siguiente posición. Esto supone además que, puesto que evaluaremos el elemento de la siguiente posición, debemos recorrer el arreglo desde la posición 0 hasta n-1 (siendo n la longitud del arreglo), ya que no queremos sobrepasar la longitud del mismo. Por otro lado, para cada elemento del arreglo contaremos sus sucesores que sean mayores que él mismo y con dicho conteo podremos determinar cual es la longitud de los subarreglos crecientes.

Solución en Java

El algoritmo en Java sería este:

public class SubarregloCreciente{
	public static void main(String args[]){
		//arreglo a evaluar
		int[] arr = {5,6,4,1,2,6,7,78,6,2,3,4,5,6,7,3,6,1};
		//la longitud al menos sera 0;
		//k contador por cada recorrido
		int longitud = 1, k;
		//recorremos el arreglo
		for(int i=0; i<arr.length-1;i++){
			//contamos desde el indice i cuantos
			//elementos hay en orden ascendente
			for(k = i; k < arr.length-1 && arr[k] < arr[k+1]; k++);
			//si la longitud es mayor que la anterior guardarla
			if(longitud < k - i + 1)
				longitud = k - i + 1;
		}
		System.out.println("Longitud del subarreglo creciente mas grande: "+longitud);
	}
}

Descargar código fuente

Solución en Python

from array import array
#arreglo a evaluar
arr = array('d',[5,6,4,1,2,6,7,78,6,2,3,4,5,6,7,3,6,1])
#la longitud al menos sera 0;
#k contador por cada recorrido
longitud = 1
#k=0
#recorremos el arreglo
for i in range (0, len(arr)-1):
	#contamos desde el indice i cuantos
	#elementos hay en orden ascendente
	for k in range(i, len(arr)-1):
		if not arr[k] < arr[k+1]: break
	#si la longitud es mayor que la anterior guardarla
	if longitud < k - i + 1:
		longitud = k - i + 1
print "Longitud del subarreglo creciente mas grande: "+str(longitud)

Descargar código fuente

Representación formal de la solución

Por supuesto, el algoritmo planteado es solo la aproximación más sencilla, mas no la más eficiente de todas.

9 Comentarios | deja el tuyo

Arreglos bidimensionales en C#

Las matrices o arreglos de dos dimensiones, son arrays bidimensionales cuyos elementos tienen dos indices. En C Sharp existen dos tipos de arreglos bidimensionales, los rectangulares y los dinámicos. Por lo general, cuando accedemos a arreglos bidimensionales utilizamos los términos filas y columnas.

En los arreglos bidimensionales rectangulares, cada fila tiene la misma cantidad de columnas. Por otro lado, las filas de los arreglos bidimensionales dinámicos pueden tener diferente cantidad de columnas. A continuación, una serie de ejemplos en donde se explica cómo se declara e inician los dos tipos de arreglos:

Leer el resto de la entrada…

5 Comentarios | deja el tuyo

Busqueda Binaria – C Sharp

Hace unos dí­as y poní­a un ejemplo acerca de búsquedas lineales en arreglos, ésta vez hablaremos acerca de las búsquedas lineales, un método mucho más rápido para buscar elementos.

¿Cómo funciona este método? Para poder aplicar éste método de búsqueda es necesario que el arreglo esté ordenado; posteriormente, se aplica el siguiente algoritmo: se ubica el elemento de la mitad del arreglo, entonces, si el número que se está buscando dentro del arreglo es menor al número de la mitad, se busca el número de la mitad entre el inicio del y la mitad del mismo, y así­ hasta encontrar el elemento deseado.

Por ejemplo, suponiendo que tenemos un arreglo con los siguientes valores:

2, 4, 5 , 6, 8, 9, 10, 12, 24, 34, 46, 56, 60, 67, 78, 89, 90

…y queremos buscar el valor 10; tenemos que, el elemento de la mitad contiene el valor 24. Puesto que 24 > 10, buscamos el valor intermedio entre el principio del arreglo y la mitad del mismo, esto es 8. Puesto que 8 < 10, buscamos el valor intermedio entre 8 y la mitad del arreglo (24), esto es 10. Así­, con tan solo 3 bucles, hemos conseguido el valor buscado.

Vamos con el código del programa, que nos sacará de toda duda:

Leer el resto de la entrada…

6 Comentarios | deja el tuyo