¿Cuál es el mejor algoritmo para decir si un entero es una hipotenusa o no?

Answer 1

La fórmula de Euclides es una fórmula fundamental para generar triples pitagóricos dado un par arbitrario de enteros positivos [matemática] m [/ matemática] y [matemática] n [/ matemática] con [matemática] m> n [/ matemática] . La fórmula establece que los enteros

[matemáticas] a = m ^ 2-n ^ 2, b = 2mn, c = m ^ 2 + n ^ 2 [/ matemáticas]

formar un triple pitagórico. El triple generado por la fórmula de Euclides es primitivo si y solo si [math] m [/ math] y [math] n [/ math] son primos y [math] m – n [/ math] es impar.

Un triple pitagórico primitivo es aquel en el que [matemática] a, b [/ matemática] y [matemática] c [/ matemática] son co-primos (el máximo común divisor de [matemática] a, b [/ matemática] y [matemática ] c [/ math] es [math] 1 [/ math]). Si generamos un triple pitagórico [matemático] a, b [/ matemático] y [matemático] c [/ matemático]. Entonces [math] ka, kb, kc [/ math] también es un triple pitagórico para cualquier valor arbitrario de [math] k [/ math]. Primitivo significa [matemáticas] k = 1 [/ matemáticas].

Lo siguiente generará todos los triples pitagóricos únicamente:

[matemáticas] a = k (m ^ 2-n ^ 2), b = k (2mn), c = k (m ^ 2 + n ^ 2) [/ matemáticas]

donde [matemática] m, n [/ matemática] y [matemática] k [/ matemática] son enteros positivos con [matemática] m> n, m – n [/ matemática] impar, y con [matemática] m [/ matemática] y [math] n [/ math] co-prime.

Use esta información e intente implementarla usted mismo. Para su pregunta solo necesita encontrar el valor de [math] c [/ math] para todos [math] m [/ math] y [math] n [/ math] donde [math] m> n [/ math] y [matemáticas] (mn)% 2 [/ matemáticas] es [matemáticas] 1 [/ matemáticas]

Answer 2

Realmente quieres encontrar el conjunto de triples pitagóricos que estos son dados por

[matemáticas] a = k \ cdot (m ^ 2 – n ^ 2), \ \, b = k \ cdot (2mn), \ \, c = k \ cdot (m ^ 2 + n ^ 2) [/ math ]

donde m , n y k son enteros positivos con m > n , m – n impar y con m y n coprimo. Desea registrar el número c.

Pase por m, n con [math] m \ le \ sqrt {10 ^ 9} \ aprox 31,622 [/ math] y [math] n c y guárdelo en una tabla hash. Si no se encuentra c, calcule los múltiplos de [matemática] c <10 ^ 9 [/ matemática] y almacénelos.

Esto es mucho más rápido que el enfoque ingenuo, ya que tiene muchos menos casos para verificar.

Esto no molesta en comprobar si m, n son primos, lo que podría conducir a una mayor optimización. También podría valer la pena leer una Fórmula para generar triples pitagóricos.

Answer 3

Fórmula de Euclides de triple pitagórico primitivo. Es uno de los temas más buscados.

Aquí hay una explicación completa:

http://stackoverflow.com/questio …

Si no funcionó, avíseme en qué idioma está utilizando. Voy a hacer una idea.

– Soubhik

Answer 4

Para cada i, j (i

Ahora su tabla hash contiene todas las hipotenusas y solo verifica si un entero dado aparece en la tabla hash.

Este es solo el punto de partida con la complejidad de tiempo y espacio como O (n ^ 2). Te lo dejo para que lo optimices.