清華內(nèi)部ACM培訓(xùn)資料,各類經(jīng)典算法

1、ACM小組內(nèi)部預(yù)定函數(shù)數(shù)學(xué)問題：1.精度計(jì)算大數(shù)階乘4.精度計(jì)算加法2.精度計(jì)算乘法（大3.精度計(jì)算乘法（大數(shù)乘小數(shù)） 6.任意進(jìn)制轉(zhuǎn)換數(shù)乘大數(shù)）7.最大公約數(shù)、最小公倍數(shù)5.精度計(jì)算減法 8.組合序列 12.求排列組合數(shù)4.兩點(diǎn)距離（2D、3D） 8.判斷線段與直線是否相交12.Graham掃描法尋找凸包4.求解模線性方程9.快速傅立葉變換（FFT） 10.Ronberg算法計(jì)算積分 11.行列式計(jì)算字符串處理： 1.字符串替換計(jì)算幾何：1.叉乘法求任意多邊形面積5.射向法判斷點(diǎn)是否在多邊形內(nèi)部9.點(diǎn)到線段最短距離 數(shù)論：1.x的二進(jìn)制長(zhǎng)度 5.求解模線性方程組(中國(guó)余數(shù)定理) 圖論：1.P

2、rim算法求最小生成樹排序/查找： 1.快速排序數(shù)據(jù)結(jié)構(gòu)：2.字符串查找2.求三角形面積3.字符串截取3.兩矢量間角度6.判斷點(diǎn)是否在線段上 7.判斷兩線段是否相交 11.判斷一個(gè)封閉圖形是凹集還是凸集3.模取冪運(yùn)算10.求兩直線的交點(diǎn)2.返回x的二進(jìn)制表示中從低到高的第i位 6.篩法素?cái)?shù)產(chǎn)生器7.判斷一個(gè)數(shù)是否素?cái)?shù)2.希爾排序源最短路徑3.選擇法排序間最短路徑4.二分查找1.順序隊(duì)列5.二叉樹 2.順序棧 3.鏈表 4.鏈棧一、數(shù)學(xué)問題1.精度計(jì)算大數(shù)階乘語法：int result=factorial(int n);參數(shù)：n： n 的階乘返回值： 階乘結(jié)果的位數(shù)注意：本程序直接輸出n!的結(jié)果

3、，需要返回結(jié)果請(qǐng)保留long a 需要 math.h源程序：int factorial(int n)long a10000;int i,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);return w;2.精度計(jì)算乘法（大數(shù)乘小數(shù)

4、）語法：mult(char c,char t,int m);參數(shù)：c： 被乘數(shù)，用字符串表示，位數(shù)不限t： 結(jié)果，用字符串表示m： 乘數(shù)，限定10以內(nèi)返回值： null注意：需要 string.h源程序：void mult(char c,char t,int m)int i,l,k,flag,add=0;char s100;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; else si=k;flag=0

5、;add=0;if (flag) l=i+1;si=add; else l=i;for (i=0;i<l;i+)tl-1-i=si+'0'tl='0'3.精度計(jì)算乘法（大數(shù)乘大數(shù)）語法：mult(char a,char b,char s);參數(shù)：a： 被乘數(shù)，用字符串表示，位數(shù)不限b： 乘數(shù)，用字符串表示，位數(shù)不限t： 結(jié)果，用字符串表示返回值： null注意：空間復(fù)雜度為 o(n2) 需要 string.h源程序：void mult(char a,char b,char s)int i,j,k=0,alen,blen,sum=0,res6565=0,fl

6、ag=0; char result65;alen=strlen(a);blen=strlen(b);for (i=0;i<alen;i+)for (j=0;j<blen;j+) resij=(ai-'0')*(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+res

7、i-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-) si=resultk-1-i;sk='0'while(1)if (strlen(s)!=strlen(a)&&s0='0')strcpy(s,s+1);elsebreak;4.精度計(jì)算加法語法：add(char a,char b,char s);參數(shù)：a： 被乘數(shù)，用字符串表示，位數(shù)不限b：

