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);
}
}
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)
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.
13 Comentarios | deja el tuyo
Algoritmo: Obtener longitud del mayor subarreglo creciente de un arreglo: A falta de tiempo para cosas más profe.. http://tinyurl.com/ngjl6e
(Colombia) Cristian Castiblanco: Algoritmo: Obtener longitud del mayor subarreglo creciente de un arreglo http://bit.ly/OC55j
¿no te conviene modificar el incremento del ciclo?
for(int i = 0; i < arr.length – 1; i = k + 1)
No le veo caso volver a recorrer los elementos que ya recorriste con el ciclo interno
Tienes toda la razón __nesthor. No es necesario recorrerlo de cero en cada ciclo. Gracias por el aporte.
Un saludo!
Algoritmo: Obtener longitud del mayor subarreglo creciente de un arreglo: A falta de tiempo para cosas más profe.. http://bit.ly/OC55j
Me puedes decir que programa usas para pasar formulas matemáticas a una imagen?
Un Saludo.
Hola Shrick. Uso Latex.
Un saludo!
o.O, que rápido contestas, muchas gracias, me lo imaginaba, pero queria estar seguro porque a lo mejor usabas algún editor visual, como alternativa a escribir code xDD.
Por cierto eso que tienes puesto, lo voy a dar dentro de nada en metodología de la programación.
Te preguntaba porque lo veo de una forma simple, concisa y directa de simplificar el programa (aunque lo único que he identificado hay son los asertos esos xD, si es que es eso).
Hola Shrick.
En realidad es una manera de representar la precondición y postcondición del programa… en pocas palabras especificar el programa.
Para usar una notación de ese estilo, y crear un modelo del programa, se usa GCL. Este lenguaje es utilizado para lo que se conoce como el análisis y verificación de programas; el tema es bastante interesante ya que trata la programación desde un enfoque más matemático y científico, y no tan artesanal como nos acostumbran en la U.
Un saludo!
Sí eso es lo que nos intenta meter en esta asignatura, hacer de la programación un enfoque como bien dices matemático y cientifico.
Personalmente, si te doy mi opinión, yo veo la programación como arte, como si de escribir poesía se tratara, donde versos encajan en el poema con sus rimas, a similitud de las líneas en los programas, para hacer que estas hagan lo que quieres que haga.
Hola
Esto ya me fue muy dificil
Saludos
mal muy mal no tienen para IDE free pascal linux lazarus