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

happy886rr

　　无忧公主又出新题目了，今天瞟了一眼她的第五个编程挑战题目，这不是欧拉计划的第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代码，可视性很强啊！

# Python 解无忧公主编程挑战005
# 设p为Rt△周长，在1000的取值范围内，当p为多少时，勾股数解最多？
r=[0]*1000;N=0
for p in range(1,1000):
	for b in range(1,int(p/2)):
		for a in range(1,b):
			if a*a+b*b==(p-a-b)*(p-a-b):
				r.insert(p,r[p]+1)
				print("周长",p,"勾股数组：",a,b,p-a-b)
for p in range(1,1000):
	if r[p]>N:
		N=r[p];P=p
print("当p为{0}时，勾股解数最多。".format(P))
复制代码

　　　python能做的计算，批处理也能做，只是效率问题，不管它了，能用就行。我相信在计算方面批处理是万能的，常规运算都能模拟，大不了分割数组，高精度迭代，级数展开。

@echo off&setlocal enabledelayedexpansion
for /l %%p in (5 1 1000) do (
	set n=0
	for /l %%i in (5 1 %%p) do (
		set/a r=%%i*%%i+2*%%p*%%i-%%p*%%p
		set/a y=14*%%i/10+1
		for /l %%j in (1 1 !y!) do (
			set/a y2=%%j*%%j
			if "!y2!"=="!r!" (
				set/a m=%%p-%%i+%%j,l=(%%p-%%i-%%j^)/2,s=m/2,rs=m%%2
				if !rs! equ 0 (
					if !l! gtr 0 (
						set/a n+=1
					)
				)
			)
		)
	)
	if !n! gtr !mark! (set mark=!n!&set p=%%p)
)
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啊。

# Python 解无忧公主编程挑战005
N=0
for p in range(0,1000):
	n=0
	for c in range(int(p/3),int(p/2)):
		delta=c*c+2*p*c-p*p
		if delta>0:
			m=p-c-delta**0.5
			if m==int(m):
				n+=1
	if n>N:
		N,P=(n,p)
print(P)
复制代码

　　补充：知道奇数＋奇数＝偶数，奇数＋偶数＝奇数，那么你就知道当ｐ为奇数时，三边长是没有整数解的，所以p只循环0到1000的偶数，再次，二次方程有解的条件是判别式c*c+2*p*c-p*p>=0可推出c>(sqrt(2)-1)*p,所以从此处开始循环最佳。改进的代码：

N=0
for p in range(0,1000,2):
	n=0
	for c in range(int((2**0.5-1)*p+1),int(p/2)):
		s=(c*c+2*p*c-p*p)**0.5
		if s==int(s):
			n+=1
	if n>N:
		N,P=(n,p)
print(P)
复制代码

　　用时0.08秒，运行结果840。

codegay

回复 6# happy886rr


    类似 C风格的字符串格式化

print("当p为%s时，勾股解数最多。" % r.index(max(r)))
复制代码

happy886rr

回复 5# codegay
哇塞，这么好用！！！

print("当p为{0}时，勾股解数最多。".format(r.index(max(r))))
复制代码

codegay

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

>>> r.index(max(r))
840
复制代码

happy886rr

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

codegay

我说的是int(p/3),int(p/2)
之类的可以写成p//3
p//2

codegay

python3自带整除法
x//2