arrays - why - Triplete cuya suma está dentro del rango(1,2)
instagram hashtags on comments or caption (4)
Dado
nnúmeros reales positivos en un conjunto, determine si existe un triplete entre este conjunto de forma que la suma del triplete esté en el rango(1, 2). Hazlo en tiempo lineal y espacio constante.
- La matriz no está ordenada.
- los números son positivos
- los números son números reales
Cualquier ayuda sería muy apreciada. Gracias.
El problema en su totalidad como se ha dicho es indecidible. Esto se debe al hecho de que para dos números reales a y b no se puede decidir si a > b mantiene (también vea esta respuesta mía). Pero debe hacer al menos una comparación de un número real con un valor entero para resolver ese problema. La comparación con un número entero no facilita el problema, ya que podría tener un número real que es 2,00...001 donde existe un número arbitrario de ceros entre los dígitos 2 y 1 que no conoce de antemano. Almacenar dichos números reales (probablemente no todos, pero muchos de ellos) en la memoria principal de una computadora no es un gran problema para tales números específicos, ya que pueden representarse mediante un algoritmo de aproximación.
para más información, sugiero leer Teoría de la Complejidad de las Funciones Reales
El truco es encontrar una manera de categorizar las posibles soluciones y obtener una solución de espacio constante de tiempo lineal para cada una.
Considere los tres rangos X = (0,2/3), Y = [2/3,1], Z = (1,2) . Como máximo, un valor puede provenir de Z (si dos valores provienen de Z , entonces la suma excederá 1+1=2 ). Del mismo modo, al menos un valor debe provenir de X Supongamos que hay 3 valores a <= b <= c modo que 1 <= a+b+c <= 2 . Luego, considere qué clases posibles de soluciones son factibles:
A) `a /in X, b /in X, C /in X`
B) `a /in X, b /in X, C /in Y`
C) `a /in X, b /in X, C /in Z`
D) `a /in X, b /in Y, C /in Y`
E) `a /in X, b /in Y, C /in Z`
Entonces, ¿cómo podemos probar cada caso?
El caso A es increíblemente fácil de probar: la suma está garantizada por debajo de 2, por lo que solo tenemos que probar que la suma más grande (los 3 elementos más grandes en X) excede de 1.
El caso C es increíblemente fácil de probar: ya que se garantiza que la suma es superior a 1, solo necesitamos verificar si la suma es inferior a 2. Así que para hacer eso, solo necesitamos probar los 2 valores más pequeños en X y menor valor en Z
Los casos D y E son similares a C (dado que la suma debe ser de al menos 4/3> 1, elija los valores más pequeños posibles en cada clase).
El caso B es el único caso complicado. 0 < a+b < 4/3 y 2/3 <= c <= 1 . Para manejar el caso B, consideramos estos intervalos: X1 = (0, 1/2), X2 = [1/2 2/3), Y = [2/3, 1].
Esto resulta en tres casos válidos siguientes:
B1. a en X1, b en X2, c en Y
B2. a en X1, b en X1, c en Y
B3. a en X2, b en X2, c en Y
Caso B1 y B3: la suma de tres números siempre es mayor que 1, por lo que tomamos valores mínimos y verificamos si es menor que 2 o no.
Caso B2: La suma de tres números siempre es menor que 2, por lo tanto, tomamos la suma máxima y verificamos si es mayor que 1 o no.
Para resumir, las pruebas son:
-
|X| >= 3|X| >= 3yXmax(1) + Xmax(2) + Xmax(3) >= 1 -
|X| >= 2|X| >= 2,|Z| >= 1|Z| >= 1yXmin(1)+Xmin(2)+Zmin(1) <= 2 -
|X| >= 1|X| >= 1,|Y| >= 2|Y| >= 2yXmin(1)+Ymin(1)+Ymin(2) <= 2 -
|X| >= 1|X| >= 1,|Y| >= 1|Y| >= 1,|Z| >= 1|Z| >= 1yXmin(1)+Ymin(1)+Zmin(1) <= 2 -
|X| >= 2|X| >= 2,|Y| >= 1|Y| >= 1yXmax(1) + Xmax(2) + Ymin(1) < 2 -
|X| >= 2|X| >= 2,|Y| >= 1|Y| >= 1yXmin(1) + Xmin(2) + Ymax(1) > 1)
Cada prueba se puede realizar en tiempo lineal y espacio constante (solo necesita encontrar Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1) , todos los cuales se pueden encontrar en una pasada, incluso si los datos no están ordenados)
Entonces, tienes una matriz de tipos de datos dobles de longitud n. Inicializar tres variables a, byc como primeros 3 valores de la matriz. Ahora, iterar de i = 3 a n y verificar lo siguiente: 1) Verifique si la suma cae en (1, 2), si lo hace, entonces devuelva verdadero. 2) Si no, verifique si la suma es mayor que 2, si es así, entonces reemplace MAX (a, b, c) al elemento actual arr [i]. 3) De lo contrario, la suma debe ser menor que 1 y luego se reemplaza MIN (a, b, c) por el elemento actual arr [i]. Y finalmente, después de salir de la verificación de bucle una vez más para el último triplete si la suma cae en (1,2), entonces devolver verdadero, de lo contrario devolver falso.
enter code here
double a=arr[0], b=arr[1], c=arr[2];
for(int i=3 ; i<n ; i++){
// check if sum fall in (1, 2)
if(a+b+c > 1 && a+b+c < 2){
return 1;
}
// if not, then check is sum greater than 2
// if so, then replece MAX(a,b,c) to new number
else if(a+b+c > 2){
if(a>b && a>c){
a = arr[i];
}
else if(b>a && b>c){
b = arr[i];
}
else if(c>a && c>b){
c = arr[i];
}
}
// else then sum must be less than 1
// then replace MIN(a,b,c) to new number
else{
if(a<b && a<c){
a = arr[i];
}
else if(b<a && b<c){
b = arr[i];
}
else if(c<a && c<b){
c = arr[i];
}
}
}
// check for last a, b, c triplet
if(a+b+c > 1 && a+b+c < 2){
return 1;
}
else{
return 0;
}
Sobre la base de las ideas de @Soul Ec, este es el código que se me ocurrió. Funciona perfectamente bien.
vector<double> x;
vector<double> y;
vector<double> z;
double d = (double)2/3;
for(i = 0 ; i < arr.size() ; i++){
if(arr[i] >= 0 && arr[i] < d) x.push_back(arr[i]);
else if(arr[i] >= d && arr[i] <= 1) y.push_back(arr[i]);
else z.push_back(arr[i]);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
sort(z.begin(), z.end());
int xsz = x.size();
int ysz = y.size();
int zsz = z.size();
if(xsz >= 3 && x[xsz-1] + x[xsz-2] + x[xsz-3] >= 1.0) return 1;
if(xsz >= 2 && zsz >= 1 && x[0] + x[1] + z[0] <= 2.0) return 1;
if(xsz >= 1 && ysz >= 2 && x[0] + y[0] + y[1] <= (double)2.0) return 1;
if(xsz >= 1 && ysz >= 1 && zsz >= 1 && x[0] + y[0] + z[0] <= 2.0) return 1;
if(xsz >= 2 && ysz >= 1){
if(x[xsz-1] + x[xsz-2] + y[0] < 2.0 && x[xsz-1] + x[xsz-2] + y[0] > 1.0) return 1;
if(x[0] + x[1] + y[ysz-1] > 1.0 && x[0] + x[1] + y[ysz-1] < 2.0) return 1;
}