Ejercicio de monedas

[spf9]

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.

[Orubatosu]

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.

[Yoel Alejandro]

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.

Código (cpp) [Seleccionar] Expandir


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).

[rir3760]

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:

Código (c) [Seleccionar] Expandir

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