鱼C论坛

 找回密码
 立即注册
查看: 6118|回复: 26

[技术交流] 小练习:20160411 找出唯一的满足a + b + c = 1000的毕达哥拉斯三元组{a, b, c}

[复制链接]
发表于 2016-4-11 08:45:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2016-4-18 20:19 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。
什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives
这里已经有了500余题,并且你每做对一题,就可以下载到参考答案的pdf文件,看看你的实现方法与参考答案有什么不同,以利于迅速提高自己的水平。


                               
登录/注册后可看大图

好了言归正传,我们开始做小练习。




题目要求:
以python语言完成,如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单,注重程序效率和创意。
答题在4.18 10:00前完成,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。


题目:

一个毕达哥拉斯三元组是一个包含三个自然数的集合,a < b < c,满足条件:


                               
登录/注册后可看大图


例如:


                               
登录/注册后可看大图


已知存在并且只存在一个毕达哥拉斯三元组满足条件 a + b + c = 1000。

找出该三元组中 abc 的乘积。



提示:如果采用循环一个个试,注意a和b的取值范围,这样可以减少计算量。

奖励:
对所有完成程序并得出正确答案的将给予加分奖励,优秀的将额外加分。
在完成一批题目后,将根据每期的完成情况总评评出最佳,会有神秘大奖。

评分

参与人数 2荣誉 +10 鱼币 +10 贡献 +8 收起 理由
wangguohui + 5 + 5 + 3 支持楼主!
~风介~ + 5 + 5 + 5 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-4-11 11:06:20 | 显示全部楼层
本帖最后由 老忘 于 2016-4-11 11:12 编辑

思路:
一、达到三个条件,就计算三数乘积结果
1、a+b+c=1000
2、a^2+b^2=c^2
3、c>b>a>0(abc 为自然数)
二、条件化简:
    1、针对已知条件1,2,可通过a + b + c = 1000得出a^2+b^2+c^2+2ab+2ac+2bc=1000000,把a^2+b^2=c^2和a=1000-c-b代入后化简,得出公式(1000-b)*(b+c)=500000
    2、由b>a 和a+b+c=1000,推导出b>500-c/2
    3、由a>0和a+b+c=1000,推导出1000-b-c>0

(感悟:学好数学非常重要啊!直接用条件一个个试,与化简减少次数后试,效率完全不同)

  1. flag=0
  2. for c in range(1000,2,-1):
  3.     if flag==0:
  4.         for b in range(499-int(c%2),1,-1):
  5.             if flag==0:
  6.                if (1000-b)*(b+c)==500000 and 1000-c-b>0:
  7.                    print(str(c*b*(1000-c-b)))
  8.                    flag=1
  9.                    break
  10.             else:break
  11.     else:break
复制代码

评分

参与人数 2荣誉 +6 鱼币 +6 收起 理由
zooo + 1 + 1 消元法果然很有效。。
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 13:42:52 | 显示全部楼层
  1. '''a<b<c 所以a的最大值为332 b的最大值为498'''
  2. temp = 0

  3. for a in range(332,2,-1):
  4.     for b in range(498,a,-1):
  5.         c = 1000 - a - b
  6.         '''构成三角形的条件'''
  7.         if a + b < c:
  8.             continue
  9.         elif b > c:
  10.             continue
  11.         elif a ** 2 + b ** 2 == c ** 2:
  12.             temp = 1
  13.             print(a,b,c)
  14.             print(a*b*c)
  15.             break
  16.     if temp == 1:
  17.         break
  18.             
  19.    
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 13:43:53 | 显示全部楼层
本帖最后由 kyjsqd222 于 2016-4-11 13:46 编辑

