我刚刚完成了欧拉计划第9题(警告剧透):
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.
我的解决方案是:
public static int specPyth(int num)
{
for (int a = 1; a < num; a++)
for (int b = 2; b < a; b++)
{
if (a*a +b*b == (num-a-b)*(num-a-b))
return a*b*(num-a-b); //ans = 31875000
}
return -1;
}
我不禁想到,有一个解决方案只涉及一个循环。有人有想法吗?我更喜欢答案只使用一个循环,但任何比我目前更有效的将是很好的。
9条答案
按热度按时间9rnv2umw1#
那么
然后你尝试每一个B,直到你找到一个使a成为自然数的b。
编辑:B不能大于499,因为c〉b,(b+c)就会大于1000。
x9ybnkn62#
我强烈推荐阅读http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple并编写一个函数,它将逐个生成勾股三元组。
不是给予太多的剧透,但有一些其他的PE问题,这个函数将派上用场。
(我并不认为这是一种过度的放弃,因为体育课的部分目的就是鼓励人们学习这类知识。)
hmtdttj43#
首先,因为a是最小的,所以不需要将其计数到num,num/3就足够了,甚至num/(2+sqrt(2))也足够了。
我们可以解这个方程,找到B和c,对于给定的a,它们已经满足这个方程,不需要像现在这样检查a^2+b^2=c^2,你需要做的就是检查b和c是否是整数,这是在一个循环中完成的
kfgdxczn4#
运行时间为62毫秒
wwwo4jvm5#
C溶液
警告:解答假设GCD(a,B)= 1。它在这里工作,但可能不总是工作。我会在一段时间内修复的解决方案。
解答使用欧几里得的三元组公式,该公式指出任何本原三元组的形式为a = r^2 - s^2,B = 2 rs,c = r^2 + s^2。
基于s为正且r〉s的事实,可以添加某些限制,如sqrt(n / 2)〈= r〈= sqrt(n)。
警告:如果产品较大,您可能需要long long
ttygqcqt6#
这肯定不是最佳的解决方案,但我的第一React是使用修改后的3SUM。
ki1q1bka7#
假设
a < b < c
,那么b
一定总是大于a
,所以第二个循环的起点可能是b = a + 1
;这肯定会导致更少的迭代。kmynzznz8#
在第一个方程中,你有三个变量
a, b, c
。如果你想找到这个方程的匹配值,你必须运行三维循环。幸运的是,还有另一个方程a+b+c=N
,其中N
是已知数。如果你知道三个维度中的两个,你就可以计算出剩下的维度,例如,如果你知道
a
和b
,c
等于N - a - b
。如果你能再减少一个维度呢?如果你摆弄两个给定的方程,这是可能的。拿一支笔和一张纸。一旦你得到了两个变量和一个常数的附加方程(N)、您将能够获取
O(n)
中的结果。以n
和a
为常数,求解两个方程a+b+c=n; a^2+b^2=c^2
,并求解b
和c
:pcww981p9#
巨蟒:
在开始编写代码之前,先做一个简单的代数练习。
a^2 + b^2 = c^2
a + b + c = 1000--〉c = 1000-(a + b)
a^2 + b^2 =(1000-(a + b))^2
a = 1000 *(500-b)/(1000-b)
现在是编写代码的时候了。