经典算法题

moe

2年前

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

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

本帖最后由 ShadowSaint 于 2022-6-26 00:17 编辑

你这个算法的时间复杂度应该是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 于 2022-6-25 23:44 编辑

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

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

穷举法,极限也就那样

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

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

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

算个P法，暴力强算

ShadowSaint 发表于 2022-6-26 00:02
你这个算法的时间复杂度应该是O(nlogn)嘛，应该能优化到O(n)的
我的理解啊：

感谢大佬，明天我来实现