8、 乘數(shù)，用字符串表示，位數(shù)不限t： 結(jié)果，用字符串表示返回值： null注意：空間復(fù)雜度為 o(n2) 需要 string.h源程序：void add(char a,char b,char back)int i,j,k,up,x,y,z,l;char *c;if (strlen(a)>strlen(b) l=strlen(a)+2; else l=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='

9、;0' else x=ai;if(j<0) y='0' else y=bj;z=x-'0'+y-'0'if(up) z+=1;if(z>9) up=1;z%=10; else up=0;ck+=z+'0'i-;j-;if(up) ck+='1'i=0;ck='0'for(k-=1;k>=0;k-)backi+=ck;backi='0'5.精度計(jì)算減法語法：sub(char s1,char s2,char t); 參數(shù)：s1： 被減數(shù)，用字符串表示，位數(shù)不限

10、s2： 減數(shù)，用字符串表示，位數(shù)不限t： 結(jié)果，用字符串表示返回值： null注意：默認(rèn)s1>=s2，程序未處理負(fù)數(shù)情況 需要 string.h源程序：void sub(char s1,char s2,char t) int i,l2,l1,k;l2=strlen(s2);l1=strlen(s1);tl1='0'l1-;for (i=l2-1;i>=0;i-,l1-)if (s1l1-s2i>=0)tl1=s1l1-s2i+'0'elsetl1=10+s1l1-s2i+'0's1l1-1=s1l1-1-1;k=l1;while

11、(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'goto loop;if (strlen(t)=0) t0='0't1='0' 6.任意進(jìn)制轉(zhuǎn)換語法：conversion(char s1,char s2,long d1,long d2);參數(shù)：s： 原進(jìn)制數(shù)字，用字符串表示s2： 轉(zhuǎn)換結(jié)果，用字符串表示d1： 原進(jìn)制

12、數(shù)d2： 需要轉(zhuǎn)換到的進(jìn)制數(shù)返回值： null注意：高于9的位數(shù)用大寫'A''Z'表示，216位進(jìn)制通過驗(yàn)證 源程序：void conversion(char s,char s2,long d1,long d2)long i,j,t,num;char c;num=0;for (i=0;si!='0'i+)if (si<='9'&&si>='0') t=si-'0' else t=si-'A'+10; num=num*d1+t;i=0;while(1)t=n

13、um%d2;if (t<=9) s2i=t+'0' else s2i=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'7.最大公約數(shù)、最小公倍數(shù)語法：resulet=hcf(int a,int b)、result=lcd(int a,int b) 參數(shù)：a： int a，求最大公約數(shù)或最小公倍數(shù)b： int b，求最大公約數(shù)或最小公倍數(shù)返回值： 返回最大公約數(shù)（hcf）或最小公倍數(shù)（lcd） 注意：lcd 需要

14、連同 hcf 使用源程序：int hcf(int a,int b)int r=0;while(b!=0)r=a%b;a=b;b=r;return(a);lcd(int u,int v,int h)return(u*v/h);8.組合序列語法：m_of_n(int m, int n1, int m1, int* a, int head) 參數(shù)：m： 組合數(shù)C的上參數(shù)n1： 組合數(shù)C的下參數(shù)m1： 組合數(shù)C的上參數(shù)，遞歸之用*a： 1n的整數(shù)序列數(shù)組head： 頭指針返回值： null注意：*a需要自行產(chǎn)生 初始調(diào)用時(shí)，m=m1、head=0 調(diào)用例子：求C(m,n)序列：m_of_n(m,n,m

15、,a,0); 源程序：void m_of_n(int m, int n1, int m1, int* a, int head)int i,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); / 遞歸調(diào)用t=ahead;ahead=an1-1+head;an1-1+head=t;m_of_n(m,n1-1,m1-1,a,head+1); /

16、 再次遞歸調(diào)用t=ahead;ahead=an1-1+head;an1-1+head=t;9.快速傅立葉變換（FFT）語法：kkfft(double pr,double pi,int n,int k,double fr,double fi,int l,int il);參數(shù)：prn： 輸入的實(shí)部pin： 數(shù)入的虛部n，k： 滿足n=2kfrn： 輸出的實(shí)部fin： 輸出的虛部l： 邏輯開關(guān)，0 FFT，1 ifFTil： 邏輯開關(guān)，0 輸出按實(shí)部/虛部；1 輸出按模/幅角返回值： null注意：需要 math.h源程序：void kkfft(pr,pi,n,k,fr,fi,l,il)int n,

17、k,l,il;double pr,pi,fr,fi;int it,m,is,i,j,nv,l0;double p,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=pr

18、i-1*pr1;q=pii-1*pi1;s=(pri-1+pii-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

19、+)p=prm*j*frit+j+nv/2;q=pim*j*fiit+j+nv/2;s=prm*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+

20、)pri=sqrt(fri*fri+fii*fii);if (fabs(fri)<0.000001*fabs(fii) if (fii*fri)>0) pii=90.0;else pii=-90.0;elsepii=atan(fii/fri)*360.0/6.283185306; return;10.Ronberg算法計(jì)算積分語法：result=integral(double a,double b);參數(shù)：a： 積分上限b： 積分下限functionf： 積分函數(shù)返回值： f在（a,b）之間的積分值注意：function f(x)需要自行修改，程序中用的是sina(x)/x 需要

