Euler Project9 欧拉工程9

寻找和为1000的勾股数之积.

勾股数定义为: 自然数a<b<c且a^2+b^2=c^2.例如3^2+4^2=9+16=25=5^2. 所以3,4,5就是一组勾股数.

存在一组勾股数满足a+b+c=1000.请计算abc之积.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2

For example, 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.

这个题用暴力方法很容易:做个3层循环,现代计算机计算能力如此强大,很快就能有结果.
但是是否有简单办法呢?

分析:
已知a+b+c=1000,令p=1000,
根据 a^2+b^2 = c^2 --(i)
和 c = p-a-b --(ii)
得到 a^2 = (p-a-b)^2-b^2
右边利用平方差公式 a^2 = (p-a)(p-a-2b) = (p-a)^2-2b(p-a)
移项变形得到 p(p-2a) = 2b(p-a) ---(1)
两边除以p(p-a)得到 2b/p + a/(p-a) = 1
因为a,b,p都是自然数,而且p>a,
所以得到 2b<p 和 a<p-a
化简得到 a<p/2 和 b<p/2 ---(2)
那么(1)和(2)就是我们需要的新的迭代终止条件
上代码,matlab的

function result = euler9()
tic;
for a=3:500         % 条件(2),循环从3开始到p/2结束
 if mod(1000*(1000-2*a),2*(1000-a))==0  % 条件1,b = p(p-2a)/2/(p-a),必须整除
  b = 1000*(1000-2*a)/(1000-a)/2;  % 得到b
  result = a*b*(1000-a-b);    % 计算a*b*c,其中c=1000-a-b
  break;         % 跳出循环
 end
end
toc;
end

结果及运行时间

% Elapsed time is 0.000027 seconds.
% ans =
%     31875000