[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

[原创代码] 无忧公主编程挑战005

本帖最后由 happy886rr 于 2016-4-12 10:24 编辑

  无忧公主又出新题目了,今天瞟了一眼她的第五个编程挑战题目,这不是欧拉计划的第39题吗?难道无忧公主喜欢抄袭。算了,谁让她名字好听,这道题就叫无忧公主编程挑战005吧。题目的大概意思是:如果p是一个直角三角形的周长,三角形的三边长{a,b,c}都是整数。当周长p为120时,边长一共有三组整数解:{20,48,52}, {24,45,51}, {30,40,50};在1000以内,当周长p取哪个值时,边长的整数解最多?

  这个问题好神秘,为什么都要整数边长。让我想起了毕达哥拉斯和他的学派,他的一个学生提出三角形的边长可以是无理数时(就是不能用整数或整数的比表示的数),就被毕老师干掉了。这种对整数的疯狂追求,延续了几千年,以至于现在的N多编程问题动不动就要求整数解。

  好吧,既然你要整数,那我就 for循环一个个的把整数往进带,周长p从1开始循环到1000,a、b、c也跟着循环吧,满足a^2+b^2=c^2,那就是一个解,然后我记录下整数解的个数,最后取整数解最多的那个边长就是答案。好歹我还知道三角形两边之和大于第三边,也就是a+b>c,那么a+b+c>c+c,即周长p>2c,又c为斜边,看来两直角边可以只循环到p/2,让电脑轻松点,少循环一半工作量,可能不止一半。于是有了这个python代码,可视性很强啊!
  1. # Python 解无忧公主编程挑战005
  2. # 设p为Rt△周长,在1000的取值范围内,当p为多少时,勾股数解最多?
  3. r=[0]*1000;N=0
  4. for p in range(1,1000):
  5. for b in range(1,int(p/2)):
  6. for a in range(1,b):
  7. if a*a+b*b==(p-a-b)*(p-a-b):
  8. r.insert(p,r[p]+1)
  9. print("周长",p,"勾股数组:",a,b,p-a-b)
  10. for p in range(1,1000):
  11. if r[p]>N:
  12. N=r[p];P=p
  13. print("当p为{0}时,勾股解数最多。".format(P))
复制代码
   python能做的计算,批处理也能做,只是效率问题,不管它了,能用就行。我相信在计算方面批处理是万能的,常规运算都能模拟,大不了分割数组,高精度迭代,级数展开。
  1. @echo off&setlocal enabledelayedexpansion
  2. for /l %%p in (5 1 1000) do (
  3. set n=0
  4. for /l %%i in (5 1 %%p) do (
  5. set/a r=%%i*%%i+2*%%p*%%i-%%p*%%p
  6. set/a y=14*%%i/10+1
  7. for /l %%j in (1 1 !y!) do (
  8. set/a y2=%%j*%%j
  9. if "!y2!"=="!r!" (
  10. set/a m=%%p-%%i+%%j,l=(%%p-%%i-%%j^)/2,s=m/2,rs=m%%2
  11. if !rs! equ 0 (
  12. if !l! gtr 0 (
  13. set/a n+=1
  14. )
  15. )
  16. )
  17. )
  18. )
  19. if !n! gtr !mark! (set mark=!n!&set p=%%p)
  20. )
  21. set/p=!p!
复制代码
  上面的运行都太慢,有没有秒开的。那肯定有,又想起初中的数学太有用了,随即转化为数学语言,不就是说a+b+c=p,a^2+b^2=c^2吗。这太简单了,一看就是韦达定理,两根之和a+b=p-c,平方一减两根之积2ab=(p-c)^2-c^2,闹了半天,两直角边是一元二次方程的两根啊。直接上判别式,△=b^2-4ac,我只要判断△能开方开尽就行,还得靠int。这下省了好大一个for啊,看看还能不能少几次循环,因为c是斜边,a+b+c<c+c+c不解释,直接p<3c,看来可以从p/3处开始循环,好吧,能省则省。精简版解法就出来了,用时不足0.2秒,代码也少写好多。写的少,干得多,不愧是python啊。
  1. # Python 解无忧公主编程挑战005
  2. N=0
  3. for p in range(0,1000):
  4. n=0
  5. for c in range(int(p/3),int(p/2)):
  6. delta=c*c+2*p*c-p*p
  7. if delta>0:
  8. m=p-c-delta**0.5
  9. if m==int(m):
  10. n+=1
  11. if n>N:
  12. N,P=(n,p)
  13. print(P)
复制代码
  补充:知道奇数+奇数=偶数,奇数+偶数=奇数,那么你就知道当p为奇数时,三边长是没有整数解的,所以p只循环0到1000的偶数,再次,二次方程有解的条件是判别式c*c+2*p*c-p*p>=0可推出c>(sqrt(2)-1)*p,所以从此处开始循环最佳。改进的代码:
  1. N=0
  2. for p in range(0,1000,2):
  3. n=0
  4. for c in range(int((2**0.5-1)*p+1),int(p/2)):
  5. s=(c*c+2*p*c-p*p)**0.5
  6. if s==int(s):
  7. n+=1
  8. if n>N:
  9. N,P=(n,p)
  10. print(P)
复制代码
  用时0.08秒,运行结果840。
1

评分人数

回复 6# happy886rr


    类似 C风格的字符串格式化
  1. print("当p为%s时,勾股解数最多。" % r.index(max(r)))
复制代码
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

本帖最后由 happy886rr 于 2016-4-12 10:40 编辑

回复 5# codegay
哇塞,这么好用!!!
  1. print("当p为{0}时,勾股解数最多。".format(r.index(max(r))))
复制代码

TOP

利用max()最取出列表中的最大值,然后index可以找出最大值的位置。
  1. >>> r.index(max(r))
  2. 840
复制代码
1

评分人数

去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

回复 4# codegay
多谢指教,这个//太好了,下次我会让它露脸的,python比批处理生动多了。

TOP

我说的是int(p/3),int(p/2)
之类的可以写成p//3
p//2
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

python3自带整除法
x//2
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

返回列表