21、math.h 默認(rèn)精度要求是1e-5源程序：double f(double x)return sin(x)/x; /在這里插入被積函數(shù)double integral(double a,double b)double h=b-a;double t1=(1+f(b)*h/2.0; int k=1;double r1,r2,s1,s2,c1,c2,t2; loop:double s=0.0;double x=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;

22、 goto loop;c2=s2+(s2-s1)/15.0; if(k=2)c1=c2;k+;h/=2.0; t1=t2;s1=s2;goto loop;r2=c2+(c2-c1)/63.0; if(k=3)r1=r2; c1=c2;k+; h/=2.0;t1=t2;s1=s2;goto loop;while(fabs(1-r1/r2)>1e-5) r1=r2;c1=c2;k+; h/=2.0;t1=t2;s1=s2;goto loop;return r2;11.行列式計(jì)算語法：result=js(int s,int n)參數(shù)：s： 行列式存儲(chǔ)數(shù)組n： 行列式維數(shù)，遞歸用返回值： 行列式

23、值注意：函數(shù)中常數(shù)N為行列式維度，需自行定義源程序：int js(s,n)int sN,n;int z,j,k,r,total=0;int bNN;/*bNN用于存放，在矩陣sNN中元素s0的余子式*/if(n>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; else bjk=sj+1k;if(z%2=0) r=s0z*js(b,n-1); /*遞歸調(diào)用*/ else r=(-1)*s0z*js(b,n-1);total=total+r;else if(n=2)tot

24、al=s00*s11-s01*s10;return total;12.求排列組合數(shù)語法：result=P(long n,long m); / result=long C(long n,long m); 參數(shù)：m： 排列組合的上系數(shù)n： 排列組合的下系數(shù)返回值： 排列組合數(shù)注意：符合數(shù)學(xué)規(guī)則：m<n源程序：long P(long n,long m)long p=1;while(m!=0)p*=n;n-;m-;return p;long C(long n,long m)long i,c=1;i=m;while(i!=0)c*=n;n-;i-;while(m!=0)c/=m;m-;return

25、 c;二、字符串處理1.字符串替換語法：replace(char str,char key,char swap);參數(shù)：str： 在此源字符串進(jìn)行替換操作key： 被替換的字符串，不能為空串swap： 替換的字符串，可以為空串，為空串表示在源字符中刪除key 返回值： null注意：默認(rèn)str長(zhǎng)度小于1000，如否，重新設(shè)定設(shè)定tmp大小 需要 string.h源程序：void replace(char str,char key,char swap)int l1,l2,l3,i,j,flag;char tmp1000;l1=strlen(str);l2=strlen(key);l3=strle

26、n(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,&stri+l2);strcpy(str,tmp);i+=l3-1;l1=strlen(str);2.字符串查找語法：result=strfind(char str,char key);參數(shù)：str： 在此源字符串進(jìn)行查找操作key： 被查找的字符串，不能為空串返回值： 如果

27、查找成功，返回key在str中第一次出現(xiàn)的位置，否則返回-1 注意：需要 string.h源程序：int strfind(char str,char key)int l1,l2,i,j,flag;l1=strlen(str);l2=strlen(key);for (i=0;i<=l1-l2;i+)flag=1;for (j=0;j<l2;j+)if (stri+j!=keyj) flag=0;break;if (flag) return i;return -1;3.字符串截取語法：mid(char str,int start,int len,char strback) 參數(shù)：str

28、： 操作的目標(biāo)字符串start： 從第start個(gè)字符串開始，截取長(zhǎng)度為len的字符 len： 從第start個(gè)字符串開始，截取長(zhǎng)度為len的字符 strback： 截取的到的字符返回值： 0：超出字符串長(zhǎng)度，截取失敗；1：截取成功 注意：源程序： 需要 string.hint mid(char str,int start,int len,char strback) int l,i,k=0;l=strlen(str);if (start+len>l) return 0;for (i=start;i<start+len;i+)strbackk+=stri;strbackk='

29、0'return 1;三、計(jì)算幾何1.叉乘法求任意多邊形面積語法：result=polygonarea(Point *polygon,int N); 參數(shù)：*polygon： 多變形頂點(diǎn)數(shù)組N： 多邊形頂點(diǎn)數(shù)目返回值： 多邊形面積注意：支持任意多邊形，凹、凸皆可 多邊形頂點(diǎn)輸入時(shí)按順時(shí)針順序排列源程序：typedef struct double x,y; Point;double polygonarea(Point *polygon,int N)int i,j;double area = 0;for (i=0;i<N;i+) j = (i + 1) % N;area += pol

30、ygoni.x * polygonj.y;area -= polygoni.y * polygonj.x;area /= 2;return(area < 0 ? -area : area);2.求三角形面積語法：result=area3(float x1,float y1,float x2,float y2,float x3,float y3); 參數(shù)：x13： 三角形3個(gè)頂點(diǎn)x坐標(biāo)y13： 三角形3個(gè)頂點(diǎn)y坐標(biāo)返回值： 三角形面積注意：需要 math.h源程序：float area3(float x1,float y1,float x2,float y2,float x3,float

31、y3) float a,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);return s;3.兩矢量間角度語法：result=angle(double x1, double y1, double x2, double y2); 參數(shù)：x/y12： 兩矢量的坐標(biāo)返回值： 兩的角度矢量注意：返回角度為弧度制，并且以逆時(shí)針方向?yàn)檎?/p>

