Hola,
tengo que hacer un ejercicio en C++ que lee una secuencia de números (monedas) todas iguales menos una. Me tiene que decir el indice de la moneda que pesa diferente precedido de + o - dependiendo de si pesa mas o menos que el resto.
Para la entrada:
7
9 9 9 9 10 9 9
Tengo que obtener la salida: +4
He hecho la siguiente función que compara dos segmentos de la secuencia y devuelve 0 si pesan lo mismo, 1 si el primero pesa más o -1 si pesa más el segundo:
int pesa(int v[], int ia, int ib, int n) {
int t = 0;
for (int i = 0; i < n; i++)
t += (v[ib+i] - v[ia+1]);
return t ? (t < 0? - 1:1) : 0;
}
Me falta hacer una función recursiva que, mediante llamadas a la funcion pesa(), se quede con el elemento que pesa diferente. Ahí es donde ando un poco perdido. Agradecería cualquier ayuda.
Si es como estoy pensando, en realidad solo tienes que hacer un bucle.
Primero, haces una comparación entre 3 unidades, las dos que sean iguales son las "iguales".
Luego haces un bucle buscando una que no sea igual, y lo tienes ya.
En el primer caso tienes 3 opciones, la 1 y 3 son iguales, o la 1 y 2 o la 2 y 3. El valor restante es el que buscas.
Luego simplemente recorre la secuencia almacenada buscando ese valor.
Bueno, tengo una idea más o menos parecida.
Comparas las dos primeras. Si son distintas entonces una de ellas es "igual" a todas las demás, y la otra es la "distinta". Para dilucidar, debes revisar el tercer valor.
Si las dos primeras son iguales, pues buscas de la 3ra en adelante la primera que sea distinta y ya.
Ojo, sólo funcionará si el array tiene los valores correctamente: todos iguales y uno desigual.
int distinto( int *x, int N) {
int i;
if ( N < 3 ) return -1;
if ( x[0] == x[1] ) { /* los dos primeros iguales */
/* repetir desde el tercero en adelante, mientras
* sea igual al primero */
for ( i = 2; i < N && x[i] == x[0]; i++ )
;
if ( i < N )
return x[i] > x[0] ? i: -i;
else
return -1;
}
else /* los dos primeros distintos, revisar el tercero */
if ( x[0] == x[2] )
return x[1] > x[0] ? 1 : -1;
else
return 0;
}
Esta función la acabo de probar y me funcionó bien en todas las combinaciones.
OBSERVACIONES: (1) Si el distinto es el primero, devuelve el índice cero (no tiene signo). De otro modo, devuelve + o - según el caso.
(2) Si todos los elementos son iguales, o tiene menos de tres elementos, devuelve -1 (condición de error, jeje).
Una implementación ligeramente distinta que funciona correctamente siempre y cuando la entrada sea valida y con la misma limitante que ya indico yoel_alejandro (el cero negativo) es:
int fn(int const a[])
{
int i;
for (i = 1; a[i] == a[0]; i++)
;
if (i == 1)
i = a[0] == a[2];
return a[i] - a[!i] > 0 ? i : -i;
}
Un saludo