Nombre Password [ Regístrate ]

De picos pardos (OIE 5 - 2001) - Solución

 

Se nos pide determinar picos (puntos que tienen un valor mayor que el anterior y el posterior) dentro de secuencias de números enteros.

Según las especificaciones iniciales, diferenciemos inicialmente varios casos que pueden llevar a confusión:

- {1,2,5,3,1} -> Caso simple, hay un pico de valor 5 y longitud 1.
- {5,4,3,2,1} -> No hay picos, pues según la primera condición no debemos considerar el 5 como pico.
- {1,5,5,4,6,6,6,3} -> Hay dos picos, uno de longitud 2 y otro de longitud 3, los cuales comienzan en las posiciones 2 y 5, respectivamente.

Nótese que en la salida se nos piden dos datos: la posición del primero de los puntos del pico y la longitud total del pico. No es relevante a la salida, por tanto, el valor que tenga un pico, aunque será necesario mantener el valor del último punto leído en una variable para compararlo con el siguiente.

También hay que darse cuenta de que para saber si un punto puede ser un pico nos basta con saber cuál es el valor del punto anterior a él y el posterior, por lo que la utilización de un array para almacenar todos los valores es innecesaria.

El algoritmo usa cuatro variables (todas de tipo int):

n: es la variable en la que se almacena cada número según se lee.
pos: indica la posición que estamos leyendo. Inicialmente vale 1 y se irá incrementando según se lean puntos hasta el final de la secuencia (n=0).
ant: en ella se almacena el valor del punto anterior al que se acaba de leer.
pic: si se encuentra un pico se marca a 1 y se va incrementando según crezca la longitud del pico.

Se van leyendo valores de la entrada. Cada vez que se lee un valor, se compara el valor leído n con la variable ant, el valor anterior. De esta comparación nos quedan tres casos:

  1. n > ant. El punto leído es un pico provisional. Es decir, el valor leído será un pico a menos que después se encuentre otro valor más grande. Situamos pic=1.
  2. n==ant. Si el punto anterior está marcado como pico (pic>0), aumentamos pic en 1, pues el valor que acabamos de leer es parte de un pico de longitud mayor de 1.
  3. n < ant. Si pic!=0 entonces había un pico en ant que ya ha terminado, así que se imprime.

 

Código

Código fuente en C

Código fuente en Pascal



© (2001-2008) ALGORITMIA.NET - Política de privacidad