32、方向 需要 math.h源程序：#define PI 3.1415926double angle(double x1, double y1, double x2, double y2) double dtheta,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);4.兩點(diǎn)距離（2D、3D）語法：resu

33、lt=distance_2d(float x1,float x2,float y1,float y2); 參數(shù)：x/y/z1各點(diǎn)的x、y、z坐標(biāo) 2：返回值： 兩點(diǎn)之間的距離注意：需要 math.h源程序：float distance_2d(float x1,float x2,float y1,float y2) return(sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);float distance_3d(float x1,float x2,float y1,float y2,float z1,float z2)return(sqrt(x1-x2)*(x1-x2)+

34、(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2); 5.射向法判斷點(diǎn)是否在多邊形內(nèi)部語法：result=insidepolygon(Point *polygon,int N,Point p); 參數(shù)：*polygon： 多邊形頂點(diǎn)數(shù)組N： 多邊形頂點(diǎn)個(gè)數(shù)p： 被判斷點(diǎn)返回值： 0：點(diǎn)在多邊形內(nèi)部；1：點(diǎn)在多邊形外部注意：若p點(diǎn)在多邊形頂點(diǎn)或者邊上，返回值不確定，需另行判斷 需要 math.h源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct double

35、x,y; Point;int insidepolygon(Point *polygon,int N,Point p)int counter = 0;int i;double xinters;Point p1,p2;p1 = 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.

36、y-p1.y)+p1.x;if (p1.x = p2.x | p.x <= xinters) counter+;p1 = p2;if (counter % 2 = 0)return(OUTSIDE);elsereturn(INSIDE);6.判斷點(diǎn)是否在線段上語法：result=Pointonline(Point p1,Point p2,Point p);參數(shù)：p1、p2： 線段的兩個(gè)端點(diǎn)p： 被判斷點(diǎn)返回值： 0：點(diǎn)在不在線段上；1：點(diǎn)在線段上注意：若p線段端點(diǎn)上返回1 需要 math.h源程序：#define MIN(x,y) (x < y ? x : y)#define MA

