¿Cómo encontrarías todos los trillizos pitagóricos en una matriz de n números?

Answer 1

No conozco una solución mejor que O (n ^ 2), y eso es fácil de lograr.

Aquí hay un fragmento de código (Java) que calcula el número de triples en el tiempo O (n ^ 2), suponiendo que no haya duplicados en la lista y que todos los números sean positivos.

Set X = new HashSet(); for(int i=0; i<n; i++) { X.add(A[i]*A[i]); } int ans = 0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(X.contains(A[i]*A[i]+A[j]*A[j])) { ans++; } } } 

La única observación no trivial es que podemos usar una tabla hash para decidir si se puede completar un triple dados los primeros dos elementos en O (1), que es cómo vencemos al algoritmo trivial O (n ^ 3).

Si hay duplicados, entonces debe reemplazar X con una estructura que cuenta el número de ocurrencias de un elemento en una matriz. Si su matriz contiene “0”, este fragmento da respuestas falsas (considere la matriz [0,1]), pero ningún triplete válido sin duplicados contiene 0, así que simplemente ignore los “triples” que contienen 0.

Answer 2

Coloque todos los números N en una tabla hash. Denote el número más grande en el conjunto como L.

Genere el árbol de triples pitagóricos primitivos como se describe en Árbol de triples pitagóricos primitivos hasta que la hipotenusa más pequeña sea mayor que L (se pueden podar ramas con hipotenos mayores que L). Para cada triple, verifique si sus elementos o una versión a escala de su elementos, aparecen en el conjunto.

Pero, ¿cuál es el tiempo de ejecución de este algoritmo?

