C语言常用代码

1、#include<iostream>usingnamespacestd;voidfullxunhuan(int*a,intn)(intt=0;intm1,m2;if(n%2!=0)n+;for(inti=0;i<n%2;i+)for(m1=i,m2=n-i-1;m1<=n-i-1;m1+)am1m2=t%n+1;t+;for(-m1,-m2;m2>i;m2-)am1m2=t%n+1;t+;for(;m1>i;m1-)am1m2=t%n+1;t+;for(;m2<n-i-1;m2+)am1m2=t%n+1;t+;voidprint(int*a,intn)

2、for(inti=0;i<n;i+)for(intj=0;j<n;j+)cout<<aij<<"t"cout<<"n”;voidmain()int*a;intn;cout<<"请输入N”<<endl;cin>>n;a=newint*n;/申请一个N行N列的数组for(inti1=0;i1<n;i1+)ai1=newintn;for(inti=0;i<n;i+)/给数组初始化for(intj=0;j<n;j+)aij=0;fullxunhuan(a,n);

3、print(a,n);ACM小组内部预定函数数学问题：1精度计算大数阶乘2精度计算乘法(大数乘小数)3精度计算乘法(大数乘大数)4精度计算一一加法5精度计算一一减法任意进制转换最大公约数、最小公倍数组合序列快速傅立叶变换(FFT)Ronberg算法计算积分行列式计算求排列组合数字符串处理：字符串替换字符串查找字符串截取计算几何：叉乘法求任意多边形面积求三角形面积两矢量间角度两点距离(2D、3D)5射向法判断点是否在多边形内部判断点是否在线段上判断两线段是否相交判断线段与直线是否相交点到线段最短距离求两直线的交点判断一个封闭图形是凹集还是凸集Graham扫描法寻找凸包数论：x的二进制长度返回x的

4、二进制表示中从低到高的第i位模取藉运算求解模线性方程求解模线性方程组(中国余数定理)筛法素数产生器判断一个数是否素数图论：Prim算法求最小生成树Dijkstra算法求单源最短路径Bellman-ford算法求单源最短路径Floyd算法求每对节点间最短路径排序/查找：快速排序希尔排序选择法排序二分查找数据结构：顺序队列顺序栈链表链栈二叉树一、数学问题1.精度计算大数阶乘语法：intresult=factorial(intn);参数：n:n的阶乘返回值：阶乘结果的位数汪息：本程序直接输出n!的结果，需要返回结果请保留longa需要math.h源程序：intfactorial(intn)longa

5、10000;inti,j,l,c,m=0,w;a0=1;for(i=1;i<=n;i+)c=0;for(j=0;j<=m;j+)aj=aj*i+c;c=aj/10000;aj=aj%10000;if(c>0)m+;am=c;w=m*4+log10(am)+1;printf("n%ld”,am);for(i=m-1;i>=0;i-)printf("%4.4ld”,ai);returnw;2精度计算乘法(大数乘小数)语法：mult(charc,chart,intm);参数：c:被乘数，用字符串表示，位数不限t:结果，用字符串表示m:乘数，限定10以内返回

6、值：null汪息：需要string.h源程序：voidmult(charc,chart,intm)inti,l,k,flag,add=0;chars100;l=strlen(c);for(i=0;i<l;i+)sl-i-1=ci-'0'for(i=0;i<l;i+)k=si*m+add;if(k>=10)si=k%10;add=k/10;flag=1;elsesi=k;flag=0;add=0;if(flag)l=i+1;si=add;elsel=i;for(i=0;i<l;i+)tl-1-i=si+'0'tl='0'3精

7、度计算乘法(大数乘大数)语法：mult(chara,charb,chars);参数：a:被乘数，用字符串表示，位数不限b:乘数，用字符串表示，位数不限t:结果，用字符串表示返回值：null汪息：空间复杂度为o(nA2)需要string.h源程序：voidmult(chara,charb,chars)inti,j,k=0,alen,blen,sum=0,res6565=0,flag=0;charresult65;alen=strlen(a);blen=strlen(b);for(i=0;i<alen;i+)for(j=0;j<blen;j+)resij=(ai-'0'

8、)*(bj-'0');for(i=alen-1;i>=0;i-)for(j=blen-1;j>=0;j-)sum=sum+resi+blen-j-1j;resultk=sum%10;k=k+1;sum=sum/10;for(i=blen-2;i>=0;i-)for(j=0;j<=i;j+)sum=sum+resi-jj;resultk=sum%10;k=k+1;sum=sum/10;if(sum!=0)resultk=sum;k=k+1;for(i=0;i<k;i+)resulti+='0'for(i=k-1;i>=0;i-)

