Solución a la Tarea 5: Secuencias saltarinas
Hay varias formas de resolver este problema. Una de ellas es la
siguiente. Creemos un nuevo vector d
con n componentes
inicializadas en 0. La componente d[i]
va a contar cuantas veces aparece el número i como diferencia. Si d[i] = 0 entonces i no
apareció. Hay que tener cuidado al actualizar d, puesto que las diferencias pueden
ser positivas o negativas (es decir, debemos calcular el valor
absoluto) y además pueden estar fuera del intervalo 1 a n-1 (y por lo tanto no existe una
componente correspondiente en d). Al final sólo revisamos cual
es el primer valor cero en d:
#include <stdio.h>
int main(void)
{
int i, n, a;
int x[1000], d[1000];
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &x[i]);
d[i] = 0;
}
for (i = 1; i < n; i++) {
a = x[i] - x[i-1];
a = (a > 0) ? a : -a;
if (a > 0 && a < n)
d[a]++;
}
for (i = 1; (i < n) && d[i]; i++);
printf("%d\n", (i < n) ? i : 0);
return 0;
}
Los valores de entrada y salida empleados para la evaluación
fueron los siguientes:
Entrada
Salida
4 1 4 2
3
0
5 3 1 5 1
2
3
10 1 2 4 7 3 -2 -8 -1 7
-2 0
5 5 1 2 9
7
3
10 0 8 1 7 2 6 3 5 4
4
9
10 0 1 2 3 4 5 6 7 8
9
2
10 3 1 4 1 5 9 2 6 5
7
5
10 2 7 1 8 2 8 1 8 2
8
1
10 99 90 98 91 97 92 96 93 91 92 0
10 0 2 4 6 8 6 4 2 0
2
1
Para probar su tarea en UNIX, escriban la instrucción gcc saltarNN.c -o saltar para
compilar su programa, y la instrucción ./saltar para correrlo.
Algunos errores comúnes fueron: (a) Olvidar calcular el valor
absoluto de la diferencia. (b) Calcular una diferencia de más o
de menos. (c) Olvidar que algunas diferencias pueden ser demasiado
grandes. (d) Dar cualquier diferencia que no apareciera en lugar de la
menor.