Para un triple pitagórico integral, es decir, [matemática] (a, b, c) [/ matemática] que satisface [matemática] a ^ 2 + b ^ 2 = c ^ 2 [/ matemática], la forma general [3] es:
- [matemáticas] a = k \ veces (m ^ 2 – n ^ 2) [/ matemáticas]
- [matemáticas] b = k \ veces (2 millones) [/ matemáticas]
- [matemáticas] c = k \ veces (m ^ 2 + n ^ 2) [/ matemáticas]
Suponga que debe calcular todos los triples pitagóricos dada una sola hipotenusa c [2], un algoritmo bastante eficiente se ve así:
- Agotar todos los divisores k de c.
- Para cada k, agote n st, [math] n ^ 2 \ le \ frac {c} {k} [/ math], y resuelva para m.
- Si n es un número entero, agregue [math] (kn, km, c) [/ math] al resultado.
El paso 1 llevaría tiempo [matemático] O (\ sqrt {c}) [/ matemático] con un enfoque ingenuo, y esto podría acelerarse con algún procesamiento previo (por ejemplo, cuando necesita procesar muchas instancias [2]) . Y solo necesitamos hacer los pasos 2-3 para f veces, donde f es el número de factores para una c dada , que es pequeño en la práctica. Para el paso 2, lleva [math] O (\ sqrt {c}) [/ math] tiempo para k = 1, y menos para otras k ‘ s.
Complejidad del tiempo total (un límite superior bastante suelto): ~ [matemática] O (f \ sqrt {c}) [/ matemática]. Parece ser bastante rápido para [math] c \ le 10 ^ 7 [/ math]. ( f es como máximo 448, para c = 8648640, en este rango)
- ¿Cómo puedo generar 8 números (aleatorios) que deberían oscilar entre 0 y 80 y la suma de esos 8 números generados debería ser 80.?
- Combinatoria: Sea el conjunto de {(1,1), (1, -1), (-1,1)} -trayecto de red que comienza en (1,1), no use el mismo vértice dos veces, y nunca toque el eje x o el eje y. ¿Cuántos caminos terminan en el punto (4,8)?
- ¿Cómo puedo determinar el límite superior más ajustado para el problema 30 en el Proyecto Euler?
- ¿Cómo funciona la función isPerfect de esta solución, ya que el problema 29 del proyecto Euler está calculando el recuento?
- ¿Cuál es la probabilidad de que un elemento permanezca en la misma posición en la matriz de n elementos distintos (por ejemplo, 0..n-1) después de realizar k intercambios aleatorios (el intercambio se realiza como elegir los índices k1 y k2 (k1 <k2) y cambiar un [k1] y un [k2]) en la matriz? Además, ¿cuál es la probabilidad de que la matriz permanezca igual después de estos k intercambios aleatorios?
Si está interesado, aquí hay un pseudocódigo aproximado:
c: = Input () // Una hipotenusa entera
ListOfPairs: = [] // Almacenamiento (a, b) st, a ^ 2 + b ^ 2 = c ^ 2
Para k en Factores de (c):
s: = c / k
Para n: = 0 a Sqrt (s / 2): // Optimización local, sabemos que m> = n
mSquare = s – n ^ 2
m: = Piso ( Sqrt (mSquare))
Si m * m = mSquare:
a = m ^ 2 – n ^ 2
b = 2 nm
ListOfPairs.Push ((ka, kb))
ListOfPairs.Push ((kb, ka))
Return ListOfPairs.RemoveDuplicates ()
Observaciones:
[1] El algoritmo propuesto se verifica resolviendo un problema de codificación que requiere generar todos los triples pitagóricos dados una hipotenusa.
[2] Si necesita resolver muchas instancias a la vez con un rango de entrada conocido, tal vez recorrer en bucle ( k, n, m ) y luego generar todos los triples pitagóricos (de abajo hacia arriba) podría ser más eficiente.
[3] Para los triples pitagóricos primitivos, suelta la k de la forma general.
