唯一整数直角三角形问题

唯一整数直角三角形问题唯一整数直角三角形问题/NUMPAGES8唯一整数直角三角形问题唯一整数直角三角形问题课程设计——数学实验与数学软件设计题目：直角三角形问题指导老师：侯为根学生姓名：孙文莉班级：信122班学号：1290842272014年6月16日重述问题：题目14：找出只能以一种方式构成直角三角形的电线长度的数目.事实证明12cm是最短的只能够以一种方式弯曲成整数边直角三角形的电线长度。但是还有很多其他例子：12cm:(3,4,5)

24cm:(6,8,10)

30cm:(5,12,13)

36cm:(9,12,15)

40cm:(8,15,17)

48cm:(12,16,20)与之相反，有一些长度，例如20cm，不能够弯曲形成整数边的直角三角形。而其他的一些长度则可以以多于一种的方式弯曲成整数边直角三角形；例如，120cm可以构成三种不同的整数边直角三角形。120cm:(30,40,50),(20,48,52),(24,45,51)L为电线的长度，对于L1,500,000，有多少个只能以一种方式构成整数边直角三角形？问题分析：在此题中要求用数值分析法来求解唯一整数边直角三角形问题，而对直角三角形这个问题我们早已不再陌生，直角形三边的勾股定理和三边关系我们再熟悉不过，可以建立数学模型列出相关运算式用数学软件MATLAB来解决这个问题模型建立与求解：目前为止，想到最快的计算方法还是利用勾股数的构造公式a=m^2-n^2b=2*m*nc=m^2+n^2,则a,b,c满足勾股定理.要用上边公式产生所有的勾股数，还要注意几个条件1、m>n，m和n都是正整数2、三边和，也就是周长为2*m*(m+n)3、当m和n互质且奇偶不同时，可以产生互质的勾股数4、假如得到一个勾股组合a，b，c，那么ka，kb，kc（k为正整数）也是勾股数周长显然也是原来的k倍所以程序的基本算法是首先设置一个数组x用于存放每个周长值可以用几种勾股数去表示然后利用勾股数的构造公式，构造互质勾股数组，并计算周长将x数组这个周长和周长的整数倍对应的位置的数增加1由于周长为L=2*m*(m+n)>2m^2,所以只用计算到m<sqrt(L/2)就可以了最后x(i)中为0的值表示周长为2*i的情况不能构造成整数边直角三角形而x(i)中为1的值表示周长为2*i的情况有一种办法构造成整数边直角三角形只要统计x中等于1的数的个数，就得到只能以一种方式构成整数边直角三角形的周长个数程序编写：clearticL=1.5e6;%最大三角形周长x=zeros(1,L/2,'uint8');%x用于存放每个周长可以以几种方式构成整数直角三角形%由于勾股数的和一定是偶数，所以这里只用L/2的长度%x有第i个数，表示周长为2i的三角形可以有几种构成整数边直角三角形的办法form=2:sqrt(L/2)f=unique(factor(m));k=1:m-1;forl=f,k(l:l:end)=0;endiff(1)~=2,k(1:2:end)=0;endk=k(k>0);%最后k是奇偶和m不同，且与m互质的小于m的数forn=k%从k中取出一个值赋给nhs=m*(m+n);%2*hs就是周长if2*hs>L;break;end%周长超过L，不用考虑x(hs:hs:end)=x(hs:hs:end)+1;%将这组勾股数三角形周长及其整数倍的构造办法增加1endendnum=sum(x==1)%统计只有一种构造办法的个数toc计算结果与分析：num=161667Elapsedtimeis3.519709seconds.所以，L为电线的长度，对于L1,500,000，有161667个只能以一种方式构成整数边直角三角形，且以上方法用时3.5秒左右方法二，用遍历法，L=1:1,500,000,用勾股定理遍历所有数，时间复杂度非常大，需要耗时一个小时左右，以下是其程序n=0;f=0;a=0;b=0;forL=6:2:1500000i=a+1;fora=1:ii=L-a;c=b+1;forb=1:cc=L-a-b;if(a*a+b*b==c*c&&a>b)n=n+1;f=1;fprintf('%d+%d+%d=%d\n',a,b,c,L)if(f)breakendend