数学与程序设计.doc

数学与程序设计 章维铣数学与程序设计数学是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。数学的特点不仅在于概念的抽象性、逻辑的严密性、结论的明确性，还在于它应用的广泛性。数学方法在程序设计中的运用包括两个方面：化简题目和直接解决问题。应用数学方法化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。应用数学方法化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数学模型提供依据。而用数学方法直接解题，其效率更是一般算法所不可及的。下面以具体的问题为例，介绍有关的数学知识和数学方法，体会利用数学方法解决问题时的乐趣。一数论基础1欧几里德转辗相除法 利用gcd(a,b)=gcd(b,a mod b)求a，b的最大公约数：function gcd(a,b:longint):longint;beginif b=0 then gcdd:=aelse gcd:=gcd(b,a mod b);end;思考：如何把上述算法写成迭代形式？2扩展的欧几里德算法 如果gcd(a,b)=d，一定存在整数x和y满足gcd(a,b)=ax+by。求d及满足gcd(a,b)=ax+by的整数对（x，y）的算法如下：function exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 thenbegin exgcd:=a; x:=1; y:=0;endelsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end;end;注释1页：1算法的理论根据：由欧几里德转辗相除法 gcd(a,b)=gcd(b,a mod b)，设整数x、y满足gcd(b,a mod b)=bx+(a mod b)y则ax+by=bx+(a mod b)y =bx+(a-(a div b)*b)y =ay+b(x-(a div b)*)y于是 x=y y=x-(a div b)y思考：1）如何把上述算法写成迭代形式？2）满足gcd(a,b)=ax+by的整数对（x，y）是否是唯一的？3. 求解二元一次不定方程ax+by=c整数解我们的任务是解二元一次不定方程 ax+by=c 其中a,b,c都是整数，所求的解(x,y)也是整数关于方程的可解性，有下面的两个重要的结论：（1）设gcd(a,b)表示整数a,b的最大公约数。方程有解的充分必要条件是gcd(a,b)|c。（记号“x|y”表示x能整除y，即存在整数k，使y=kx）。 （2）如果(x0,y0)是方程的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程的解。下面我们讨论具体求解的方法。为了避免计算中对负数和0的讨论，我们假定a0，b0，并且a=b。假定方程有解，即系数满足：gcd(a,b)|c，这时，c=c/gcd(a,b)一定是个整数。我们先讨论下面的方程： ax+by= gcd(a,b) 根据上述扩展的欧几里德算法，一定存在整数x0和y0满足ax+by =gcd(a,b)。显然，如果(x0,y0)是方程的一组解，则(cx0,cy0)也是方程的一组解，即a(cx0)+b(cy0)=(cf)=c。下面给出求二元一次不定方程ax+by=c一组整数解（x0,y0）的算法：procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);参见扩展的欧几里德算法if c mod d0 thenbegin writeln(no answer); halt;end elsebegin x0:=x*(c div d); y0:=y*(c div d);end;end; 说明：（1）如果a,b中有一个小于0，例如aba0),现c筒装满水，问能否在c筒中量出d升水(a+b+d=cd0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2不是一个筒被倒满就是另一个筒被倒光；3c筒仅起中转作用，而本身容积除了必须足够装下a筒和b筒的全部水外，别无其它限制。 因此，问题的实质是水总是按a筒或b筒的容积倒来倒去，最后量出d升水来。即通过c筒的中转作用，把倒满a筒一次记为a +1次，从 a筒中倒出a升记为a -1次；对b筒同样如此定义。若a筒累计x次，b筒累计y次,使得ax+by=c-d，则c中量出d升水。于是，能否在c筒中量出d升水，取决于方程ax+by=c-d是否存在整数解。参考程序如下: program mw;typenode=array0.1 of longint;vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 then begin exgcd:=a;x:=1;y:=0; end else begin exgcd:=exgcd(b,a mod b,x,y); t:=x;x:=y;y:=t-(a div b)*y end;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d0 thenbegin writeln(no answer); halt;end elsebegin x0:=x*(c div d); y0:=y*(c div d);end;end;procedure fill(var a,b:node);a筒向b筒倒var t:longint;beginif a10 then repeat if a1=0 then fill(c,a) else if b1=b0 then fill(b,c) else fill(a,b); inc(step); writeln(step:5,:,a1:5,b1:5,c1:5); until c1=d else repeat if b1=0 then fill(c,b) else if a1=a0 then fill(a,c) else fill(b,a); inc(step); writeln(step:5,:,a1:5,b1:5,c1:5); until c1=d;end.4素数的快速测试-Miller-Rabbin算法同余 若a mod c=b mod c,称a和b关于模c同余，记作 ab(mod c).伪素数 对正整数n，如果an-11（mod n） ,则称n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是 素数。另一方面，如果一个数不是伪素数，它一定不是素数。计算ab mod c (1) 直接迭代法求ab mod n 根据模算术的基本知识（a*b）mod c=(a mod c)*b) mod c 得到ab mod n的迭代式算法描述如下：function f1(a,b,n:longint): longint; var d,i:longint; begin d:=a; for i:=2 to b do d:=d mod n*a; d:=d mod n; f1:=d; end; （2）加速叠代法求ab mod n把b化为二进制（btbt-1.b1b0）,这样有：b=bt2t+bt-12t-1+b121+b020 （其中bi=0或1）bt2t+bt-12t-1+b121+b020于是 ab mod n=(a ) mod nb020aMod n)*b121Mod n)a=（算法描述：function f2(a,b,n:longint):longint; var d,t:longint; begin d:=1;t:=a; while b0 do begin if t=1 then begin f:=d;exit end ; if b mod 2 =1 then d:=d*t mod n; b:=b div 2; t:=t*t mod n; end; f2:=d end; Miller-Rabbin算法是基于概率论的素数测试算法，对于an-11（mod n），随机选取s个基a,若an-11（mod n）都成立，则n为素数，否则为合数。下面给出的Miller-Rabbin算法采用计算an-1 mod n的函数f2(a,n-1,n),对于随机选取s个基a, f2(a,n-1,n)都等于1，则认为n为素数。Function Miller_Rabbin(n:longint):boolean;Var I,a:longint; Bl:Boolean;function f2(a,b,n:longint):longint; var d,t:longint; begin d:=1;t:=a; while b0 do begin if t=1 then begin f:=d;exit end ; if b mod 2 =1 then d:=d*t mod n; b:=b div 2; t:=t*t mod n; end; f2:=d end; begini:=0;bl:=tuue;while (is) and bl dobeginint(i);a:=random(n-2)+2;if f2(a,n-1,n)1 then bl:=false;end;miller_rabbin:=blend;二 组合数学基础1加法原理与乘法原理11加法原理： 做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn 种不同的方法。 12乘法原理： 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。 13两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。 2排列与组合的概念与计算公式 21排列及计算公式 从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p(n,m)表示. p(n,m)=n(n-1)(n-2)(n-m+1)= n!/(n-m)!(规定0!=1). 22组合及计算公式 从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号c (n,m)表示. c(n,m)=p(n,m)/m!=n!/(n-m)!*m!)；c(n,m)=c(n,n-m); 23 n个元素中取出r个元素的循环排列数p(n,r)/r=n!/r(n-r)!. 24 n个元素被分成k类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为 n!/(n1!*n2!*.*nk!). 25可重复组合 如果上述组合定义中每一个元素可重复选取，则称为n元集中的可重复r-组合。n元集中的可重复r-组合的总数为C(n+r-1,r)。证明：从n元集中可重复地选取r个元素，设第一个元素选x1个，第二个元素选x2个，第n个元素选xn个，则议程x1+x2+xn=r的非负整数解的个数就是n元集中的可重复r-组合的总数。将r个1排成一排，插入n-1个分隔符，把r个1分成n段，n段中的1的个数即是方程的一个解。插入n-1个分隔符的过程实际上就是从n+r-1个位置中选择n-1个位置放分隔符，其余r个位置放1，共有C(n+r-1,n-1)=C(n+r-1,r)。可重复组合也可解释为：有n类元素,每类的个数无限,从中取出r个元素的组合。3.排列与组合的产生算法31排列的产生方法：（递归，深度优先产生）程序如下：program pailei;const m=4;var a:array1.m of integer ; b:array1.m of boolean;procedure print;var i:integer;beginfor i:=1 to m do write(ai);writeln;end;procedure try(dep:integer);var i:integer;beginfor i:=1 to m do if bi then begin adep:=i; bi:=false; if dep=m then print else try(dep+1); bi:=true; end;end;beginfillchar(b,sizeof(b),true);try(1);end.方法根据上一个排列产生下一个排列程序如下：program pailei;const m=5;var a:array1.m of integer ;i,j,temp,k,l:integer;procedure print;var i:integer;beginfor i:=1 to m do write(ai);writeln;end;beginfor i:=1 to m do ai:=i;repeatprint;i:=m-1;while (i0) and (aiai+1) do i:=i-1;if i0 thenbegin j:=m; while ajai do j:=j-1; temp:=ai;ai:=aj;aj:=temp; k:=i+1;l:=m; while k0) and (ai=n-(m-i) do dec(i); if i0 then begin ai:=ai+1; for j:=i+1 to m do aj:=aj-1+1; end;until i=0;end.4二项式定理C(n,0)+C(n,1)+C(n,n-1) +C(n,n)=2n 证明：等式左边包含了n元集的从零个元素到n个元素的全部组合，每一种组合与一个n位二进制数一一对应，对应方式为：n 位二进制数共有n位，每一位对应n元集的一个元素，如果n 位二进制数某一位上为1，则表示选中该位对应的元素，否则表示未选中该位对应的元素，这样一个n位二进制数就对应一种组合；反过来每一种组合同样对应一个n位二进制数，而n位二进制数的总数为2n。 杨辉三角 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 11 9 36 84 126 126 84 36 9 1 杨辉三角的每一行中的第一个数和最后一个数均为1,其余位置上的数可利用其上一行中的数递推计算出来,其值为上一行中位于同一列和前一列的两个数之和。5.鸽巢原理 5.1简单形式 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。 例2：在13个人中必存在两个人，他们的生日在同一月份里。 例3：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（n+1） 5.2加强形式 令q1,q2,.qn为正整数。如果将 q1+q2+.+qn-n+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1个物体,或者第二个盒子 至少含有q2个物体,.,或者第n个盒子含有qn个物体. 例4:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9 个橘子，则放入篮子中的水果的最小件数是多少？（21件） 6. 容斥原理及应用 设S为有穷集，P1，P2，Pn是n条性质。S中的任一元素x对于这n条性质可能具有其中的一种、二种、n种，也可能任何性质都没有。设Ai(i=1,2, ,n)表示S中具有Pi的元素构成的子集。这时容斥原理可叙述为：定理：S中不具有性质P1，P2，Pn的元素数是： 如:m=3,时上式为： =|S|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)|A1A2A3| 推论:至少具有性质P1,P2,.Pm之一的集合S的物体的个数有： | A1A2.Am|=|S|A1A2.Am|= |Ai|-|AiAj|+|AiAjAk|+.+(-1)m+1|A1A2.Am| 例4：求从1到1000不能被5，6，和8整除的整数的个数？ （1000-（200+166+125）+（33+25+41）-8=600） 7. 常见递推关系及应用7.1算术序列 每一项比前一项大一个常数d； 若初始项为h0：则递推关系为 hn=hn-1+d=h0+nd； 对应的各项为：h0，h0+d，h0+2d，.,h0+nd; 前n项的和为(n+1)h0+dn(n+1)/2 例5: 1,2,3,. 例6: 1,3,5,7.等都是算术序列。 7.2几何序列 每一项是前面一项的常数q倍 若初始项为h0：则递推关系为 hn=h0qn-1q=h0qn； 对应的各项为: h0，h0q1，h0q2，.,h0qn例7: 1,2,4,8,16,. 例8: 5,15,45,135,.等都是几何序列; 前n项和为(qn+1-1)/(q-1) )h0 7.3Fibonacci序列 除第一、第二项外每一项是它前两项的和； 若首项为f0为0,则序列为0，1，1，2，3，5，8.递推关系为(n=2)fn=fn-1+fn-2 前n项的和Sn=f0+f1+f2+.+fn=fn+2-1 例9:以下是Fibonacci的示例: (1)楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法? (2)有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子? (3)有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？ 7.4错位排列 首先看例题：例10：在书架上放有编号为1,2,.n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3时:原来位置为:123放回去时只能为:312或231这两种问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法) (44)1，2，3，.,n错位排列是1,2,3,.,n的一个排列i1i2.in,使得i11,i22,i33,.inn 错位排列数列为 0,1,2,9,44,265,. 错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n=3) =ndn-1+(-1)n-2 7.5分平面的最大区域数 (1) 直线分平面的最大区域数的序列为: 2，4，7，11，., 递推公式是: fn=fn-1+n=n(n+1)/2+1 (2)折线分平面的最大区域数的序列为: 2, 7, 16,29, ., 递推公式是:fn=(n-1)(2n-1)+2n; (3)封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为: 2, 4, 8, 14,., 递推公式是:fn=fn-1+2(n-1)=n2-n+2 7.6 Catalan 数列 先看下面两个例题:例11: 欧拉多边形分割问题： 设有一个正凸n边形,可以用n-3条不相交的对角线将n边形分成n-2个互相没有重叠的三角形, 例如n=5,共有图2_1所示的5种方法。图2_1 对任意给定的一个n边形，任意选定一条边，则该边必是某一组成分割的三角形的一边，它的两个端点也是该三角形的两个端点，另一个端点可以来自于另外n-2个顶点，这个三角形将n边形分成二个多边形，图2_2是选定底边时的情况。图2_2 根据加法原理和乘法原理有： Hn=Hn-1+H3Hn-2+Hn-2H3+Hn-1 (1)另外任取一条对角线Pij，将n边形一分为二，二部分分别为多边形，它们的边数之和为n+2，从一个顶点出发的n-3条对角线形成的n边形分割数为：H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3，从n个顶点出发的n(n-3)条对角线形成的n边形分割数为n(H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3)，由于一条对角线有两个端点，所以在上面的统计中，每条对角线出现了两遍，从所有的对角线出发形成的n边形分割数为：n(H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3)/2。任何一个分割是由n-3条对角线组成的，每个分割在上式中被重复统计了n-3遍，所以：(n-3)Hn=n(H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3)/2 (2)将(1)式写成n+1的情况有：Hn+1=Hn+H3Hn-1+Hn-1H3+Hn=(2+2(n-3)/n)Hn=(4n-6)/n)HnCatalan数的计算公式： Hn+1=c(2n-2,n-1)/n (n=1,2,3,.)例12: n个+1和n个-1构成2n项 a1,a2,.,a2n 其部分和满足a1+a2+.+ak=0(k=1,2,3,.,2n)，满足该条件的2n项不同的排列方式为 Cn=C(2n,n)/(n+1) 对应的序列为 1,1,2,5,14,42,132,.序列1,1,2,5,14,42,132,.叫Catalan数列。N凸多边形的分割总数Hn=Cn-1例13：下列问题都是Catalan数列。(1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(2)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？(3)在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?(4)n个结点可够造多少个不同的二叉树?(5)一个栈(无穷大)的进栈序列为1,2,3,.n,有多少个不同的出栈序列?7.7 第二类Stirling数定义：n个有区别的球放入r个相同的盒子中，要求无一空盒，其不同的方案数 s(n,r)称为第二类Stirling数。例如：红(k)、黄(y)、蓝(b)、白(w)四种颜色的球，放入两个无区别的盒子里，不允许空盒，其方案数共有如下7种：方案1234567第1盒子rybWryrbrw第2盒子ybwrbwrywRybbwywyb所以S(4,2)=7 下面就1n5,1rn列出各个S(n,r)的值如下r1234511211313141761511525101定理：第二类Stirling数满足下面的递推关系S(n,r)=rS(n-1,r)+S(n-1,r-1) (n1,r1)证明：设n个不同的球为b1,b2,bn，从中取一个球设为b1。把这n个球放入r个盒子无一空盒的方案全体可分为两类： b1独占一盒，其余n-1个球放入r-1个盒子无一空盒的方案数为S(n-1,r-1) b1不独占一盒，这相当于先将b2,b3,bn这n-1个球放入r个盒子，不允许有空盒的方案数共有S(n-1,r)，然后将b1放入其中一盒，这一盒子有r种可挑选，故b1不独占一盒的方案数为rS(n-1,r)。根据加法原理，则有S(n,r)=rS(n-1,r)+S(n-1,r-1) (n1,r1)对于 n=r，或r=1，显然有 S(n,n)=1，S(n,1)=1。思考题： n个有区别的球放入r个不同的盒子中，要求无一空盒，求不同的方案数。算法提示 可用第二类Stirling数的递推关系先求出S(n,r)，再乘上r!，即得所求方案数页：14主要算法描述如下：数据结构const maxn=10 球的最大数目var s:Array0.maxn,0.maxn of longint 存放第二类数用下列二重循环 求S(n,r)置 S0,0=1; for i:=1 to n do for j:=1 to r do S(i,j)=i*S(i-1,j)+S(i-1,j-1);计算方案数S S:=Sn,r; for i:=1 to r doS:=S*I;。8. 正整数的分拆8.1概念把正整数n表示成k个正整数之和的一种表示法n=n1+n2+nk称为 n的一个k部分拆，每个被加数ni称为此分拆的一个分部。n的k部分拆的个数记为P(n,k)；n的所有分拆的个数记为P(n)，即P(n)=P(n,k)，k=1,2,n，P(n)称为n的分拆数。在1669年GLeibnitz给JBernoulli的一封信里最先提出了确定分拆数的问题。不过首先系统研究这类计数问题的是Euler，对分拆数的研究是一类重要的计数课题，其内容十分丰富，在数学各分支中有广泛的应用。这里只是一个很初步的介绍。8.2有序分拆 首先应该说明，以上所说的分拆不考虑各分部的次序。所以n的每个 k部分拆可以唯一确定地表示成如下规范形式：n=n1+n2+nk，其中n1n2nk1。这个分拆可简记为(n1,n2,nk)。一般地，正整数n的有序分拆用有序k元组(a1,ak)表示，其中数ai称为这个有序分拆的第i个分部(i=1,k)。例如4只有1个3部分拆(2,1,1)，但有3个有序3部分拆(2,1,1)，(1,2,1)和(1,1,2)。一般说来，有序分拆的计数比较容易处理。下面是一个典型的有关结论，它们说明有序分拆的计数常常能归结到可重复组合公式。正整数 n的一个 k部有序分拆(n1,n2,nk)就是k元不定方程 x1+x2+xk=n的一个正整数解，从而可知其总数是C(n-1,k-1)。三 计算几何初步1 基础知识 1.1两点间的距离公式： 已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则P1和P2两点间的距离为 d=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) 1.2线段的中点坐标公式： 已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则线段P1P2的中点坐标为 x=(x1+x2)/2 y=(y1+y2)/2 1.3直线的斜率公式： 已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2),则线段P1P2所在的直线的斜率为 k=（y2-y1）/(x2-x1) 1.4直线的点斜式方程: 已知：直线过点P0(x0,y0)，斜率为k,则该直线所在的方程为 y=k(x-x0)+y0=kx+y0-kx0=kx+b(与y轴交点的纵坐标:纵截距) 思考题 （1）已知:矩形上三点的坐标p1(x1,y1),p2(x2,y2),p3(x3,y3) （2）求矩形另外一点的坐标p4(x4,y4)。 （3）判断点p(x,y)是在矩形内、矩形外还是在矩形的边上。 2 线段的相交判断 2.1叉积 已知：平面上的两点的直角坐标分别为p1(x1,y1)，p2(x2,y2)则 （1）该两点相对坐标原点(0,0)的叉积为m=x1*y2-x2*y1 若m0 则相对坐标原点,点p1在点p2的顺时针方向 若m0 则相对p0点,点p1在点p2的顺时针方向 若m0 则p1点向左拐 若mb then max:=a else max:=b;end;function min(a,b:real):real;beginif a=min(p3.x,p4.x) and (max(p3.x,p4.x)=min(p1.x,p2.x) and (max(p1.y,p2.y)=min(p3.y,p4.y) and (max(p3.y, p4.y)=min(p1.y,p2.y) and (m(p2,p3,p1)*m(p2,p4,p1)0) and (m(p4,p1,p3)*m(p4,p2,p3)0) or (t=0) and (sqr(p1.x-list0.x)+sqr(p1.y-list0.y) sqr(p2.x-list0.x)+sqr(p2.y-list0.y) then comp:=true else comp:=false;end;procedure sort(l,r:integer);var i,j:integer;x:p;beginif r-l+11) and comp(listi,listi-1) do begin swap(listi,listi-1); dec(i) end end; end else begin x:=listl+random(r-l+1); i:=l;j:=r; repeat while comp(listi,x) do inc(j); while comp(x,listj) do dec(j); if i=j; sort(l,j); sort(j+1,r); endend;procedure init;var i:integer;beginassign(f,input.txt);reset(f);readln(f,n);for i:=0 to n-1 do begin readln(f,listi.x,listi.y); if (listi.ylist0.y) or (listi.y=list0.y) and (listi.x=0 do dec(top); inc(top); stop:=i; end; for i:=1 to top do write(,listsi.x:7:2,listsi.y:7:2,); writelnend;begininit;graham;readlnend.四 编程实例题1欧几里德的游戏【问题描述】欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得到的数，和M,N中较小的那个数，再进行同样的操作直到一个人得到了0，他就取得了胜利。下面是他们用（25,7）两个数游戏