El número de tripletas pitagóricas primitivas es una fracción constante de L (como límite) y cada nodo del árbol visitado produce una nueva tupla primitiva, por lo que enumerarlas toma tiempo O (L). (El límite es en realidad [matemáticas] {1 \ over 2 \ pi} [/ matemáticas] – vea la referencia a Lehmer 1900 en Mathworld: http://mathworld.wolfram.com/Pyt …) Visitamos no más de 3L hojas que son muy grandes

El problema aquí es que solicitó todos los trillizos pitagóricos (no solo los primitivos), por lo que la comprobación de las versiones escaladas lleva más tiempo. Para (3,4,5) debe marcar L / 5 triples adicionales, para (5,12,13) ​​debe marcar L / 13 triples adicionales, etc.

Un límite muy ondulado a mano para esta cantidad de trabajo es el número armónico [matemática] H (n) = 1/1 + 1/2 + 1/3 + 1/4 +… + 1 / n [/ matemática]. Ahora, está ondulado a mano porque algunas hipotenusas aparecen varias veces, pero el resultado límite anterior dice que el número total de tuplas sigue siendo una fracción (pequeña), por lo que deberíamos tener algo de espacio para la cabeza. Entonces, el tiempo de ejecución del algoritmo es (probablemente) proporcional a [math] L \ cdot H (L) [/ math].

Comprobación: no encontré una estimación explícita para el número de triples pitagóricos (no primitivos) con hipotenusa menor que un límite, pero A101930 – OEIS da números hasta [matemática] 10 ^ {12} [/ matemática], y [matemática] L \ log (L) [/ matemática] es un buen límite a través de ese rango. El tiempo de ejecución debe ser proporcional al número de triples pitagóricos, porque no visitamos ningún triple dado más de una vez, y solo se requiere un trabajo constante por triple (bajo el supuesto simplificador de que la multiplicación es tiempo constante).

Ahora, si la matriz de números es densa, es decir, si N es [matemática] \ Theta (L) [/ matemática], entonces este algoritmo podría superar a los algoritmos de tiempo cuadrático dados. Pero si N no es proporcional a L, entonces el algoritmo de tiempo cuadrático casi seguro proporcionaría una mejor opción.

Answer 3

Hay un pequeño truco que puede usarse para resolver el problema en el peor de los casos [matemática] O (n ^ 2) [/ matemática].

Supongamos que la matriz dada es [matemática] A [/ matemática]. Cree otra matriz [matemática] S [/ matemática], que contenga el cuadrado de todos los números en [matemática] A [/ matemática]. Ahora, ordene la matriz [math] S [/ math] en orden ascendente. Consideraríamos todos los elementos de [math] S [/ math], digamos [math] S_i [/ ​​math] como la hipotenusa al cuadrado y trataríamos de encontrar otros dos elementos en [math] S [/ math], digamos [math] S_j , S_k [/ math], de modo que [math] S_i = S_j + S_k, i \ neq j, i \ neq k, j \ neq k [/ math].

Para encontrar los números [matemática] S_j [/ matemática] y [matemática] S_k [/ matemática], comience con [matemática] j = 0 [/ matemática] y [matemática] k = n – 1 [/ matemática]. Si [math] S_j + S_k> S_i [/ ​​math], entonces necesitamos disminuir la suma [math] S_j + S_k [/ math]. Esto se puede hacer disminuyendo [math] k [/ math] a [math] n – 2 [/ math]. Por otro lado, si [math] S_j + S_k

Durante la programación, se debe garantizar que [math] j [/ math] y [math] k [/ math] aumenten y disminuyan respectivamente si son iguales a [math] i [/ math] en cualquier momento. Además, debe garantizarse que [math] j

EDITAR, agregando el comentario de Mark Gritter:

No necesitamos comenzar con [math] k = n – 1 [/ math] como, para cualquier triplete dado [math] j

Además, si para [matemática] S_i [/ ​​matemática], se encuentra un triplete, entonces aumente [matemática] j [/ matemática] a [matemática] j + 1 [/ matemática] y disminuya [matemática] k [/ matemática] a [ matemáticas] k – 1 [/ matemáticas] y repita el proceso. La iteración se detiene cuando [math] j> = k [/ math].

Answer 4

Aquí hay un enfoque:
1- Digamos que la lista ordenada es x1, … xn donde xn> x1
2- Tome cualquier 2 no.s xa y xb de esta lista donde xb> xa
(comience con xa = x1)
3- Descubre (xb-xa) y (xb + xa)
Si xb-xa y xb + xa son impares o ambos pares, entonces continúe o regrese al paso 2 y elija otro par.
Si xb-xa o xb-xa es primo, entonces regrese al paso 2 y elija otro par
4- calcular z = (xb-xa) * (xb + xa)
5- Evalúa si z es un cuadrado (por ejemplo, es la suma de 2 números triangulares consecutivos). En caso afirmativo, vaya al paso 6; de lo contrario, vuelva al 2
6- Elige todos los números entre xb y xa y cuadrátalos
7- Si alguno de estos coincide con z, entonces tienes tu triplete pitagórico. Regrese al paso 2 hasta que todos los pares se hayan agotado.

Answer 5

Tomemos el ejemplo 3,4,5 son triplete. Entonces
Paso 1: en la matriz, encuentre el número par / 2 y su factorización prima
Paso 2: márquelos A y C.
(aquí 4 => 2 y 1).
Paso 3: p = A ^ 2 – C ^ 2 y q = A ^ 2 + C ^ 2.
Paso 4: Encuentre p y q ambos juntos en una exploración en Array, si el triplete encontrado está allí, de lo contrario, no está allí.
PD: Esta es la fórmula de Euclides 🙂

Answer 6

Código de Rosetta> Triples pitagóricos

Answer 7

#include
#include

pithotriangles vacíos (int * a, int len) {
para (int i = 0; i {
para (int j = i + 1; j if (a [i] * a [i] + a [j] * a [j] == (a [k] * a [k])) {
printf (“\ n primer conjunto% d% d% d”, a [i], a [j], a [k]);
}
}
}
}
}

int main () {
int array [] = {1,2,3,4,5,6,7,8,9,10,11,12};
int len ​​= sizeof (array) / sizeof (int);
pythotriangles (matriz, len);
}