Board logo

标题: [原创代码] 无忧公主编程挑战005 [打印本页]
作者: happy886rr    时间: 2016-4-11 21:40     标题: 无忧公主编程挑战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取哪个值时，边长的整数解最多？

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

　　好吧，既然你要整数，那我就 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只循环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。
作者: codegay    时间: 2016-4-11 22:45

python3自带整除法
x//2
作者: codegay    时间: 2016-4-11 23:38

我说的是int(p/3),int(p/2)
之类的可以写成p//3
p//2
作者: happy886rr    时间: 2016-4-12 00:01

回复 4# codegay
多谢指教，这个//太好了，下次我会让它露脸的，python比批处理生动多了。
作者: codegay    时间: 2016-4-12 00:56

利用max()最取出列表中的最大值，然后index可以找出最大值的位置。
  1. >>> r.index(max(r))

  2. 840
复制代码
作者: happy886rr    时间: 2016-4-12 08:52

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

回复 5# codegay
哇塞，这么好用！！！
  1. print("当p为{0}时，勾股解数最多。".format(r.index(max(r))))
复制代码
作者: codegay    时间: 2016-4-12 11:24

回复 6# happy886rr


    类似 C风格的字符串格式化
  1. print("当p为%s时，勾股解数最多。" % r.index(max(r)))
复制代码




欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2