讓我做下，本來懶得做的，但是他說打表就OK了，于是我就欣然答應(yīng)了。。。奈何他眼中的打表難易度和我眼中不一樣，再次看到了數(shù)學(xué)系高材生和我的差距，嘿嘿。
第一次嘗試，失敗。
我說，不就是勾股定理a^2+b^2=c^2嗎？結(jié)果他說，你再去補(bǔ)補(bǔ)數(shù)學(xué)知識。。。。
于是給了我一個鏈接，我一看，不就是百度百科的勾股數(shù)嗎，于是就暫時擱淺了。
今晚第二次嘗試，仍然失敗。
依稀記得昨天他給我說了有個什么勾股數(shù)公式，在百度百科那個勾股數(shù)的最下面介紹了，但是我看了半天，還是有點(diǎn)迷糊。
然后讓他把代碼給我看看，好吧，結(jié)合百科介紹的勾股數(shù)公式，茅塞頓開。
這里給出勾股數(shù)公式：
直角三角形三條邊a, b, c，其中a,b是直角邊。
則 a=2*m*n
b=m^2-n^2
c=m^2+n^2
當(dāng)然，這是有前提條件的，也就是其局限性：“勾股數(shù)的公式還是有局限的。勾股數(shù)公式可以得到所有的基本勾股數(shù)，但是不可能得到所有的派生勾股數(shù)。比如6，8，10；9，12，15…，就不能全部有公式計(jì)算出來”
也就是說，3,4,5可以求出來，但是其倍數(shù)6,8,10就不行了。
這里要注意幾個問題：
1.構(gòu)成三角形的條件：
2*m*n+m^2-n^2 > m^2+n^2
既m>n
2.a, b, c互質(zhì)，即無法得到派生的勾股數(shù)。
以下是代碼：
// Tanky Woo
// www.WuTianQi.com
#include <iostream>
#define M 1000000
int arr[M+1];
using namespace std;
int gcd(int a, int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
void init()
{
for(int i=1; i<=800; ++i)
for(int j=i+1; 2*j*j+2*j*i<=M; ++j)
{
int x, y, z;
x=2*i*j;
y=j*j-i*i;
z=j*j+i*i;
//確保x,y,z互質(zhì)
if(gcd(gcd(x, y), z) == 1)
{
int t = x+y+z;
int tmp = 1;
while(tmp*t <= M)
{
arr[tmp*t]++;
++tmp;
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
init();
int n, m;
while(scanf("%d%d",&n,&m) != EOF){
int pos = 0;
int Max = 0;
for(int i=n; i<=m; i++){
if(arr[i] > Max){
Max = arr[i];
pos = i;
}
}
printf("%d %d\n",pos, Max);
}
return 0;
}
Tanky Woo原創(chuàng)，轉(zhuǎn)載請注明： 轉(zhuǎn)載自Tanky Woo
文章標(biāo)題: 勾股數(shù)公式
本文鏈接地址: http://www.wutianqi.com/?p=1632