37、X(x,y) (x > y ? x : y)typedef struct double x,y; Point;int FC(double x1,double x2)if (x1-x2<0.000002&&x1-x2>-0.000002) return 1; else return 0; int Pointonline(Point p1,Point p2,Point p)double x1,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) ret

38、urn 0;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) return 1; else return 0;7.判斷兩線段是否相交語法：result=sectintersect(Point p1,Point p2,Point p3,Point p4); 參數(shù)：p1兩條線段的四個(gè)端點(diǎn)4：返回0：兩線段不相交；1：兩線段相交；2兩線段首尾相接值：注 意：源程 p1!=p2;p3!=p4;序：#defi

39、ne MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct double x,y; Point;int lineintersect(Point p1,Point p2,Point p3,Point p4)Point tp1,tp2,tp3;if(p1.x=p3.x&&p1.y=p3.y)|(p1.x=p4.x&&p1.y=p4.y)|(p2.x=p3.x&&p2.y=p3.y)|(p2.x=p4.x&&p2.y=p4.y)retur

40、n 2;/快速排斥試驗(yàn)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)<p3.y<MAX(p1.y,p2.y);else return 0;/跨立試驗(yàn)tp1.x=p1.x-p3.x;tp1.y=p1.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=

41、p4.y-p3.y;tp3.x=p2.x-p3.x;tp3.y=p2.y-p3.y;8.判斷線段與直線是否相交語法：result=lineintersect(Point p1,Point p2,Point p3,Point p4);參數(shù)：p1、p2： 線段的兩個(gè)端點(diǎn)p3、p4： 直線上的兩個(gè)點(diǎn)返回值： 0：線段直線不相交；1：線段和直線相交注意：如線段在直線上，返回 1源程序：typedef struct double x,y; Point;int lineintersect(Point p1,Point p2,Point p3,Point p4)Point tp1,tp2,tp3;tp1.x

42、=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;9.點(diǎn)到線段最短距離語法：result=mindistance(Point p1,Point p2,Point q);參數(shù)：p1、線段的兩個(gè)端點(diǎn) p2：q： 判斷點(diǎn)返回點(diǎn)q到線段p1p2的距離值：注 意：源程 需要 math.h序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct double x

43、,y; Point;double mindistance(Point p1,Point p2,Point q)int flag=1;double k;Point s;if (p1.x=p2.x) s.x=p1.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<

