找到毕达哥拉斯三元组，其中a + b + c = 1000
毕达哥拉斯三元组是一组三个自然数，a <b <c，其中， 2 + b 2 = c 2
例如，3 2 + 4 2 = 9 + 16 = 25 = 5 2 。
恰好存在一个毕达哥拉斯三元组，其中a + b + c = 1000.找到产品abc。
资料来源 ： http ： //projecteuler.net/index.php？section = problem＆id = 9
我试过但不知道我的代码出错了。 这是我在C中的代码：
#include #include #include void main() { int a=0, b=0, c=0; int i; for (a = 0; a<=1000; a++) { for (b = 0; b<=1000; b++) { for (c = 0; c<=1000; c++) { if ((a^(2) + b^(2) == c^(2)) && ((a+b+c) ==1000))) printf("a=%d, b=%d, c=%d",a,b,c); } } } getch(); } #include #include int main() { const int sum = 1000; int a; for (a = 1; a <= sum/3; a++) { int b; for (b = a + 1; b <= sum/2; b++) { int c = sum - a - b; if ( a*a + b*b == c*c ) printf("a=%d, b=%d, c=%d\n",a,b,c); } } return 0; }
说明：
- b = a;
如果a，b（a <= b）和c是毕达哥拉斯三重态，
那么b，a（b> = a）和c - 也是解决方案，所以我们只能搜索一个案例 - c = 1000 - a - b; 这是问题的一个条件（我们不需要扫描所有可能的'c'：只计算它）
我害怕^不会做你认为它在C中做的事情。你最好的选择是使用a*a作为整数方块。
这是使用Euclid公式（ 链接 ）的解决方案。
让我们做一些数学：一般来说，每个解决方案都有表格
a=k(x²-y²) b=2kxy c=k(x²+y²)
其中k，x和y是正整数，y 现在，a + b + c =kx²-ky²+ 2kxy +kx²+ky²=2kx²+ 2kxy = 2kx（x + y）= 1000 除以2：kx（x + y）= 500 现在我们设置s = x + y：kxs = 500 现在我们正在寻找kxs = 500的解，其中k，x和s是整数， 你仍然可以改善这个： 对于n = 1000，程序必须检查x的六个值，并根据实现的细节，最多为y的一个值。 这将在您释放按钮之前终止。 x < s < 2x 。 因为它们全部除以500，所以它们只能取值1,2,4,5,10,20,25,50,100,125,250,500。有些伪代码可以为任意n做这个（它可以是手工完成n = 1000）
If n is odd return "no solution" else L = List of divisors of n/2 for x in L for s in L if x< s <2*x and n/2 is divisible by x*s y=sx k=((n/2)/x)/s add (k*(x*xy*y),2*k*x*y,k*(x*x+y*y)) to list of solutions sort the triples in the list of solutions delete solutions appearing twice return list of solutions
如上所述，^是按位xor，而不是幂。
你也可以删除第三个循环，而是使用c = 1000-ab; 并优化这一点。
伪代码
for a in 1..1000 for b in a+1..1000 c=1000-ab print a, b, c if a*a+b*b=c*c
对这个问题有一个非常肮脏但快速的解决方案。 给出了两个方程
a * a + b * b = c * c
a + b + c = 1000。
您可以推断出以下关系
a =（1000 * 1000-2000 * b）/（2000-2b）
或者在两次简单的数学变换之后，你得到：
a = 1000 *（500-b）/（1000 – b）
因为a必须是自然数。 因此你可以：
for b in range(1, 500): if 1000*(500-b) % (1000-b) == 0: print b, 1000*(500-b) / (1000-b)
得到了结果200和375。
祝好运
#include int main() // main always returns int! { int a, b, c; for (a = 0; a<=1000; a++) { for (b = a + 1; b<=1000; b++) // no point starting from 0, otherwise you'll just try the same solution more than once. The condition says a < b < c. { for (c = b + 1; c<=1000; c++) // same, this ensures a < b < c. { if (((a*a + b*b == c*c) && ((a+b+c) ==1000))) // ^ is the bitwise xor operator, use multiplication for squaring printf("a=%d, b=%d, c=%d",a,b,c); } } } return 0; }
没有测试过，但它应该让你走上正轨。
来自man pow ：
POW(3) Linux Programmer's Manual POW(3) NAME pow, powf, powl - power functions SYNOPSIS #include double pow(double x, double y); float powf(float x, float y); long double powl(long double x, long double y); Link with -lm. Feature Test Macro Requirements for glibc (see feature_test_macros(7)): powf(), powl(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99 DESCRIPTION The pow() function returns the value of x raised to the power of y. RETURN VALUE On success, these functions return the value of x to the power of y. If x is a finite value less than 0, and y is a finite non-integer, a domain error occurs, and a NaN is returned. If the result overflows, a range error occurs, and the functions return HUGE_VAL, HUGE_VALF, or HUGE_VALL,
如你所见， pow正在使用浮点运算，这不太可能给你精确的结果（虽然在这种情况下应该没问题，因为相对较小的整数具有精确的表示;但是在一般情况下不依赖于它）。 ..使用n*n对整数运算中的数字求平方（同样，在具有强大浮点单位的现代CPU中，浮点数的吞吐量甚至可以更高，但是从整数到浮点的转换在CPU数量上的成本非常高循环，所以如果你正在处理整数，试着坚持整数运算）。
一些伪代码可以帮助您优化一点算法：
for a from 1 to 998: for b from 1 to 999-a: c = 1000 - a - b if a*a + b*b == c*c: print a, b, c
在C中，^运算符计算按位xor，而不是幂。 请改用x*x 。
正如其他人提到的，你需要理解^运算符。 此外，您的算法将使用不同顺序的参数a，b和c生成多个等效答案。
虽然许多人已经指出，一旦你切换到使用pow ，你的代码将正常工作。 如果您有兴趣学习一些适用于CS的数学理论，我建议尝试使用“Euclid公式”实现一个更有效的版本来生成Pythagorean三元组（ 链接 ）。
我知道这个问题很老了，每个人都在发布带有3个for循环的解决方案，这是不需要的。 我把它解决了O（n）， **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2** **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**
所以，进一步解决问题;
a+b = 1000-c (a+b)^2 = (1000-c)^2
如果我们进一步解决， 我们推导它;
A =（（50000-（1000 * B））/（1000-B））。 我们循环“b”，找到“a”。
一旦我们有“a”和“b”，我们得到“c”。
public long pythagorasTriplet(){ long a = 0, b=0 , c=0; for(long divisor=1; divisor<1000; divisor++){ if( ((500000-(1000*divisor))%(1000-divisor)) ==0){ a = (500000 - (1000*divisor))/(1000-divisor); b = divisor; c = (long)Math.sqrt(a*a + b*b); System.out.println("a is " + a + " b is: " + b + " c is : " + c); break; } } return a*b*c; }
Euclid方法给出周长为m（m + n）= p / 2，其中m> n，边是m ^ 2 + n ^ 2是斜边，腿是2mn和m ^ 2-n ^ 2.thus m（m + n）= 500，快速得到m = 20，n = 5。 边是200,375和425.使用欧几里德解决所有pythorean原始问题。
由于有两个方程（ a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2 ）有三个变量，我们可以通过循环遍历一个变量的所有可能值来在线性时间内解决它，然后我们可以解决另外两个变量恒定时间内的变量。
从第一个公式得到b=1000-ac ，如果用这个替换第二个公式中的b，我们得到c^2 = aˆ2 + (1000-ac)ˆ2 ，这简化为c=(aˆ2 + 500000 - 1000a)/(1000-a) 。
然后我们循环遍历a的所有可能值，用上面的公式求解c和b，如果条件满足，我们找到了我们的三元组。
int n = 1000; for (int a = 1; a < n; a++) { int c = (a*a + 500000 - 1000*a) / (1000 - a); int b = (1000 - a - c); if (b > a && c > b && (a * a + b * b) == c * c) { return a * b * c; } }
我认为这里最好的方法是：
int n = 1000; unsigned long long b =0; unsigned long long c =0; for(int a =1;a
解释：我们将引用N和A常量，因此我们不必使用两个循环。 我们可以这样做，因为c=nab和b = (a^2-(an)^2)/(2(an))我通过求解方程组得到了这些公式：
a+b+c=n ， a^2+b^2=c^2
func maxProd(sum:Int)->Int{ var prod = 0 // var b = 0 var c = 0 let bMin:Int = (sum/4)+1 //b can not be less than sum/4+1 as (a+b) must be greater than c as there will be no triangle if this condition is false and any pythagorus numbers can be represented by a triangle. for b in bMin..c for a valid triangle c = sum - a - b let csquare = Int(pow(Double(a), 2) + pow(Double(b), 2)) if(c*c == csquare){ let newProd = a*b*c if(newProd > prod){ prod = newProd print(a,b,c) } } } } // return prod }
上面的答案足够好但缺少一条重要的信息a + b> c 。 ;）
将向那些提出要求的人提供更多细节。
for a in range(1,334): for b in range(500, a, -1): if a + b < 500: break c = 1000 - a - b if a**2 + b**2 == c**2: print(a,b,c)
从Oleg的答案进一步优化。 一方不能大于另外两方的总和。 所以a + b不能小于500。