9、si=resultk-1-i;sk='0'while(1)if(strlen(s)!=strlen(a)&&s0='0')strcpy(s,s+1);elsebreak;4精度计算一一加法语法:add(chara,charb,chars);参数：a：被乘数，用字符串表示，位数不限b：乘数，用字符串表示，位数不限t:结果，用字符串表示返回值：null汪息：空间复杂度为o(nA2)需要string.h源程序：voidadd(chara,charb,charback)(inti,j,k,up,x,y,z,l;char*c;if(strlen(a)>

10、;strlen(b)l=strlen(a)+2;elsel=strlen(b)+2;c=(char*)malloc(l*sizeof(char);i=strlen(a)-1;j=strlen(b)-1;k=0;up=0;while(i>=0|j>=0)(if(i<0)x='0'elsex=ai;if(j<0)y='0'elsey=bj;z=x-'0'+y-'0'if(up)z+=1;if(z>9)(up=1;z%=10;elseup=0;ck+=z+'0'i-;j-;if(up)ck+

11、='1'i=0;ck='0'for(k-=1;k>=0;k-)backi+=ck;backi='0'精度计算一一减法语法:sub(chars1,chars2,chart);参数：s1：被减数，用字符串表示，位数不限s2：减数，用字符串表示，位数不限t:结果，用字符串表示返回值：null汪息：默认s1>=s2,程序未处理负数情况需要string.h源程序：voidsub(chars1,chars2,chart)(inti,l2,l1,k;l2=strlen(s2);l1=strlen(s1);tl1='0'l1-;for

12、(i=l2-1;i>=0;i-,l1-)(if(s1l1-s2i>=0)tl1=s1l1-s2i+'0'else(tl1=10+s1l1-s2i+'0's1l1-1=s1l1-1-1;k=l1;while(s1k<0)(s1k+=10;s1k-1-=1;k-;while(l1>=0)(tl1=s1l1;l1-;loop:if(t0='0')(l1=strlen(s1);for(i=0;i<l1-1;i+)ti=ti+1;tl1-1='0'gotoloop;if(strlen(t)=0)t0='

13、0't1='0'任意进制转换语法:conversion(chars1,chars2,longd1,longd2);参数：s：原进制数字，用字符串表示s2：转换结果，用字符串表示d1:原进制数d2：需要转换到的进制数返回值：null汪息：高于9的位数用大写A''Z'表示，216位进制通过验证源程序：voidconversion(chars,chars2,longd1,longd2)longi,j,t,num;charc;num=0;for(i=0;si!='0'i+)if(si<='9'&&si

14、>='0')t=si-'0'elset=si-'A'+10;num=num*d1+t;i=0;while(1)t=num%d2;if(t<=9)s2i=t+'0'elses2i=t+'A'-10;num/=d2;if(num=0)break;i+;for(j=0;j<i/2;j+)c=s2j;s2j=si-j;s2i-j=c;s2i+1='0'最大公约数、最小公倍数语法：resulet=hcf(inta,intb)、result=lcd(inta,intb)a：inta,求最大公约

15、数或最小公倍数b:intb,求最大公约数或最小公倍数返回值：返回最大公约数(hcf)或最小公倍数(lcd)汪息：lcd需要连同hcf使用源程序：inthcf(inta,intb)intr=0;while(b!=0)r=a%b;a=b;b=r;return(a);lcd(intu,intv,inth)return(u*v/h);组合序列语法:m_of_n(intm,intn1,intm1,int*a,inthead)参数：m:组合数C的上参数n1:组合数C的下参数m1:组合数C的上参数，递归之用*a：1n的整数序列数组head：头指针返回值：null汪息：*a需要自行产生初始调用时，m=m1、h

16、ead=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);源程序：voidm_of_n(intm,intn1,intm1,int*a,inthead)inti,t;if(m1<0|m1>n1)return;if(m1=n1)(for(i=0;i<m;i+)cout<<ai<<''/输出序列cout<<'n'return;m_of_n(m,n1-1,m1,a,head);/递归调用t=ahead;ahead=an1-1+head;an1-1+head=t;m_of_n(m,n1-1,m1-1,

17、a,head+1);/再次递归调用t=ahead;ahead=an1-1+head;an1-1+head=t;快速傅立叶变换(FFT)语法：kkfft(doublepr,doublepi,intn,intk,doublefr,doublefi,intl,intil);参数：prn:输入的实部pin:数入的虚部n,k:满足n=2Akfrn:输出的实部fin:输出的虚部l:逻辑开关，0FFT,1ifFTil:逻辑开关，0输出按实部/虚部；1输出按模/幅角返回值：null汪息：需要math.h源程序：voidkkfft(pr,pi,n,k,fr,fi,l,il)intn,k,l,il;doublep

18、r,pi,fr,fi;(intit,m,is,i,j,nv,l0;doublep,q,s,vr,vi,poddr,poddi;for(it=0;it<=n-1;it+)(m=it;is=0;for(i=0;i<=k-1;i+)(j=m/2;is=2*is+(m-2*j);m=j;frit=pris;fiit=piis;pr0=1.0;pi0=0.0;p=6.283185306/(1.0*n);pr1=cos(p);pi1=-sin(p);if(l!=0)pi1=-pi1;for(i=2;i<=n-1;i+)(p=pri-1*pr1;q=pii-1*pi1;s=(pri-1+p

19、ii-1)*(pr1+pi1);pri=p-q;pii=s-p-q;for(it=0;it<=n-2;it=it+2)(vr=frit;vi=fiit;frit=vr+frit+1;fiit=vi+fiit+1;frit+1=vr-frit+1;fiit+1=vi-fiit+1;m=n/2;nv=2;for(l0=k-2;l0>=0;l0-)(m=m/2;nv=2*nv;for(it=0;it<=(m-1)*nv;it=it+nv)for(j=0;j<=(nv/2)-1;j+)(p=prm*j*frit+j+nv/2;q=pim*j*fiit+j+nv/2;s=prm*

20、j+pim*j;s=s*(frit+j+nv/2+fiit+j+nv/2);poddr=p-q;poddi=s-p-q;frit+j+nv/2=frit+j-poddr;fiit+j+nv/2=fiit+j-poddi;frit+j=frit+j+poddr;fiit+j=fiit+j+poddi;if(l!=0)for(i=0;i<=n-1;i+)(fri=fri/(1.0*n);fii=fii/(1.0*n);if(il!=0)for(i=0;i<=n-1;i+)(pri=sqrt(fri*fri+fii*fii);if(fabs(fri)<0.000001*fabs(f

21、ii)(if(fii*fri)>0)pii=90.0;elsepii=-90.0;elsepii=atan(fii/fri)*360.0/6.283185306;return;Ronberg算法计算积分语法：result=integral(doublea,doubleb);参数：a：积分上限b:积分下限functionf:积分函数返回值：f在(a,b)之间的积分值汪息：functionf(x)需要自行修改，程序中用的是sina(x)/x需要math.h默认精度要求是1e-5源程序：doublef(doublex)(returnsin(x)/x;/在这里插入被积函数doubleintegr

22、al(doublea,doubleb)(doubleh=b-a;doublet1=(1+f(b)*h/2.0;intk=1;doubler1,r2,s1,s2,c1,c2,t2;loop:doubles=0.0;doublex=a+h/2.0;while(x<b)(s+=f(x);x+=h;t2=(t1+h*s)/2.0;s2=t2+(t2-t1)/3.0;if(k=1)(k+;h/=2.0;t1=t2;s1=s2;gotoloop;c2=s2+(s2-s1)/15.0;if(k=2)(c1=c2;k+;h/=2.0;t1=t2;s1=s2;gotoloop;r2=c2+(c2-c1)/

23、63.0;if(k=3)(r1=r2;c1=c2;k+;h/=2.0;t1=t2;s1=s2;gotoloop;while(fabs(1-r1/r2)>1e-5)r1=r2;c1=c2;k+;h/=2.0;t1=t2;s1=s2;gotoloop;returnr2;行列式计算语法:result=js(ints,intn)参数：s:行列式存储数组n:行列式维数，递归用返回值：行列式值汪息：函数中常数N为行列式维度，需自行定义源程序：intjs(s,n)intsN,n;(intz,j,k,r,total=0;intbNN;/*bNN用于存放，在矩阵sNN中元素s0的余子式*/if(n>

24、2)(for(z=0;z<n;z+)(for(j=0;j<n-1;j+)for(k=0;k<n-1;k+)if(k>=z)bjk=sj+1k+1;elsebjk=sj+1k;if(z%2=0)r=s0z*js(b,n-1);/*递归调用*/elser=(-1)*s0z*js(b,n-1);total=total+r;elseif(n=2)total=s00*s11-s01*s10;returntotal;求排列组合数语法：result=P(longn,longm);/result=longC(longn,longm);m：排列组合的上系数n:排列组合的下系数返回值：排列

25、组合数汪息：符合数学规则：m<=n源程序：longP(longn,longm)(longp=1;while(m!=0)p*=n;n-;m-;returnp;longC(longn,longm)longi,c=1;i=m;while(i!=0)c*=n;n-;i-;while(m!=0)c/=m;m-;returnc;二、字符串处理字符串替换语法:replace(charstr,charkey,charswap)参数：str:在此源字符串进行替换操作key：被替换的字符串，不能为空串swap：替换的字符串，可以为空串，为空串表示在源字符中删除key返回值：null汪息：默认str长度小于1

26、000,如否，重新设定设定tmp大小需要string.h源程序：voidreplace(charstr,charkey,charswap)intl1,l2,l3,i,j,flag;chartmp1000;l1=strlen(str);l2=strlen(key);l3=strlen(swap);for(i=0;i<=l1-l2;i+)(flag=1;for(j=0;j<l2;j+)if(stri+j!=keyj)(flag=0;break;if(flag)(strcpy(tmp,str);strcpy(&tmpi,swap);strcpy(&tmpi+l3,&

27、;stri+l2);strcpy(str,tmp);i+=l3-1;l1=strlen(str);字符串查找语法:result=strfind(charstr,charkey);参数：str:在此源字符串进行查找操作key：被查找的字符串，不能为空串返回值：如果查找成功，返回key在str中第一次出现的位置，否则返回-1汪息：需要string.h源程序：intstrfind(charstr,charkey)(intl1,l2,i,j,flag;l1=strlen(str);l2=strlen(key);for(i=0;i<=l1-l2;i+)(flag=1;for(j=0;j<l2

28、;j+)if(stri+j!=keyj)(flag=0;break;if(flag)returni;return-1;字符串截取语法:mid(charstr,intstart,intlen,charstrback)参数：str:操作的目标字符串start：从第start个字符串开始，截取长度为len的字符len：从第start个字符串开始，截取长度为len的字符strback:截取的到的字符返回值：0：超出字符串长度，截取失败；1：截取成功汪息：需要string.h源程序：intmid(charstr,intstart,intlen,charstrback)(intl,i,k=0;l=strl

29、en(str);if(start+len>l)return0;for(i=start;i<start+len;i+)strbackk+=stri;strbackk='0'return1;三、计算几何叉乘法求任意多边形面积语法:result=polygonarea(Point*polygon,intN);参数：*polygon:多变形顶点数组N:多边形顶点数目返回值：多边形面积汪息：支持任意多边形，凹、凸皆可多边形顶点输入时按顺时针顺序排列源程序：typedefstruct(doublex,y;Point;doublepolygonarea(Point*polygon

30、,intN)(inti,j;doublearea=0;for(i=0;i<N;i+)(j=(i+1)%N;area+=polygoni.x*polygonj.y;area-=polygoni.y*polygon田.x;area/=2;return(area<0?-area:area);求三角形面积语法：result=area3(floatx1,floaty1,floatx2,floaty2,floatx3,floaty3);参数：x13:三角形3个顶点x坐标y13:三角形3个顶点y坐标返回值：三角形面积汪息：需要math.h源程序：floatarea3(floatx1,floaty

31、1,floatx2,floaty2,floatx3,floaty3)(floata,b,c,p,s;a=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);b=sqrt(x1-x3)*(x1-x3)+(y1-y3)*(y1-y3);C=sqrt(x3-x2)*(x3-x2)+(y3-y2)*(y3-y2);p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c);returns;两矢量间角度语法:result=angle(doublex1,doubley1,doublex2,doubley2);参数：x/y12：两矢量的坐标返回值：两的角度矢量汪息：返回

32、角度为弧度制，并且以逆时针方向为正方向需要math.h源程序：#definePI3.1415926doubleangle(doublex1,doubley1,doublex2,doubley2)(doubledtheta,theta1,theta2;theta1=atan2(y1,x1);theta2=atan2(y2,x2);dtheta=theta2-theta1;while(dtheta>PI)dtheta-=PI*2;while(dtheta<-PI)dtheta+=PI*2;return(dtheta);两点距离(2D、3D)语法：result=distance_2d(f

33、loatx1,floatx2,floaty1,floaty2);参数：x/y/z12：各点的x、y、z坐标返回值：两点之间的距离汪息：需要math.h源程序：floatdistance_2d(floatx1,floatx2,floaty1,floaty2)(return(sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);floatdistance_3d(floatx1,floatx2,floaty1,floaty2,floatz1,floatz2)(return(sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);5射向

34、法判断点是否在多边形内部语法：result=insidepolygon(Point*polygon,intN,Pointp);参数：*polygon:多边形顶点数组N:多边形顶点个数p:被判断点返回值：0:点在多边形内部；1:点在多边形外部汪息：若p点在多边形顶点或者边上，返回值不确定，需另行判断需要math.h源程序：#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstruct(doublex,y;Point;intinsidepolygon(Point*polygon,intN,Pointp)(intcounter=

35、0;inti;doublexinters;Pointp1,p2;pl=polygon0;for(i=1;i<=N;i+)p2=polygoni%N;if(p.y>MIN(p1.y,p2.y)if(p.y<=MAX(p1.y,p2.y)if(p.x<=MAX(p1.x,p2.x)if(p1.y!=p2.y)xinters=(p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;if(p1.x=p2.x|p.x<=xinters)counter+;p1=p2;if(counter%2=0)return(OUTSIDE);elsereturn(I

36、NSIDE);判断点是否在线段上语法：result=Pointonline(Pointp1,Pointp2,Pointp);参数：p1、p2:线段的两个端点p:被判断点返回值：0:点在不在线段上；1:点在线段上汪息：若p线段端点上返回1需要math.h源程序：#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstructdoublex,y;Point;intFC(doublex1,doublex2)if(x1-x2<0.000002&&x1-x2>-0.000002)return1;elsere

37、turn0;intPointonline(Pointp1,Pointp2,Pointp)doublex1,y1,x2,y2;x1=p.x-p1.x;x2=p2.x-p1.x;y1=p.y-p1.y;y2=p2.y-p1.y;if(FC(x1*y2-x2*y1,0)=0)return0;if(MIN(p1.x,p2.x)<=p.x&&p.x<=MAX(p1.x,p2.x)&&(MIN(p1.y,p2.y)<=p.y&&p.y<=MAX(p1.y,p2.y)return1;elsereturn0;判断两线段是否相交语法:res

38、ult=sectintersect(Pointp1,Pointp2,Pointp3,Pointp4);参数：p14:两条线段的四个端点返回值：0:两线段不相交；1:两线段相交；2两线段首尾相接汪息：p1!=p2;p3!=p4;源程序：#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstruct(doublex,y;Point;intlineintersect(Pointp1,Pointp2,Pointp3,Pointp4)(Pointtp1,tp2,tp3;if(p1.x=p3.x&&p1.y=p3.y)

39、|(p1.x=p4.x&&p1.y=p4.y)|(p2.x=p3.x&&p2.y=p3.y)|(p2.x=p4.x&&p2.y=p4.y)return2;/快速排斥试验if(MIN(p1.x,p2.x)<p3.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y)|(MIN(p1.x,p2.x)<p4.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p

40、3.y<MAX(p1.y,p2.y);elsereturn0;/跨立试验tp1.x=p1.x-p3.x;tp1.y=p1.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=p4.y-p3.y;tp3.x=p2.x-p3.x;tp3.y=p2.y-p3.y;if(tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0)return1;elsereturn0;判断线段与直线是否相交语法:result=lineintersect(Pointp1,Pointp2,Pointp3,Pointp4);参数：p1、p2:线段的两个端点p

41、3、p4:直线上的两个点返回值：0:线段直线不相交；1:线段和直线相交汪息：如线段在直线上，返回1源程序：typedefstruct(doublex,y;Point;intlineintersect(Pointp1,Pointp2,Pointp3,Pointp4)(Pointtp1,tp2,tp3;tp1.x=p1.x-p3.x;tp1.y=p1.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=p4.y-p3.y;tp3.x=p2.x-p3.x;tp3.y=p2.y-p3.y;if(tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)&

42、gt;=0)return1;elsereturn0;9点到线段最短距离语法:result=mindistance(Pointp1,Pointp2,Pointq);p1、p2:线段的两个端点q:判断点返回值：点q到线段p1p2的距离汪息：需要math.h源程序：#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstruct(doublex,y;Point;doublemindistance(Pointp1,Pointp2,Pointq)(intflag=1;doublek;Points;if(p1.x=p2.x)s.x=p1

43、.x;s.y=q.y;flag=0;if(p1.y=p2.y)s.x=q.x;s.y=p1.y;flag=0;if(flag)k=(p2.y-p1.y)/(p2.x-p1.x);s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1);s.y=k*(s.x-p1.x)+p1.y;if(MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x)returnsqrt(q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y);elsereturnMIN(sqrt(q.x-p1.x)*(q.x-p1.x)+(q

44、.y-p1.y)*(q.y-p1.y),sqrt(q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y);求两直线的交点语法:result=mindistance(Pointp1,Pointp2,Pointq);k1(注释中)的值是否在01之间，用在01之间的那个求交点源程序：typedefstructdoublex,y;Point;intlinecorss(Pointp1,Pointp2,Pointp3,Pointp4,Point*p)doublek;/同一直线if(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)=0

45、&&(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)=0)return2;/平行，不同一直线if(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)=0)return0;k=(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)/(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y);/k1=(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)/(p4.y-p3.y)*(

46、p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y);(*p).x=p1.x+k*(p2.x-p1.x);(*p).y=p1.y+k*(p2.y-p1.y);return1;/有交点判断一个封闭图形是凹集还是凸集语法：result=convex(Point*p,intn);p1p4:直线上不相同的两点*p:通过指针返回结果返回值：1:两直线相交；2:两直线平行汪息：如需要判断两线段交点，检验k和对应*p:封闭曲线顶点数组n:封闭曲线顶点个数返回值：1:凸集；-1:凹集；0:曲线不符合要求无法计算汪息：默认曲线为简单曲线：无交叉、无圈源程序：typedefstruct(doubl

47、ex,y;Point;intconvex(Point*p,intn)(inti,j,k;intflag=0;doublez;if(n<3)return(0);for(i=0;i<n;i+)j=(i+1)%n;k=(i+2)%n;z=(pj.x-pi.x)*(pk.y-pj.y);z-=(pj.y-pi.y)*(pk.x-pj.x);if(z<0)flag|=1;elseif(z>0)flag|=2;if(flag=3)return1;/CONCAVEif(flag!=0)return1;/CONVEXelsereturn0;Graham扫描法寻找凸包语法：Graham_

48、scan(PointPointSet,Pointch,intn,int&len);参数：PointSet:输入的点集ch:输出的凸包上的点集，按照逆时针方向排列n:PointSet中的点的数目len:输出的凸包上的点的个数返回值：null源程序：structPointfloatx,y;floatmultiply(Pointp1,Pointp2,Pointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);floatdistance(Pointp1,Pointp2)return(sqrt(p1.x-p2.x)*(p1.x-p2

49、.x)+(p1.y-p2.y)*(p1.y-p2.y);voidGraham_scan(PointPointSet,Pointch,intn,int&len)inti,j,k=0,top=2;Pointtmp;for(i=1;i<n;i+)if(PointSeti.y<PointSetk.y)|(PointSeti.y=PointSetk.y)&&(PointSeti.x<PointSetk.x)k=i;tmp=PointSet0;PointSet0=PointSetk;PointSetk=tmp;for(i=1;i<n-1;i+)k=i;for

50、(j=i+1;j<n;j+)if(multiply(PointSetj,PointSetk,PointSet0)>0)II(multiply(PointSetj,PointSetk,PointSet0)=0)&&(distance(PointSet0,PointSetj)<distance(PointSet0,PointSetk)k=j;tmp=PointSeti;PointSeti=PointSetk;PointSetk=tmp;ch0=PointSet0;ch1=PointSet1;ch2=PointSet2;for(i=3;i<n;i+)(whil

51、e(multiply(PointSeti,chtop,chtop-1)>=0)top-;ch+top=PointSeti;len=top+1;四、数论x的二进制长度语法:result=BitLength(intx);参数：x：测长的x返回值：x的二进制长度源程序：intBitLength(intx)(intd=0;while(x>0)(x>>=1;d+;returnd;返回x的二进制表示中从低到高的第i位语法:result=BitAt(intx,inti);参数：x:十进制xi:要求二进制的第i位返回值：返回x的二进制表示中从低到高的第i位汪息：最低位为第一位源程序：i

52、ntBitAt(intx,inti)return(x&(1<<(i-1);模取藉运算语法：result=Modular_Expoent(inta,intb,intn);参数：a、b、n:aAbmodn的对应参数返回值：aAbmodn的值汪息：需要BitLength和BitAt源程序：intModular_Expoent(inta,intb,intn)(inti,y=1;for(i=BitLength(b);i>0;i-)(y=(y*y)%n;if(BitAt(b,i)>0)y=(y*a)%n;returny;求解模线性方程语法：result=modular_eq

53、uation(inta,intb,intn);参数：a、b、n:ax=b(modn)的对应参数返回值：方程的解源程序：intext_euclid(inta,intb,int&x,int&y)/求gcd(a,b)=ax+by(intt,d;if(b=0)(x=1;y=0;returna;d=ext_euclid(b,a%b,x,y);t=x;x=y;y=t-a/b*y;returnd;voidmodular_equation(inta,intb,intn)(inte,i,d;intx,y;d=ext_euclid(a,n,x,y);if(b%d>0)printf("

54、;Noanswer!n");else(e=(x*(b/d)%n;for(i=0;i<d;i+)printf("The%dthansweris:%ldn”,i+1,(e+i*(n/d)%n);求解模线性方程组(中国余数定理)语法：result=Modular_Expoent(inta,intb,intn);参数：B、W:a=B(modW)的对应参数返回值：a的值汪息：其中W,B已知，Wi>0且Wi与W田互质，求a源程序：intext_euclid(inta,intb,int&x,int&y)/求gcd(a,b)=ax+by(intt,d;if(b=

55、0)(x=1;y=0;returna;d=ext_euclid(b,a%b,x,y);t=x;x=y;y=t-a/b*y;returnd;intChina(intB,intW,intk)(for(i=0;i<k;i+)n*=Wi;for(i=0;i<k;i+)(m=n/Wi;d=ext_euclid(Wi,m,x,y);a=(a+y*m*Bi)%n;if(a>0)returna;elsereturn(a+n);筛法素数产生器语法：result=prime(inta,intn);参数：a:用于返回素数的数组n:产生n以内的素数，按升序放入a口中返回值：n以内素数的个数汪息：其中

56、W,B已知，Wi>0且Wi与Wj互质，求a源程序：intprime(inta,intn)(inti,j,k,x,num,*b;n+;n/=2;b=(int*)malloc(sizeof(int)*(n+1)*2);a0=2;a1=3;num=2;for(i=1;i<=2*n;i+)bi=0;for(i=3;i<=n;i+=3)for(j=0;j<2;j+)(x=2*(i+j)-1;while(bx=0)(anum+=x;for(k=x;k<=2*n;k+=x)bk=1;inti;intd,x,y,a=0,m,n=1;returnnum;判断一个数是否素数语法：result=comp(intn);参数：n:判断n是否素数返回值：素数返回1,否则返回0源程序：intcomp(intn)(inti,flag=1;for(i=2;i<=sqrt(n);i+)if(n%i=0)flag=0;break;if(flag=1)retur