第一次发帖,用的最原始的方法。(大学时候学的数据结构和算法都忘了
结果是:31875000
  1. for a in range(1,1000):
  2.     for b in range(1,1000):
  3.         
  4.         if (a<=b)&(a*a+b*b==(1000-a-b)*(1000-a-b)):
  5.             c=1000-a-b
  6.             print("%d "%(a*b*c))
  7.             continue
  8.         else :
  9.             continue
  10.     continue
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 16:54:52 | 显示全部楼层
a,b,c分别是200 375 425
乘积是31875000

  1. #明显是直角三角形,由三角形的性质可知a+b>c,所以a+b>500且三个数都小于500
  2. #同时依然通过以上性质,不妨设a<b,计算得知a属于[2,251],b属于[251,499]
  3. for a in range(2,252):
  4.     for b in range(251,500):
  5.         if a+b>500:
  6.             if a**2 + b**2 == (1000-a-b)**2:
  7.                 result = a*b*(1000-a-b)
  8.                 print('a,b,c分别是%d %d %d'%(a,b,1000-a-b))
  9.                 print('乘积是%d'%result)
  10.                 break
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 19:27:57 | 显示全部楼层
flag=0
#i最小不可能大于334
for i in range(334,1,-1):
    if(flag==0):
        #三角形定则确定j的取值范围小于2000/3-i
        for j in range(i,int(2000/3)-i):
            if((i**2+j**2)==(1000-i-j)**2 and (1000-i-j)>0):
                print(i,j,(1000-i-j))
                flag=1
                break


评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 19:52:02 | 显示全部楼层
  1. for a in range(500):
  2.     for b in range(a,500):
  3.         for c in range(b,500):            
  4.             if(a<b<c and a+b+c==1000 and a**2+b**2==c**2):
  5.                 print(a,b,c)
  6.                 print(a*b*c)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 22:19:35 | 显示全部楼层
本帖最后由 挥舞乾坤 于 2016-4-11 22:22 编辑
  1. print([a*b*c for a in range(500) for b in range(a,500) for c in (1000-a-b,) if a*a + b*b == c*c][0])
复制代码


ps:对于我这样的学渣来说,真是痛苦,每期都要恶补一下数学,不过想到以后教儿子能用的到,也就没那么痛了.

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 22:24:11 | 显示全部楼层
  1. a=int(1000//(2+2**0.5))
  2. for i in range(1,a+1):
  3.     for j in range(a,1000//2):
  4.         k=1000-i-j
  5.         if i*i+j*j==k*k :
  6.                 print(i,j,k)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-11 23:42:36 | 显示全部楼层
这个题目数学成分比编程技术更多一些:
  1. a = [a for a in range(1,334) if int(1000*(a-500)/(a-1000))==1000*(a-500)/(a-1000)][0]
  2. b = int(1000*(a-500)/(a-1000))
  3. print('这一组毕达哥拉斯三元组是:%d,%d,%d,乘积为:%d'%(a,b,1000-a-b,a*b*(1000-a-b)))
复制代码

结果是:
  1. 这一组毕达哥拉斯三元组是:200,375,425,乘积为:31875000
复制代码

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-12 09:01:32 | 显示全部楼层
  1. for a in range(1,500):
  2.     for b in range(a,500):
  3.         c=1000-a-b
  4.         if a**2+b**2==c**2:
  5.             squ=a*b*c
  6.             print("a=%d,b=%d,c=%d" % (a,b,c))
  7.             print("abc的乘积是:%d" % squ)
  8.             break
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-12 11:57:43 | 显示全部楼层
  1. def triangle(summ=1000):
  2.     import math as m
  3.     for c in range(int(summ*m.sqrt(2)/(m.sqrt(2)+2)),summ//2+1):
  4.         a=(summ-c-1)
  5.         b=1
  6.         if a**2+b**2==c**2:
  7.             print(a,b,c)
  8.             return a*b*c
  9.         else:
  10.             while a>=b:
  11.                 a-=1
  12.                 b+=1
  13.                 if a**2+b**2<=c**2:
  14.                     if a**2+b**2==c**2:
  15.                         print(a,b,c)
  16.                         return a*b*c
  17.                     else:
  18.                         break
  19.                
复制代码

答案
375 200 425
31875000

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-12 12:32:18 | 显示全部楼层
  1. for a in range(1, 333):
  2.     for c in range(334, 500):
  3.         b = 1000 - a - c        
  4.         if (b>a) and (b<c) and ((a**2 + b**2) == c**2) :
  5.             print('%s\t%d\t%d\t%d\t%d' %('a,b,c,abc:',a,b,c,a*b*c))
  6.             break;
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-12 14:07:10 | 显示全部楼层
  1. for a in range(500):
  2.     for b in range(a,500):
  3.         if a*a+b*b==(1000-a-b)**2:
  4.             c=1000-a-b
  5.             print('a='+str(a),'b='+str(b),'c='+str(c))
  6.             print('三元组abc的乘积为',a*b*c)
复制代码


结果
  1. a=200 b=375 c=425
  2. 三元组abc的乘积为 31875000
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-12 16:13:47 | 显示全部楼层
本帖最后由 mather 于 2016-4-12 17:17 编辑

算法一:纯用生成器的思路,这个效率不高,用时大约27s,回头再修改看看!!    ps:filter真是太强大了(这绝对是吹牛逼~)
  1. import time
  2. ## 使用生成器,生成所有a<b<c的(a,b,c)的元组
  3. def _genabc():
  4.     for a in range(1,1001):
  5.         for b in range(a+1,1001):
  6.             for c in range(b+1,1001):
  7.                 yield(a,b,c)

  8. i = 0
  9. abc = _genabc()
  10. ##筛选a+b+c==1000的元组
  11. abc = filter(lambda x:sum(x)==1000,abc)
  12. ##选出对的元组
  13. abc = filter(lambda x:x[0]**2+x[1]**2==x[2]**2,abc)

  14. timeon=time.clock()
  15. ans=next(abc)
  16. print('a=%d,b=%d,c=%d'ans)
  17. print('三个数的乘积是:',str(ans[0]*ans[1]*ans[2]))

  18. timeoff=time.clock()
  19. print('总用时:',str(timeoff-timeon))
复制代码

算法2:额不用yield的生成器,感觉快多了,不过还是要7s
  1. import time
  2. ## 使用生成器
  3. abc = ((a,b,c) for a in range(1,1001) for b in range(a+1,1001) for c in range(b+1,1001) if a+b+c==1000 and a**2+b**2==c**2)
  4. ##选出对的元组
  5. timeon=time.clock()
  6. ans = next(abc)
  7. timeoff=time.clock()
  8. print(ans)
  9. print(ans[0]*ans[1]*ans[2])
  10. print('总用时:',str(timeoff-timeon))
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-13 18:02:38 | 显示全部楼层
答案是200, 375, 425,代码如下:
import math
def Pythagoras():
    for i in range(1, 250): # 定义第一个数的取值范围
        for k in range(1, 500): # 定义第二个数的取值范围
            if i + k + math.sqrt(i**2 + k**2) == 1000:  # 在各自的取值范围内循环
                b = i
                c = k
                d = math.sqrt(i**2 + k**2)
                print("毕达格拉斯三元数组为:%d, %d, %d" % (b, c, d))
Pythagoras()

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-13 19:39:46 | 显示全部楼层
没有学过pyton,用刚学的java试了一下

public class ss {

        public static void main(String[] args) {
                int a,b,c;
                for(c=1;c<=1000;c++){
                        for(b=1;b<c;b++){
                                for(a=1;a<b;a++){
                                        if(a*a+b*b==c*c){
                                                if(a+b+c==1000){
                                                        System.out.print(a+","+b+","+c);
                                                }
                                        }
                                }
                        }
                }
        }

}

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
冬雪雪冬 + 3 + 3 虽然不是python编写的,也鼓励一下

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-14 08:31:19 | 显示全部楼层
  1. import time
  2. def abc():
  3.     for a in range(1000):
  4.         for b in range(a + 1, 1000):
  5.             c = 1000 - a - b
  6.             if a < b < c:
  7.                 if a ** 2 + b ** 2 == c ** 2:
  8.                     return (a, b, c)
  9.                 pass
  10.             elif c <= b:
  11.                 break
  12.     return (0, 0, 0)

  13. t1 = time.clock()
  14. a, b, c = abc()
  15. print(a, b, c)
  16. print(a ** 2, b ** 2, c ** 2)
  17. print(time.clock() - t1)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-14 10:02:52 | 显示全部楼层
  1. for a in range(1,333):
  2.     for b in range (1,500):
  3.         c=1000-a-b
  4.         if (a**2+b**2)== c**2 :
  5.             print (a,b,c,a*b*c)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-14 23:07:33 | 显示全部楼层

  1. for i in range(1,400):
  2.     for j in range(1,i+1):
  3.             if (1000-i-j)**2 == i**2 + j**2:
  4.                 print((1000-i-j)*j*i)
  5.                 break
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-30 00:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表