ckk*_*ght 7 c# math pythagorean
给定一个斜边(c在典型的方程a*a + b*b = c*c),什么是计算所有可能的整数值的有效途径a和b,这样a < b？
注:我已经看到了c为大于1e12,从而c*c大于long.MaxValue,从我所知道的,c*c倒是可以进入decimal,但.
所有毕达哥拉斯三元组(a,b,c)满足对于某些整数k,m和n的性质,
a = k(m ^ 2-n ^ 2),b = 2kmn,c = k(m ^ 2 + n ^ 2)
因此,首先考虑因素c.然后,对于c的每个不同因子k(即,对于因子的每个不同子集,乘以一起),找到满足c/k =(m ^ 2 + n ^ 2)的所有m和n.做后者将比其他人建议的蛮力方法花费更少的时间(你只需找到总和为c/k而不是c ^ 2的方格),但会识别所有三元组(a,b,c) .您也不需要使用bignums,因为所有中间结果都适合长.
我还建议你查看网页http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html标题下的"更通用的毕达哥拉斯三重计算器",其中包含嵌入式计算器,用javascript编写,完全符合你的要求.
有一种数学解决方案,即使对于较大的c值,也能快速找到a和b.不幸的是,事情并非那么简单.我试图给出一个简短的算法解释.我希望它不会太混乱.
既然给出了c并且你正在寻找a和b,你基本上想要求解形式的丢番图方程
n=x^2+y^2,
其中n给出.n = c*c是一个正方形并没有多大帮助,因此我正在描述任何n的解.如果n是素数,那么你可以使用 费马定理,来决定你的方程是否可以解决,并使用,因为莫伦指出Hermite-Serret算法找到解决方案,如果有的话.
为了解决n不是素数的情况,使用高斯整数是个好主意 .(高斯整数只是具有积分系数的复数).特别值得注意的是x + yi 的范数是
N(x+yi) = x^2+y^2.
因此,必须找到其范数为n的高斯整数x + yi.由于范数是乘法的,因此对于n的因子求解该等式然后乘以单个等式的高斯整数就足够了.让我举个例子.我们想解决
65 = x^2 + y^2.
这相当于找到x,y这样
N(x+yi) = 65
超过高斯整数.我们考虑65 = 5*13,然后我们使用Fermat来注意5和13都可以表示为两个正方形的总和.最后,我们通过使用Hermite-Serret算法使用强力发现
N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13
注意,我用负系数省略了Gaussion整数2-i,-2 + i等.那些当然也是解决方案.
因此,我们现在可以将这些解决方案相乘以获得
65 = 5*13 = N(2 + i)*N(2 + 3i)= N((2 + i)*(2 + 3i))= N(1 + 8i)
和
65 = 5*13 = N(2 + i)*N(3 + 2i)= N((2 + i)*(3 + 2i))= N(4 + 7i).
因此,人们得到了两个解决方案
1*1 + 8*8 = 65
4*4 + 7*7 = 65
还需要检查例如具有负系数的其他组合.除了排列和改变标志之外,它们不提供新的解决方案.
为了计算所有解决方案,还可以补充说,不需要计算c*c.找到c的因素是必要的.此外,由于a和b都小于c,因此高斯整数的乘积不能用64位整数系数表示.因此,如果小心,64位整数就足以解决问题.当然,使用像Python这样没有这种溢出问题的语言总是更容易.