唯一整数直角三角形问题.doc

课 程 设 计 ——数学实验与数学软件 设计题目：直角三角形问题 指导老师：侯为根 学生姓名： 孙文莉 班级 ： 信122班 学号 ：129084227 2014年6月16日 重述问题： 题目14：找出只能以一种方式构成直角三角形的电线长度的数目. 事实证明12 cm是最短的只能够以一种方式弯曲成整数边直角三角形的电线长度。但是还有很多其他例子： 12 cm: (3,4,5)24 cm: (6,8,10)30 cm: (5,12,13)36 cm: (9,12,15)40 cm: (8,15,17)48 cm: (12,16,20) 与之相反，有一些长度，例如20cm，不能够弯曲形成整数边的直角三角形。而其他的一些长度则可以以多于一种的方式弯曲成整数边直角三角形；例如，120cm可以构成三种不同的整数边直角三角形。 120 cm: (30,40,50), (20,48,52), (24,45,51) L为电线的长度，对于 L 1,500,000，有多少个只能以一种方式构成整数边直角三角形？ 问题分析： 在此题中要求用数值分析法来求解唯一整数边直角三角形问题，而对直角三角形这个问题我们早已不再陌生，直角形三边的勾股定理和三边关系我们再熟悉不过，可以建立数学模型列出相关运算式用数学软件MATLAB来解决这个问题 模型建立与求解： 目前为止，想到最快的计算方法还是利用 勾股数的构造公式 a=m^2-n^2 b=2*m*n c=m^2+n^2,则a,b,c满足勾股定理. 要用上边公式产生所有的勾股数，还要注意几个条件 1、mn，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,所以只用计算到msqrt(L/2)就可以了 最后x(i)中为0的值表示周长为2*i的情况不能构造成整数边直角三角形 而x(i)中为1的值表示周长为2*i的情况有一种办法构造成整数边直角三角形 ...... 只要统计x中等于1的数的个数，就得到只能以一种方式构成整数边直角三角形的周长个数 程序编写： clear tic L=1.5e6;%最大三角形周长 x=zeros(1,L/2,uint8); %x用于存放每个周长可以以几种方式构成整数直角三角形 %由于勾股数的和一定是偶数，所以这里只用L/2的长度 %x有第i个数，表示周长为2i的三角形可以有几种构成整数边直角三角形的办法 for m=2:sqrt(L/2) f=unique(factor(m)); k=1:m-1; for l=f,k(l:l:end)=0;end if f(1)~=2,k(1:2:end)=0;end k=k(k0);%最后k是奇偶和m不同，且与m互质的小于m的数 for n=k %从k中取出一个值赋给n hs=m*(m+n); %2*hs就是周长 if 2*hsL;break;end %周长超过L，不用考虑 x(hs:hs:end)=x(hs:hs:end)+1; %将这组勾股数三角形周长及其整数倍的构造办法增加1 end end num=sum(x==1) %统计只有一种构造办法的个数 toc 计算结果与分析： num = 161667 Elapsed time is 3.519709 seconds. 所以，L为电线的长度，对于 L 1,500,000，有个只能以一种方式构成整数边直角三角形 方法二，用遍历法，L=1:1,500,000,用勾股定理遍历所有数，时间复杂度非常大，需要耗时一个小时左右，以下是其程序 n=0; f=0; a=0; b=0; for L=6:2:1500000 i=a+1; for a=1:i i=L-a; c=b+1; for b=1:c