经典算法题-251768938

如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?

大佬们有更优的算法吗？
发代码被拦截了，所以截图，大佬们要想复制可以到
https://www.vrt.app/246.html

热议
推荐楼 ShadowSaint 11小时前

你这个算法的时间复杂度应该是O(nlogn)嘛，应该能优化到O(n)的
我的理解啊：

已知：
1、直角三角形
2、三边只和长度为1000

求：
每条边都为正整数的所有解

因为：
直角三角形一条直角边长已知，且周长已知，那么另外两条边有且仅有唯一解
如：
短直角边a
长直角边b
斜边c
当a=1时
b方+a方=c方
b方+1=(1000-1-b)方
b方+1=(1000-1)方 - 2*（1000-1）*b + b方
1=(1000-1)方 - 2*（1000-1）*b
b=((1000-1)方 - 1)/(2*（1000-1) )
等号右边都是已知量，这时候只要b是正整数即为解，并且如果a!=b，一下就求出来两个解，这里500/根号2必不可能是整数，所以不存在等腰直角三角形的情况

所以:
只需要遍历一遍就够了，时间复杂度为O(n)

伪代码：

循环a从1到 500/根号2，每次循环自增1
b = ((1000-a)方 - a方)/ (2*（1000-a) )
if (b为正整数 且 b < 500)
输出 a, b, c = a, b, 1000-a-b
输出 a, b, c = b, a, 1000-a-b

大概就是这样，循环到500/根号2是因为，如果是等腰直角三角形的话边长最多就是500/根号2，再大就没有意义了，之前遍历过这样的情况

没验证，可能有bug哈

推荐楼 xieshang 昨天23:43

直接枚举平方数会不会要好些？(指先预处理一个平方数库;把a^2当作a1,b^2当作a2,c^2当作a3,a1和a2从平方数中枚,加起来看下是不是平方数,不是或者sqrt(a3)不等于1000-a-b就继续枚)

推荐楼 gdtv 昨天23:37

别和我说什么算法，无脑用for循环穷举就行了

3楼 2CO3 昨天23:40

穷举法,极限也就那样

5楼 lsin 昨天23:47

虽然想不出更好的，但是一看你这个就压根没用到啥算法，建议读读数论

6楼 bugtrap 昨天23:47

能跑就行，能出来结果就行

7楼 HOH 昨天23:48

哪有什么最优，能算出来就行

8楼 asd1314s 昨天23:55

算个P法，暴力强算

10楼 251768938 11小时前

你这个算法的时间复杂度应该是O(nlogn)嘛，应该能优化到O(n)的
我的理解啊：

感谢大佬，明天我来实现

12楼 VPS小白白 8小时前

a+b>c 令c>b>a（之后把算出来所有的满足条件的ab值交换即可得到所有可能性），因此c的值在334到499之间。(1000-c)^2-2ab=c^2 所以ab=5e5-c，如果c为偶数，a和b也为偶数，c为奇数，ab一奇一偶。

13楼 VPS小白白 8小时前

说错了，c应该是334～500。其实我想到一种解法，固定c的值以后，画一条长为c的线段，再画一个以线段两端点为焦点的椭圆，上面的点到焦点距离和为1，再画一个以线段为直径的正圆。通过椭圆和正圆的交点就可以求出a和b的值。

14楼 VPS小白白 8小时前

我用手机打字不方便，应该是 （上面的点到焦点距离和为1000-c），因为这是个解方程题目，应该对于满足范围的每个c都能求出解，但我们只需要自然数解，所以可以不用求精确解，比如牛顿下山法之类的，每个c的求解，复杂度在O(logN)，加上c的范围大概是O(NlogN)

15楼 VPS小白白 8小时前

而且NlogN应该是最坏的情况，精度为1的话牛顿下山法收敛很快的（基础不是很记得牢了），总之这个方法对数学要求较高一些。

16楼 小二的cat 7小时前

啊这。直接abc随便取一个变量，0到1000遍历。比如把c从0到1000遍历，那这不就是求解一元二次方程的根了吗，一次遍历就结束了啊

申明：本文内容由网友收集分享，仅供学习参考使用。如文中内容侵犯到您的利益，请在文章下方留言，本站会第一时间进行处理。