勾股定理高效算法问题
题目：求1000以内，符合a*a+b*b=c*c的三元组(a,b,c)，用尽量高效的算法实现。
[解决办法]
我有一个不成熟的想法：就是除了我们老祖宗留下来的勾三股四玄五这个勾股定理比例外，其它勾、股、玄的比例都带有根号倍数，也就是没有整数解。因此，我想1000 以内的整数解就是勾三股四玄五的相似三角形。如果不是单求整数解，基于相似三角形的原理，那应该是无限的
- C/C++ code
#include <stdio.h>int main(){ for(int i = 1; i <= 200; ++i)//1000以内（包括1000），因此i的最大值是1000 / 5，也就是200 { printf("%d, %d, %d\n", 3 * i, 4 * i, 5 * i); } return 0;}
[解决办法]
[解决办法]
[解决办法]
a + b > c
a*a + b*b = c*c
c > a, c > b
a,b,c 为整数
这个范围就缩小了不少
[解决办法]
[解决办法]
- C/C++ code
#include "stdafx.h"#include <math.h>int _tmain(int argc, _TCHAR* argv[]){ int k1,k2; int sum=0; for(int i=1;i<708;i++)//708*1.414>1000 { for(int j=(i+1)*1.414;j<1000;j++)//j为斜边.k2和i为直角边 j=(i+1)*1.414保证k2>i { k1=(j+i)*(j-i); k2=(int)sqrt((double)k1); if(k1==k2*k2) { printf("%d^2 = %d^2 + %d^2\n", j, i, k2); sum++; } } } printf("%d\n",sum); getchar(); return 0;}
[解决办法]
[解决办法]
- C/C++ code
#include <stdio.h>int main() { static int bitmap[10000001]={0}; for (int i=0; i<=1001; i++) bitmap[i*i] = i; for (int a=1,c; a<=1000; a++) for (int b=a+1; b<=1000; b++) if (c=bitmap[a*a + b*b]) printf("%d^2 + %d^2 = %d^2\n", a, b, c);}
[解决办法]
[解决办法]
[解决办法]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
float min_step = 0.1;
int min_q = 1;
int main()
{
float x,y;
for(float z = min_step; z - 1000.0 < 0.001; z += min_step)
for(float j = min_q;j - 45.0 < 0.001;j += min_q)
{
x = i * sin(j*3.14/180);
y = i * cos(j*3.14/180);
printf("%f, %f, %f\n", x,y, z);
}
return 0;
}
注解：
linux下的编译命令为 gcc -o test test.c -std=c99 -lm，测试已经通过
window下直接编译就可以了吧，我没有测试，没有环境
原理：sin(Q)* sin(Q) + cos(Q)*cos(Q) = 1
想要多少有多少！！！！
[解决办法]
[解决办法]
[解决办法]
- C/C++ code
#include "stdafx.h"#include <math.h>const double PI = 3.14159265;int f(double num){ return (num-(int)num)>0.5?(int)num+1:(int)num;}int _tmain(int argc, _TCHAR* argv[]){ int a1, a2=1, b1, b2=1, c, sum=0; for(int i=5;i<1001;i++) { c = i*i; for(int j=1;j<450;j++)//1到45度，变化为0.1度 { a1 = f(i*sin(j*PI/1800)); b1 = f(i*cos(j*PI/1800)); if(a1 && a2 != a1)//这里也不好控制 { a2 = a1; b2 = b1; if(c==a2*a2+b2*b2) { printf("%d^2=%d^2+%d^2\n", i, a2, b2); sum++; } } } } printf("%d\n", sum); return 0;}
[解决办法]
第7章讨论Pythagorean Triples的算法(C++)
[解决办法]
内存越界了也没人提醒一下?
[解决办法]
- C/C++ code
#include <stdio.h>#include <math.h>using namespace std;int main(void){ unsigned a,b,c,r=3,count=0,total=0; for(c=5;c!=1000;++c) for(a=r;a<c*(sqrt(2)/2);++a,++total) { b=sqrt(c*c-a*a); if(a*a+b*b==c*c) printf("%4u %4u %4u\n", a, b, c,++count); r=sqrt(c<<1); } printf("循环%u次 共%u个组合。\n",total,count); getchar(); return 0;}
[解决办法]
勾股定理的数字（特指整数）是有规律的
三个整数，A,B,C，满足C*C = A*A + B*B
A的序列是1,3,5,7,9,11,...
B的序列是B(n) = B(n-1) + 4 * n，其中n表示第几组
C就是B+1
有了上面的这个规律，相信下面这个代码应该是比较高效的了（非空间换时间）：
- C/C++ code
int main(int argc, char* argv[]){ int sq[3]={1,0,1}; for(int n=1; n<25; n++) { cout << sq[0] << ',' << sq[1] << ',' << sq[2] << endl; sq[0] += 2; sq[1] += 4*n; sq[2] = sq[1] + 1; } return 0;}
[解决办法]
LS的规律不对吧
[解决办法]
由：a*a = (c+b)(c-b)得出，只要一个数的平方可以分解成2个同奇或者同偶的因数相乘，那么它就满足勾股定理。
如：5*5= 25*1 --> 5*5=[(25+1)/2]*[(25+1)/2] - [(25-1)/2]*[(25-1)/2]
把所有的数，以及所有的分解都找出来，总数除以2就ok了。
[解决办法]
[解决办法]
[解决办法]
果然，还是selooloo比较细心
[解决办法]
[解决办法]
以任意奇数代入P ，任意偶数代入Q ，即可得到唯一一组勾股数。
X = P＾2 + PQ （X等于P平方加PQ）
Y = Q＾2/ 2 + PQ （Y等于二分之Q方加PQ）
Z = P＾2 + Q＾2 / 2 + PQ （Z等于P平方加二分之Q方加PQ）
void gougudingli()
{
for (int i = 1; i < 25; i+=2)
{
for (int j = 2; j < 25; j+=2)
{
int x = i*i + i*j;
int y = j*j/2 + i*j;
int z = i*i + j*j/2 + i*j;
cout<<x<<" ";
cout<<y<<" ";
cout<<z<<" ";
cout<<endl;
}
}
}
[解决办法]
学习了，帮顶
[解决办法]
- C/C++ code
#include "stdafx.h"const int N = 23;int _tmain(int argc, _TCHAR* argv[]){ int sum = 0; int a, b, c; int m, n; for(int i = 2; i < N; i++) { for(int j = 1; j < i; j++) { m = i * i; n = j * j; a = 2 * i * j; b = m - n; c = m + n; printf("%d^2 + %d^2 = %d^2\n", a, b, c); sum++; } } printf("%d\n",sum); return 0;}/*对于任意自然数m,n如果a=2mn,b=m*m-n*n,c=m*m+n*n那么必然有a*a+b*b=c*c求1000以内的勾股解，有斜边c<1000即m*m+n*n<1000b为自然数，所以n<m所以有m*m<500所以m<23所以对于a的循环控制就是从1到23此方法也会丢失解：当mn都为无理数时，abc也有整数解。比如a=697,b=696,c=985*/
[解决办法]
- C/C++ code
#include<stdio.h>#include <math.h>int main(){ int a,b,n; long x,y,z,d; scanf("%d,%d",&a,&b); n=0; for (x=a;x<=b-2;x++) for (y=x+1;y<=b-1;y++) { d=x*x+y*y; z=sqrt(d); if (z>b) break; if (z*z==d) { n++; printf("%ld^2+%ld^2=%ld^2\n",x,y,z); } } printf("共%d组勾股数",n); }
[解决办法]
881组，#2楼的答案1762是因为忘记做判断，每一组重复计算了。
#4楼，你是怎么算出878组的？纠结中
[解决办法]
菜鸟再提出一个想法
可以考虑和质数的筛法类似的方法
每算出一个勾股数组就把它的倍数先筛掉
如：3, 4, 5 是勾股数组，那么 3n, 4n, 5n 都是勾股数组。
这样可以减少运算次数
[解决办法]
sqrt(1000*1000>>1) = 707;
[解决办法]
好强！学习！
[解决办法]
好强！学习！
[解决办法]
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
const int N = 1000;//(int)sqrt(1000.0) + 1;
int main(int argc, char **argv)
{
std::vector<int> sqrs;
for(int i=0; i<N; i++)
{
sqrs.push_back(i * i);
}
for(int x=1; x<N-1; x++)
{
for(int y=x+1; y<N; y++)
{
int zz = sqrs[x] + sqrs[y];
if(std::binary_search(sqrs.begin(), sqrs.end(), zz))
{
std::cout << "x = " << x
<< ", y= " << y
<< std::endl;
}
}
}
return 0;
}
[解决办法]
[解决办法]
878组
- C/C++ code
#include <iostream>#include <iomanip>#include <string>#include <vector>#include <algorithm>using namespace std;class A{public: int x; int y; int z;};bool myfunction (A i,A j) { if (i.x == j.x && i.y == j.y) return i.z < j.z; if (i.x == j.x ) return i.y < j.y; return i.x < j.x; }bool efunction (A i,A j) { return (i.x == j.x && i.y == j.y && i.z == j.z);}void gougudingli(){ vector<A> va; int count = 0; for (int i = 1; i*i < 1000; i+=2) { for (int j = 2; i*i + j*j/2 + i*j < 1000; j+=2) { int x = i*i + i*j; int y = j*j/2 + i*j; int z = i*i + j*j/2 + i*j; A a; for (int k = 1; k*z < 1000; k++) { A a; a.x = x < y ? k*x : k*y; a.y = x > y ? k*x : k*y; a.z = k * z; if (x*x + y*y == z*z) va.push_back(a); } } } sort (va.begin(), va.end(), myfunction); vector<A>::iterator it; it = unique (va.begin(), va.end(),efunction); va.resize( it - va.begin() ); for (it=va.begin(); it!=va.end(); ++it) { cout << (*it).x <<" "<< (*it).y<< " " <<(*it).z<<endl; } cout<<va.size()<<endl;}int main (int argc,char** args) { gougudingli(); system("pause"); return 0;}
[解决办法]
[解决办法]
给一个伪代码，效率不太高，不过很直白:
- Python code
require 'set'def gougu(limit=10) r=[] return if limit<3 1.upto(limit) do |a| 1.upto(limit) do |b| 1.upto(limit) do |c| next if [a,b,c].uniq.size != 3 r<<Set[a,b,c] if a*a+b*b==c*c end end end r.uniq!end
[解决办法]
[解决办法]