44、;=MAX(p1.x,p2.x)return sqrt(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.y-p1.y)*(q.y-p1.y),sqrt(q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y);10.求兩直線的交點(diǎn)語法：result=mindistance(Point p1,Point p2,Point q);參數(shù)：p1直線上不相同的兩點(diǎn)p4：*p： 通過指針返回結(jié)果返回1：兩直線相交；2：兩直線平行值：注 意：源程 如需要判斷兩線段交

45、點(diǎn)，檢驗(yàn)k和對(duì)應(yīng)k1（注釋中）的值是否在01之間，用在01之間的那個(gè)求交點(diǎn)序：typedef struct double x,y; Point;int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p)double k;/同一直線if (p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)=0&&(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)=0) return 2;/平行，不同一直線if (p4.y-p3.y)*(p2.x-p1.

46、x)-(p4.x-p3.x)*(p2.y-p1.y)=0) return 0;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)*(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);return 1;/有

47、交點(diǎn)11.判斷一個(gè)封閉圖形是凹集還是凸集語法：result=convex(Point *p,int n);參數(shù)：*p： 封閉曲線頂點(diǎn)數(shù)組n： 封閉曲線頂點(diǎn)個(gè)數(shù)返回值： 1：凸集；-1：凹集；0：曲線不符合要求無法計(jì)算注意：默認(rèn)曲線為簡(jiǎn)單曲線：無交叉、無圈源程序：typedef struct double x,y; Point;int convex(Point *p,int n)int i,j,k;int flag = 0;double z;if (n < 3)return(0);for (i=0;i<n;i+) j = (i + 1) % n;k = (i + 2) % n;z =

48、 (pj.x - pi.x) * (pk.y - pj.y);z -= (pj.y - pi.y) * (pk.x - pj.x);if (z < 0)flag |= 1;else if (z > 0)flag |= 2;if (flag = 3)return 1; /CONCAVEif (flag != 0)return 1; /CONVEXelsereturn 0;12.Graham掃描法尋找凸包語法：Graham_scan(Point PointSet,Point ch,int n,int &len); 參數(shù)：PointSet輸入的點(diǎn)集 ：ch： 輸出的凸包上的點(diǎn)集，

49、按照逆時(shí)針方向排列n： PointSet中的點(diǎn)的數(shù)目len： 輸出的凸包上的點(diǎn)的個(gè)數(shù)返回值： null源程序：struct Pointfloat x,y;float multiply(Point p1,Point p2,Point p0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);float distance(Point p1,Point p2)return(sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);void Graham_scan(Point PointSet,Poi

50、nt ch,int n,int &len)int i,j,k=0,top=2;Point tmp;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 (j=i+1;j<n;j+)if ( (multiply(PointSetj,PointSetk,Po

51、intSet0)>0) |(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+)while (multiply(PointSeti,chtop,chtop-1)>=0) top-;

52、 ch+top=PointSeti;len=top+1;四、數(shù)論1.x的二進(jìn)制長(zhǎng)度語法：result=BitLength(int x);參數(shù)：x： 測(cè)長(zhǎng)的x返回值： x的二進(jìn)制長(zhǎng)度源程序：int BitLength(int x)int d = 0;while (x > 0) x >>= 1;d+;return d;2.返回x的二進(jìn)制表示中從低到高的第i位語法：result=BitAt(int x, int i);參數(shù)：x： 十進(jìn)制 xi： 要求二進(jìn)制的第i位返回值： 返回x的二進(jìn)制表示中從低到高的第i位 注意：最低位為第一位源程序：int BitAt(int x, int i)return ( x & (1 << (i-1) );3.模取冪運(yùn)算語法：result=Modular_Expoent(int a,int b,int n); 參數(shù)：a、b、n： ab mod n 的對(duì)應(yīng)參數(shù)返回值： ab mod n 的值注意：需要BitLength和BitAt源程序：int Modular_Expoent(int a,int b,int n)int i, y=1;for (i = BitLength(b)