C语言 找出其中 a + b + c = 1000 的勾股三元组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2817848/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find Pythagorean triplet for which a + b + c = 1000
提问by Rahul
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2+ b2= c2
毕达哥拉斯三元组是一组三个自然数，a < b < c，对于其中，a 2+ b 2= c 2
For example, 32+ 42= 9 + 16 = 25 = 52.
例如， 3 2+ 4 2= 9 + 16 = 25 = 5 2。
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
恰好存在一个毕达哥拉斯三元组，其中 a + b + c = 1000。求积 abc。
Source: http://projecteuler.net/index.php?section=problems&id=9
来源：http: //projecteuler.net/index.php?section=problems&id=9
I tried but didn't know where my code went wrong. Here's my code in C:
我试过了，但不知道我的代码哪里出错了。这是我在 C 中的代码：
#include <math.h>
#include <stdio.h>
#include <conio.h>
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();
}
回答by Paul Stephenson
I'm afraid ^doesn't do what you think it does in C. Your best bet is to use a*afor integer squares.
恐怕^不会做你认为它在 C 中所做的事情。你最好的选择是使用a*a整数平方。
回答by Oleg Razgulyaev
#include <math.h>
#include <stdio.h>
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;
}
explanation:
解释：
- b = a;
if a, b (a <= b) and c are the Pythagorean triplet,
then b, a (b >= a) and c - also the solution, so we can search only one case - c = 1000 - a - b; It's one of the conditions of the problem (we don't need to scan all possible 'c': just calculate it)
- b = a;
如果 a, b (a <= b) 和 c 是勾股三元组，
那么 b, a (b >= a) 和 c - 也是解，所以我们只能搜索一种情况 - c = 1000 - a - b; 这是问题的条件之一（我们不需要扫描所有可能的'c'：只需计算它）
回答by do_the_math
Here's a solution using Euclid's formula (link).
这是使用欧几里得公式的解决方案（链接）。
Let's do some math: In general, every solution will have the form
让我们做一些数学计算：一般来说，每个解决方案都会有以下形式
a=k(x2-y2)
b=2kxy
c=k(x2+y2)
where k, x and y are positive integers, y < x and gcd(x,y)=1 (We will ignore this condition, which will lead to additional solutions. Those can be discarded afterwards)
其中 k、x 和 y 是正整数，y < x 和 gcd(x,y)=1（我们将忽略这个条件，这将导致额外的解决方案。这些可以在之后丢弃）
Now, a+b+c= kx2-ky2+2kxy+kx2+ky2=2kx2+2kxy = 2kx(x+y) = 1000
现在，a+b+c= kx2-ky2+2kxy+kx2+ky2=2kx2+2kxy = 2kx(x+y) = 1000
Divide by 2: kx(x+y) = 500
除以 2：kx(x+y) = 500
Now we set s=x+y: kxs = 500
现在我们设置 s=x+y：kxs = 500
Now we are looking for solutions of kxs=500, where k, x and s are integers and x < s < 2x.
Since all of them divide 500, they can only take the values 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Some pseudocode to do this for arbitrary n (it and can be done by hand easily for n=1000)
现在我们正在寻找 kxs=500 的解，其中 k、x 和 s 是整数和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=s-x
k=((n/2)/x)/s
add (k*(x*x-y*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
You can still improve this:
您仍然可以改进这一点：
- x will never be bigger than the root of n/2
- the loop for s can start at x and stop after 2x has been passed (if the list is ordered)
- x 永远不会大于 n/2 的根
- s 的循环可以从 x 开始并在经过 2x 后停止（如果列表是有序的）
For n = 1000, the program has to check six values for x and depending on the details of implementation up to one value for y. This will terminate before you release the button.
对于 n = 1000，程序必须检查 x 的六个值，并根据实现的细节检查最多 y 的一个值。这将在您松开按钮之前终止。
回答by Dogbert
As mentioned above, ^ is bitwise xor, not power.
如上所述，^ 是按位异或，而不是幂。
You can also remove the third loop, and instead use
c = 1000-a-b;and optimize this a little.
您还可以删除第三个循环，而是使用
c = 1000-a-b;并稍微优化一下。
Pseudocode
伪代码
for a in 1..1000
for b in a+1..1000
c=1000-a-b
print a, b, c if a*a+b*b=c*c
回答by dgg32
There is a quite dirty but quick solution to this problem. Given the two equations
这个问题有一个非常脏但快速的解决方案。给定两个方程
a*a + b*b = c*c
a*a + b*b = c*c
a+b+c = 1000.
a+b+c = 1000。
You can deduce the following relation
可以推导出以下关系
a = (1000*1000-2000*b)/(2000-2b)
a = (1000*1000-2000*b)/(2000-2b)
or after two simple math transformations, you get:
或经过两次简单的数学转换，您将得到：
a = 1000*(500-b) / (1000 - b)
a = 1000*(500-b) / (1000 - b)
since a must be an natural number. Hence you can:
因为 a 必须是自然数。因此，您可以：
for b in range(1, 500):
if 1000*(500-b) % (1000-b) == 0:
print b, 1000*(500-b) / (1000-b)
Got result 200 and 375.
得到结果 200 和 375。
Good luck
祝你好运
回答by fortran
From man pow:
来自man pow：
POW(3) Linux Programmer's Manual POW(3)
NAME
pow, powf, powl - power functions
SYNOPSIS
#include <math.h>
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,
as you see, powis using floating point arithmetic, which is unlikely to give you the exact result (although in this case should be OK, as relatively small integers have an exact representation; but don't rely on that for general cases)... use n*nto square the numbers in integer arithmetic (also, in modern CPU's with powerful floating point units the throughput can be even higher in floating point, but converting from integer to floating point has a very high cost in number of CPU cycles, so if you're dealing with integers, try to stick to integer arithmetic).
如您所见，pow正在使用浮点运算，这不太可能为您提供确切的结果（尽管在这种情况下应该没问题，因为相对较小的整数具有精确的表示；但在一般情况下不要依赖它）。 . 用于n*n在整数运算中对数字进行平方（此外，在具有强大浮点单元的现代 CPU 中，浮点的吞吐量可能更高，但从整数转换为浮点在 CPU 周期数方面的成本非常高，因此如果您正在处理整数，请尝试使用整数算术）。
some pseudocode to help you optimise a little bit your algorithm:
一些伪代码可以帮助您优化算法：
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
回答by IVlad
#include <stdio.h>
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;
}
Haven't tested this, but it should set you on the right track.
尚未对此进行测试，但它应该使您走上正确的轨道。
回答by swegi
In C the ^ operator computes bitwise xor, not the power. Use x*xinstead.
在 C 中，^ 运算符计算按位异或，而不是幂。使用x*x来代替。
回答by Kendall Hopkins
While as many people have pointed out that your code will work fine once you switch to using pow. If your interested in learning a bit of math theory as it applies to CS, I would recommend trying to implementing a more effient version using "Euclid's formula" for generating Pythagorean triples (link).
虽然许多人指出，一旦您切换到使用pow. 如果您有兴趣学习一些适用于 CS 的数学理论，我建议您尝试使用“欧几里得公式”来实现一个更有效的版本来生成勾股数（链接）。
回答by Elemental
As others have mentioned you need to understand the ^ operator. Also your algorithm will produce multiple equivalent answers with the parameters a,b and c in different orders.
正如其他人所提到的，您需要了解 ^ 运算符。此外，您的算法将以不同的顺序使用参数 a、b 和 c 生成多个等效答案。
