triangulo - hallar la cantidad de cuadrados

Número total de triángulos posibles de n números

Question

Si se dan n números, ¿cómo encontraría el número total de triángulos posibles? ¿Hay algún método que haga esto en menos de O(n^3) tiempo?

Estoy considerando las condiciones a+b>c , b+c>a y a+c>b para ser un triángulo.

Answer 1

Hay un algoritmo simple en O(n^2*logn) .

• Supongamos que desea que todos los triángulos sean triples (a, b, c) donde a <= b <= c .
• Hay 3 desigualdades de triángulos, pero solo a + b > c suficiente (otras entonces se mantienen trivialmente).

Y ahora:

• Ordene la secuencia en O(n * logn) , por ejemplo, por combinación de ordenación.
• Para cada par (a, b), a <= b el valor restante c debe ser al menos b y menor que a + b .
• Por lo tanto, debe contar el número de elementos en el intervalo [b, a+b) .

Esto se puede hacer simplemente buscando en binario a + b ( O(logn) ) y contando el número de elementos en [b,a+b) para cada posibilidad que es ba.

Todos juntos O(n * logn + n^2 * logn) que es O(n^2 * logn) . Espero que esto ayude.

Answer 2

He desarrollado un algoritmo que se ejecuta en tiempo O (n ^ 2 lgn). Creo que es correcto ... El código está wtitten en C ++ ...

int Search_Closest(A,p,q,n)  /*Returns the index of the element closest to n in array 
                                  A[p..q]*/

{
   if(p<q)
   {
      int r = (p+q)/2;
      if(n==A[r])
         return r;
      if(p==r)
         return r;
      if(n<A[r])
         Search_Closest(A,p,r,n);
      else 
         Search_Closest(A,r,q,n);
   }
   else
      return p;
 }



   int no_of_triangles(A,p,q) /*Returns the no of triangles possible in A[p..q]*/
   {
      int sum = 0;
      Quicksort(A,p,q);  //Sorts the array A[p..q] in O(nlgn) expected case time
      for(int i=p;i<=q;i++)
          for(int j =i+1;j<=q;j++)
           {
               int c = A[i]+A[j];
               int k = Search_Closest(A,j,q,c);
               /* no of triangles formed with A[i] and A[j] as two sides is (k+1)-2 if A[k] is small or equal to c else its (k+1)-3. As index starts from zero we need to add 1 to the value*/
               if(A[k]>c)
                    sum+=k-2;
               else 
                    sum+=k-1;
            }
       return sum;
   }

Espero eso ayude........

Answer 3

Parece que no hay algoritmo mejor que O (n ^ 3). En el peor de los casos, el conjunto de resultados tiene elementos O (n ^ 3).

Por ejemplo, si se dan n números iguales, el algoritmo debe devolver los resultados n * (n-1) * (n-2).

Answer 4

Sean a, byc tres lados. La siguiente condición debe ser válida para un triángulo (la suma de dos lados es mayor que el tercer lado)

i) a + b > c
ii) b + c > a
iii) a + c > b

Los siguientes son los pasos para contar triángulo.

1. Ordena la matriz en orden no decreciente.

2. Inicialice dos punteros ''i'' y ''j'' al primer y segundo elementos respectivamente, e inicie el conteo de triángulos como 0.

3. Corrija ''i'' y ''j'' y encuentre el índice más a la derecha ''k'' (o el más grande ''arr [k]'') tal que ''arr [i] + arr [j]> arr [k]''. El número de triángulos que se pueden formar con ''arr [i]'' y ''arr [j]'' como dos lados es ''k - j''. Agrega ''k - j'' al conteo de triángulos.

Consideremos ''arr [i]'' como ''a'', ''arr [j]'' como b y todos los elementos entre ''arr [j + 1]'' y ''arr [k]'' como ''c''. Las condiciones mencionadas anteriormente (ii) y (iii) se cumplen porque ''arr [i] <arr [j] <arr [k]''. Y verificamos la condición (i) cuando seleccionamos ''k''

4. Incrementar ''j'' para arreglar el segundo elemento de nuevo.

