ACM小組預定函Ver2.0by

快速變換（FFT）10.Ronberg算法計算積分11.行列式計

段

Graham凸

從低到高的第i

Dijkstra3.Bellman-ford4.Floyd

2.排 2.順序 5.二叉語法：intresult=factorial(intn：n的階返回值本程序直接輸出n!的結果，需要返回結果請保留long需要源程序intfactorial(int{longa[10000];inti,j,l,c,m=0,w;{}if(c>0)}for(i=m-1;i>=0;i--)printf("%4.4ld",a[i]);returnw;}語法：mult(charc[],chart[],intm：限定10返回值：null需要源程序voidmult(charc[],chart[],int{inti,l,k,flag,add=0;chars[100];forfor{}if(flag){l=i+1;s[i]=add;}elsefor}語法：mult(chara[],charb[],chara[]：b[]：乘數(shù)，用字符串表示，位數(shù)不限t[]：結果，用字符串表示返回值空間復雜度為需要源程序voidmult(chara[],charb[],char{inti,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;charresult[65];forfor(j=0;j<blen;j++)res[i][j]=(a[i]-'0')*(b[j]-for(i=alen-1;i>=0;i--{}for(i=blen-2;i>=0;i--{for(j=0;j<=i;j++)sum=sum+res[i-j][j];}if(sum!=0)for(i=0;i<k;i++)for(i=k-1;i>=0;i--)s[i]=result[k-1-i];{if(strlen(s)!=strlen(a)&&s[0]=='0')}}

}}語法：add(chara[],charb[],chara[]：b[]：乘數(shù)，用字符串表示，位數(shù)不限t[]：結果，用字符串表示返回值空間復雜度為需要源程序voidadd(chara[],charb[],char{inti,j,k,up,x,y,z,l;char*c;c=(char*)malloc(l*sizeof(char));{if(i<0)x='0';elseif(j<0)y='0';elseif(up)if(z>9){up=1;z%=10;}elseup=0;}if(up)c[k++]='1';語法：sub(chars1[],chars2[],chars1[s2[]：減數(shù)，用字符串表示，位數(shù)不限t[]：結果，用字符串表示返回值默認s1>=s2，程序未處理負數(shù)情況需要string.h源程序voidsub(chars1[],chars2[],char{inti,l2,l1,k;for(i=l2-1;i>=0;i--,l1--{if(s1[l1]-

}

{}

while(s1[k]<0){s1[k]+=10;s1[k-1]-=1;k--while(l1>=0){t[l1]=s1[l1];l1--if{for(i=0;i<l1-1;i++)t[i]=t[i+1];goto}if(strlen(t)==0)語法：conversion(chars1[],chars2[],longd1,longd1：制d2：返回值：null源程序voidconversion(chars[],chars2[],longd1,long{longi,j,t,num;charc;for{}}

{if(t<=9)s2[i]=t+'0';elses2[i]=t+'A'-10;if(num==0)break;}for語法：resulet=hcf(inta,intb)、result=lcd(inta,inta：inta，求最大公約數(shù)或最小公倍數(shù)b：intb返回值數(shù)（hcf）或最小公倍數(shù)（lcd）lcd連同hcf源程序inthcf(inta,int{intr=0;{}}lcd(intu,intv,int{}語法：m_of_n(intm,intn1,intm1,int*a,intm：合數(shù)C參n1：合數(shù)C參m1：合數(shù)C*a：1～n數(shù)head返回值：null*a產源程序voidm_of_n(intm,intn1,intm1,int*a,int{intif(m1<0||m1>n1)}快速變換

{for(i=0;i<m;icout<<a[i]<序}m_of_n(m,n1-1,m1,a,head);//遞歸調用m_of_n(m,n1-1,m1-1,a,head+1);//再次遞歸調用pr[npi[nn，k：滿足n=2^kfr[nfi[nl：，0FFT，1il：，0部/虛部；1返回值null需要voidkkfft(pr,pi,n,k,fr,fi,l,il)intn,k,l,il;double{intdoublep,q,s,vr,vi,poddr,poddi;for(it=0;it<=n-1;it++){m=it;for(i=0;i<=k-1;{j=m/2;is=2*is+(m-2*j);m=j;}fr[it]=pr[is];fi[it]=pi[is];}pr[0]=1.0;pi[0]=0.0;pr[1]=cos(p);pi[1]=-if(l!=0)pi[1]=-pi[1];for(i=2;i<=n-1;i++){p=pr[i-q=pi[i-pr[i]=p-q;pi[i]=s-p-q;}for(it=0;it<=n-2;{vr=fr[it];fr[it]=vr+fr[it+1];fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1];fi[it+1]=vi-fi[it+1];}m=n/2;for(l0=k-2;l0>=0;l0--{m=m/2;for(it=0;it<=(m-1)*nv;it=it+nv)for(j=0;j<=(nv/2)-1;{poddr=p-q;poddi=s-p-q;}}iffor(i=0;i<=n-1;{if

}for(i=0;i<=n-1;{if{if((fi[i]*fr[i])>0)pi[i]=90.0;elsepi[i]=-90.0;}}

}

Ronberg積語法：result=integral(doublea,doublea：上b：下

積分函返回值f（a,b）之間的積分值functionf(x)需要自行修改，程序中用的是需要默認精度要求是1e-源程序doublef(double{returnsin(x)/x;//在這里被積函}doubleintegral(doublea,double{doubleh=b-double

intdoubledoubles=0.0;doublex=a+h/2.0;{}{gotoloop;gotoloop;r1=r2;c1=c2;k++;gotoloop;}gotoloop;}return}語法：result=js(ints[][],ints[][]：行列式數(shù)n：返回值：行列式值函數(shù)中常數(shù)N定源程序intjs(s,n)ints[][N],n;{子式

int{{}else

elser=(-1)*s[0][z]*js(b,n-1);}return}語法：result=P(longn,longmresult=longC(longn,longm：系n：返回值：排列組合數(shù)源程序longP(longn,long{longp=1;returnp;}longC(longn,long{longi,c=1;returnc;}語法：replace(charstr[],charkey[],char返回值默認str1000，如否，重新設定設定tmp需要string.h源程序voidreplace(charstr[],charkey[],char{intl1,l2,l3,i,j,flag;chartmp[1000];for(i=0;i<=l1-{forif(str[i+j]!=key[j]){flag=0;break;}if(flag){}}}語法：result=strfind(charstr[],char返回值返回keystr則返回-1需要源程序intstrfind(charstr[],char{intl1,l2,i,j,flag;for(i=0;i<=l1-{forif(str[i+j]!=key[j]){flag=0;break;}if(flag)returni;}return-}語法：mid(charstr[],intstart,intlen,charstr[符start第start長度為len字len：第start長度為len字strback[返回值0：超出字符串長度，截取失??；1：截取成功需要源程序intmid(charstr[],intstart,intlen,char{intl,i,k=0;if(start+len>l)return0;forreturn}語法：result=polygonarea(Point*polygon,intN：返回值：多邊形面積源程序typedefstructdouble}doublepolygonarea(Point*polygon,int{intdoublearea=for(i=0;i<N;i++)j=(i+1)%area+=polygon[i].x*polygon[j].y;area-=polygon[i].y*}area/=return(area<0?-area:}語法：result=area3(floatx1,floaty1,floatx2,floaty2,floatx3,floatx1～3：三角形3個頂點xy1～3角形3頂點y標返回值：三角形面積需要源程序{floatreturns;}語法：result=angle(doublex1,doubley1,doublex2,double返回值：兩的角度矢量需要math.h源程序#definePIdoubleangle(doublex1,doubley1,doublex2,double{}

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;語法：resuistance_2d(floatx1,floatx2,floaty1,float

各點的x、y、z返回值需要源程序floatdistance_2d(floatx1,floatx2,floaty1,float{}{}語法：result=insidepolygon(Point*polygon,intN,Point*polygonN：p：被判斷點返回值：0：點在多邊形；1：點在多邊形外部若p需要math.h源程序#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:typedefstructdouble}intinsidepolygon(Point*polygon,intN,Point{intcounter=0;inti;doublePointp1=for(i=1;i<=N;i++)p2=polygon[i%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){xintersp.x<=}}}p1=

}}if(counter%2==} 段

語法：result=Pointonline(Pointp1,Pointp2,Point

p：斷返0：點在不段上；1：點段值若p上返回需要#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:typedefstruct{doublex,y;}intFC(doublex1,double{}intPointonline(Pointp1,Pointp2,Point{}

doublex1,y1,x2,y2;if(FC(x1*y2-x2*y1,0)==0)returnifreturn1;elsereturn0;語法：result=sectintersect(Pointp1,Pointp2,Pointp3,Point~返0：兩線段不相交；1：兩線段相交；2段首尾相接#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:typedefstructdouble}intlineintersect(Pointp1,Pointp2,Pointp3,Point{Pointtp1,tp2,tp3;return;elsereturn}語法：result=lineintersect(Pointp1,Pointp2,Pointp3,Point返回值0：線段直線不相交；1：線段和直線相交如線段在直線上，返回源程序typedefstructdouble}intlineintersect(Pointp1,Pointp2,Pointp3,Point{Pointtp1,tp2,tp3;return1;elsereturn0;}語法：result=mindistance(Pointp1,Pointp2,Point

q：返回點q線段p1p2需要#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:typedefstructdouble}doublemindistance(Pointp1,Pointp2,Point{intflag=1;doublek;Points;if(p1.x==p2.x)if(p1.y==p2.y){s.x=q.x;s.y=p1.y;flag=0;}if(flag){}if}語法：result=mindistance(Pointp1,Pointp2,Point~1：兩直線相交；2：兩直線平行如需要判斷兩線段交點，檢驗k對應k1（注釋中）的值是否0～1之間，用在0～1之間的那typedefstructdouble}intlinecorss(Pointp1,Pointp2,Pointp3,Pointp4,Point{doubleif((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0)returnif((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0)return*(p2.y-return1;//有交點}語法：result=convex(Point*p,int*p：數(shù)n：個返回值1：凸集；-1：凹集；0：曲線不符合要求無法計算源程序typedefstructdouble}intconvex(Point*p,int{inti,j,k;intflag=0;doublez;if(n<for(i=0;i<n;i++)j=(i+1)%k=(i+2)%z=(p[j].x-p[i].x)*(p[k].y-z-=(p[j].y-p[i].y)*(p[k].x-p[j].x);if(z<0)flag|=1;elseif(z>0)flag|=2;if(flag==3)return－1;}if(flag!=return1;}

return0;語法：Graham_scan(PointPointSet[],Pointch[],intn,int

len：返回值null源程序structfloatfloatmultiply(Pointp1,Pointp2,Point{}floatdistance(Pointp1,Point{}voidGraham_scan(PointPointSet[],Pointch[],intn,int{inti,j,k=0,top=2;Pointtmp;for(i=1;i<n-{forif((multiply(PointSet[j],PointSet[k],PointSet[0])>0)|| }for(i=3;i<n;i++){while(multiply(PointSet[i],ch[top],ch[top-1])>=0)top--;}}1.x長語法：result=BitLength(intx：長的返回值x二進制長度intBitLength(int{intd=while(x>0)x>>=1;}return}返回x高的第i語法：result=BitAt(intx,intx：i：制的第i返回值：返回xi源程序intBitAt(intx,int{return(x&(1<<(i-1))}語法：result=Modular_Expoent(inta,intb,inta、b、n：a^bmodn返回值：a^bmodn的值需要BitLength源程序intModular_Expoent(inta,intb,int{inti,for(i=BitLength(b);i>0;i--{y=if(BitAt(b,i)>y=}return}語法：result＝modular_equation(inta,intb,inta、b、n：ax=b(modn)返回值：方程的解源程序intext_euclid(inta,intb,int&x,int //求{intif(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);returnd;}voidmodular_equation(inta,intb,int{inte,i,d;intx,y;if(b%d>0)printf("No

{forprintf("The%dthis:}}語法：result=Modular_Expoent(inta,intb,intB[]、W[]a=B[](modW返回值：a的值其中W[],B[]已知，W[i]>0W[iW[j]互質,求源程序intext_euclid(inta,intb,int&x,int //求{intif(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);returnd;}intChina(intB[],intW[],int{intintd,x,y,a=0,m,n=1;for(i=0;i<k;i++)for{}if(a>0)returna;elsereturn(a+n);}語法：result=prime(inta[],intn：產生n放入a[]中返回值：n內素數(shù)的個數(shù)其中W[],B[]已知，W[i]>0W[iW[j]互質,求源程序intprime(inta[],int{inti,j,k,x,num,*b;b=(int*)malloc(sizeof(int)*(n+1)*2);{{}

}return p(intn：判斷n返回值返回1，否則返回源程序intcomp(int{intforif(n%i==0)if(flag==1)return1;elsereturn}Prim成語法：prim(GraphG,intvcount,intfather[返回值：null常數(shù)max_vertexes常數(shù)infinity窮大源程序#defineinfinity#definemax_vertexestypedefintGraph[max_vertexes][max_vertexes];voidprim(GraphG,intvcount,intfather[]){inti,j,k;for(i=0;i<vcount;i++){}forwhile(used[j])j++;for(k=0;k<vcount;k++)forif{lowcost[k]=G[j][k];closeset[k]=j;}}}語法：resuijkstra(GraphG,intn,ints,intt,intn：s：開始節(jié)點t：目標節(jié)點path返回值：最短路徑長度頂點標號從0始while{}源程序intDijkstra(GraphG,intn,ints,intt,int{inti,j,w,minc,d[max_vertexes],mark[max_vertexes];for(i=0;i<n;i++)mark[i]=0;for{path[i]=s;}for{forfor(j=0;j<n;j++){d[j]=d[w]+G[w][j];path[j]=w;}}return}n：s：開始節(jié)點t：目標節(jié)點success：返回值：最短路徑長度頂點標號從0while{}源程序{intfor(i=0;i<n;i++){d[i]=infinity;path[i]=0;}forforforifforforif(d[j]>d[i]+G[i][j])returnreturnd[t];}語法：Floyd_Washall(GraphG,intn,GraphD,GraphG：n：個D：D[i,j]表示從ij距P：P[i,j]表示從ij路徑上j返值voidFloyd_Washall(GraphG,intn,GraphD,Graph{intforfor{P[i][j]=i;for(i=0;i<n;i++){D[i][i]=0;P[i][i]=0;forforforif{P[i][j]=P[k][j];}語法：quicksort(intl,intr,intl：始時r：始時r=數(shù)組元素個數(shù)b[]：被排序的元素返回值源程序voidquicksort(intl,intr,int{inti,j,x;if(l>=r)return;{while(b[j]>x&&j>i)j--;{}}

}}語法：ssort(inta[],intn：個a[]：返值注voidssort(inta[],int{inti,j,g;inttemp,k;{{{}}

}

{}}語法：sort(intt[],intt[]：n：組t[]元素的個數(shù)返回值：null源程序voidsort(intt[],int{intfor{for(j=i;j<n;j++)if(t[j]<t[k])}}語法：result=search_bin(int*t,intt[]：返回值：如果kt[]中存在，輸出i：t[i]=k源程序intsearch_bin(int*t,int{intwhile{if(k==t[mid])returnmid;elseif(k<t[mid])high=mid-1;elselow=mid+1;}return-}源程序#definemaxsize100typedefstruct{intdata[maxsize];intfront;int}sintsqinit(sueue*p{return1;}intenqueue(sueue*q,inte)//入{return0;return1;}intdequeue(sueue*q)//出{intif(q->front==q-return0;returne;}intempty(sueue {intif(q->front==q->rear)return}intgethead(sueue {intif(q->front==q->rear)return}voiddisplay(sueue*q){intprintf("thesequeueisdisplay:\n");if(q->front==q->rear)printf("thesequeueis

{{printf("->%d",q->data[s]);}}}main(sueue {intn,i,m,x,y,select,xq;printf("createaemptysequeue\n");printf("pleaseinputthesequeuelength:\n");for{printf("pleaseinputasequeuevalue:\n");}printf("select1****enqueue()\n");printf("select2****dequeue()\n");printf("select3****empty()\n");printf("select4****gethead()\n");printf("select5****display()\n");printf("pleaseselect(1--5):");{casecasecase

printf("pleaseinputavalue:\n");}{}{casecase}}}

printf("thesequeueisprintf("thesequeueis}{printf("outputheadvalue:%d\n",y);}{}源程序#definem100typedefstruct{intstack[m];inttop;}init(stackstru*s*裝入棧{return}intpush(stackstru*s,intx)*入棧操作{if(s-printf("thestackis

{}}voiddisplay(stackstru*s*顯示棧所有數(shù)據(jù){printf("thestackis

{{}}}intpop(stackstru*s)*出棧操作并返回被刪除的那個記錄{intprintf("thestackis}

{returny;}intgettop(stackstru*s)/*得到棧頂數(shù){intreturnreturn}main(stackstru*p演{intn,i,k,h,x1,x2,select;printf("createaemptystack!\n");printf("inputastacklength:\n");{printf("inputastackvalue:\n");}printf("select1:display()\n");printf("select2:push()\n");printf("select3:pop()\n");printf("select4:gettop()\n");printf("inputayourselect(1-4):\n");{casecasecasecase}

}{printf("inputapushavalue:\n");}{}{}}源程序#definenulltypedefcharElemType/**/typedefstructLNode{ElemTypedata;structLNode*next;setnull(structLNode**p);intlength(structLNode**p);ElemTypeget(structLNode**p,intvoidinsert(structLNode**p,ElemTypex,inti);intdelete(structLNode**p,inti);voiddisplay(structLNode{

structLNode*head,*q*定義靜態(tài)變量*/intselect,x1,x2,x3,x4;inti,n;intm,g;charhead=setnull(&head);/*建議鏈表并設置為空表*/printf("請輸入數(shù)據(jù)長度:");{printf("將數(shù)據(jù)到單鏈表中:");insert(&head,y,i);}/*數(shù)據(jù)到鏈表*/display(&head);/*顯示鏈表所有數(shù)據(jù)*/printf("select1length()\n");printf("select2取結點get()\n");printf("select3查找locate()\n");printf("select4結點delete()\n");printf("inputyourselect:");{casecasecase}}

case}

{printf("請輸入要取得結點{printf("請輸入要查找的數(shù)據(jù){printf("請輸入要刪除的結點setnull(structLNode{}intlength(structLNode{intstructLNode*q=*p;while(q!=null)-}}ElemTypeget(structLNode**p,int{intstructLNode*q=*p;while{}}

intlocate(structLNode**p,ElemType{intstructLNodewhile(q!=null&&q-{}}

voidinsert(structLNode**p,ElemTypex,int{intstructLNodes=(structLNode*)malloc(sizeof(structLNode));{}{{}{}}}

intdelete(structLNode**p,int{intstructLNode*q=*p,*t;{}

{{}{}}}

voiddisplay(structLNode{structLNode*q;printf("單鏈表顯示elseif(q->next==null)

{{-}}}源程序#definenulltypedefstruct{intstructstacknode}stacklink;typedefstruct{stacklink*top;intstacksize;ini