Tenga en cuenta que en el paso 3, podemos usar el valor anterior de ''k''. La razón es simple, si sabemos que el valor de ''arr [i] + arr [j-1]'' es mayor que ''arr [k]'', entonces podemos decir ''arr [i] + arr [j]'' también será mayor que ''arr [k]'', porque la matriz está ordenada en orden creciente.

5. Si ''j'' ha llegado a su fin, entonces incremente ''i''. Inicialice ''j'' como ''i + 1'', ''k'' como ''i + 2'' y repita los pasos 3 y 4.

Complejidad del tiempo: O (n ^ 2). La complejidad del tiempo parece más debido a 3 bucles anidados. Si observamos más de cerca el algoritmo, observamos que k se inicializa solo una vez en el bucle más externo. El bucle más interno se ejecuta a lo sumo O (n) en cada iteración del bucle más externo, porque k comienza desde i + 2 y va hasta n para todos los valores de j. Por lo tanto, la complejidad del tiempo es O (n ^ 2).

Answer 5

Si utiliza una ordenación binaria, eso es O (n-log (n)), ¿verdad? Mantenga su árbol binario a mano, y para cada par (a, b) donde ab y c <(a + b).

Answer 6

Supongamos que no hay números iguales en n dada y se permite usar un número más de una vez. Por ejemplo, dimos un número {1,2,3}, por lo que podemos crear 7 triángulos:

1. 1 1 1
2. 1 2 2
3. 1 3 3
4. 2 2 2
5. 2 2 3
6. 2 3 3
7. 3 3 3

Si alguna de esas suposiciones no es cierta, es fácil modificar el algoritmo.

Aquí presento un algoritmo que lleva tiempo O (n ^ 2) en el peor de los casos:

1. Ordenar números (orden ascendente). Tomaremos triples ai <= aj <= ak, de modo que i <= j <= k.
2. Para cada i, j necesitas encontrar el k más grande que satisfaga ak <= ai + aj. Entonces todos los triples (ai, aj, al) j <= l <= k es un triángulo (porque ak> = aj> = ai solo podemos violar ak <a i + aj).

Considere dos pares (i, j1) y (i, j2) j1 <= j2. Es fácil ver que k2 (que se encuentra en el paso 2 para (i, j2))> = k1 (que se encuentra en el paso 2 para (i, j1)). Significa que si iteras para j, y solo necesitas verificar los números que comienzan con k anterior. Por lo tanto, le da una complejidad de tiempo O (n) para cada i particular, lo que implica O (n ^ 2) para todo el algoritmo.

Código fuente de C ++:

int Solve(int* a, int n)
{
    int answer = 0;
    std::sort(a, a + n);

    for (int i = 0; i < n; ++i)
    {
        int k = i;

        for (int j = i; j < n; ++j)
        {
            while (n > k && a[i] + a[j] > a[k])
                ++k;

            answer += k - j;
        }
    }

    return answer;
}

Actualización para downvoters:

¡Esto definitivamente es O (n ^ 2)! Lea detenidamente "Una introducción de algoritmos" por el capítulo de Thomas H. Cormen sobre Análisis amortizado (17.2 en la segunda edición). Encontrar complejidad al contar los bucles anidados es completamente incorrecto a veces. Aquí trato de explicarlo lo más simple que pude. Vamos a arreglar i variable. Entonces, para eso, debemos iterar j desde i hasta n (significa operación O (n)) e interno mientras que la iteración en bucle k desde i hasta n (también significa operación O (n)). Nota: No comienzo mientras estoy en bucle desde el principio para cada j . También necesitamos hacerlo para cada i de 0 a n . Entonces nos da n * (O (n) + O (n)) = O (n ^ 2) .

Answer 7

posible respuesta

Aunque podemos usar la búsqueda binaria para encontrar el valor de ''k'', ¡por lo tanto, mejoramos la complejidad del tiempo!

Answer 8

N0,N1,N2,...Nn-1
sort
X0,X1,X2,...Xn-1 as X0>=X1>=X2>=...>=Xn-1
choice X0(to Xn-3) and choice form rest two item x1...
choice case of (X0,X1,X2)
check(X0<X1+X2)
OK is find and continue
NG is skip choice rest