2022年C语言常用代码 .pdf

《2022年C语言常用代码 .pdf》由会员分享，可在线阅读，更多相关《2022年C语言常用代码 .pdf（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include using namespace std;void fullxunhuan(int*a,int n)int t=0;int m1,m2;if(n%2!=0)n+;for(int i=0;in%2;i+)for(m1=i,m2=n-i-1;m1i;m2-)am1m2=t%n+1;t+;for(;m1i;m1-)am1m2=t%n+1;t+;for(;m2n-i-1;m2+)am1m2=t%n+1;t+;void print(int*a,int n)for(int i=0;in;i+)for(int j=0;jn;j+)coutaijt;coutn;void main()int*a

2、;int n;cout 请输入 Nn;a=new int*n;/申请一个N 行 N 列的数组for(int i1=0;i1n;i1+)ai1=new intn;for(int i=0;in;i+)/给数组初始化 for(int j=0;jn;j+)aij=0;fullxunhuan(a,n);print(a,n);名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 28 页 -ACM 小组内部预定函数数学问题：1.精度计算大数阶乘2.精度计算乘法（大数乘小数）3.精度计算乘法（大数乘大数）4.精度计算加法5.精度计算减法6.任意进制转换7.最大公约数、最小公倍数8.组合序列9.快速傅

3、立叶变换（FFT）10.Ronberg算法计算积分11.行列式计算12.求排列组合数字符串处理：1.字符串替换2.字符串查找3.字符串截取计算几何：1.叉乘法求任意多边形面积2.求三角形面积3.两矢量间角度4.两点距离（2D、3D）5.射向法判断点是否在多边形内部6.判断点是否在线段上7.判断两线段是否相交8.判断线段与直线是否相交9.点到线段最短距离10.求两直线的交点11.判断一个封闭图形是凹集还是凸集12.Graham扫描法寻找凸包数论：1.x的二进制长度2.返回 x 的二进制表示中从低到高的第i 位3.模取幂运算4.求解模线性方程5.求解模线性方程组(中国余数定理)6.筛法素数产生器7

4、.判断一个数是否素数图论：1.Prim 算法求最小生成树2.Dijkstra 算法求单源最短路径3.Bellman-ford 算法求单源最短路径4.Floyd 算法求每对节点间最短路径排序/查找：1.快速排序2.希尔排序3.选择法排序4.二分查找数据结构：1.顺序队列2.顺序栈3.链表4.链栈5.二叉树一、数学问题1.精度计算大数阶乘语法：int result=factorial(int n);参数：n：n 的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留 long a 需要 math.h 源程序：int factorial(int n)long a10000;i

5、nt i,j,l,c,m=0,w;a0=1;for(i=1;i=n;i+)c=0;for(j=0;j0)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.精度计算乘法（大数乘小数）语法：mult(char c,char t,int m);参数：c：被乘数，用字符串表示，位数不限t：结果，用字符串表示m：乘数，限定10 以内返回值：null 注意：需要string.h 源程序：void mult(char c,char t,int m)int i,l,k,flag,add

6、=0;char s100;l=strlen(c);for(i=0;il;i+)sl-i-1=ci-0;for(i=0;i=10)si=k%10;add=k/10;flag=1;else si=k;flag=0;add=0;if(flag)l=i+1;si=add;else l=i;for(i=0;il;i+)tl-1-i=si+0;tl=0;3.精度计算乘法（大数乘大数）语法：mult(char a,char b,char s);参数：a：被乘数，用字符串表示，位数不限b：乘数，用字符串表示，位数不限t：结果，用字符串表示返回值：null 注意：空间复杂度为o(n2)需要string.h 源程

7、序：void mult(char a,char b,char s)int i,j,k=0,alen,blen,sum=0,res6565=0,flag=0;char result65;alen=strlen(a);blen=strlen(b);for(i=0;ialen;i+)for(j=0;j=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

8、;sum=sum/10;if(sum!=0)resultk=sum;k=k+1;for(i=0;i=0;i-)si=resultk-1-i;sk=0;while(1)if(strlen(s)!=strlen(a)&s0=0)strcpy(s,s+1);名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 28 页 -else break;4.精度计算加法语法：add(char a,char b,char s);参数：a：被乘数，用字符串表示，位数不限b：乘数，用字符串表示，位数不限t：结果，用字符串表示返回值：null 注意：空间复杂度为o(n2)需要string.h 源程序：void

9、 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(i0)x=0;else x=ai;if(j9)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

10、;backi=0;5.精度计算减法语法：sub(char s1,char s2,char t);参数：s1：被减数，用字符串表示，位数不限s2：减数，用字符串表示，位数不限t：结果，用字符串表示返回值：null 注意：默认 s1=s2，程序未处理负数情况需要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;else tl1=10+s1l1-s2i+0;

11、s1l1-1=s1l1-1-1;k=l1;while(s1k=0)tl1=s1l1;l1-;loop:if(t0=0)l1=strlen(s1);for(i=0;il1-1;i+)ti=ti+1;tl1-1=0;goto loop;if(strlen(t)=0)t0=0;t1=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 28 页 -6.任意进制转换语 法：conversion(char s1,char s2,long d1,long d2);参数：s：原进制数字，用字符串表示s2：转换结果，用字符串表示d1：原进制数d2：需要转换到的进制数返回值：null 注意：高于 9

12、 的位数用大写A Z表示，216 位进制通过验证源程序：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=0)t=si-0;else t=si-A+10;num=num*d1+t;i=0;while(1)t=num%d2;if(t=9)s2i=t+0;else s2i=t+A-10;num/=d2;if(num=0)break;i+;for(j=0;ji/2;j+)c=s2j;s2j=si-j;s2i-j=c;s2i+1=0;7.最大公约数、最小公倍

13、数语法：resulet=hcf(int a,int b)、result=lcd(int a,int b)参数：a：int a，求最大公约数或最小公倍数b：int b，求最大公约数或最小公倍数返回值：返回最大公约数（hcf）或最小公倍数（lcd）注意：lcd 需要连同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)参数：m：组合

14、数 C 的上参数n1：组合数 C 的下参数m1：组合数 C 的上参数，递归之用*a：1n 的整数序列数组head：头指针返回值：null 注意：*a 需要自行产生初始调用时，m=m1、head=0 调 用 例 子：求C(m,n)序 列：m_of_n(m,n,m,a,0);源程序：void m_of_n(int m,int n1,int m1,int*a,int head)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 28 页 -int i,t;if(m1n1)return;if(m1=n1)for(i=0;im;i+)coutai;/输出序列coutn;return;m_of_

15、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,a,head+1);/再次递归调用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);参数：prn：输入的实部pin：数入的虚部n，k：满足 n=2k frn：输出的实部fin：输出的虚部l：逻辑开关，0 FFT，1 ifFT il

16、：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回值：null 注意：需要 math.h 源程序：void kkfft(pr,pi,n,k,fr,fi,l,il)int n,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);

17、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+pii-1)*(pr1+pi1);pri=p-q;pii=s-p-q;for(it=0;it=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*j+pim*j;s=s*(frit+j+nv/2+fiit+j+nv/2);poddr=p

18、-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;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 28 页 -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)pii=90.0;else pii=-90.0;else pii=at

19、an(fii/fri)*360.0/6.283185306;return;10.Ronberg算法计算积分语法：result=integral(double a,double b);参数：a：积分上限b：积分下限function f：积分函数返回值：f 在（a,b）之间的积分值注意：function f(x)需要自行修改，程序中用的是 sina(x)/x 需要 math.h 默认精度要求是1e-5 源程序：double f(double x)return sin(x)/x;/在这里插入被积函数 double integral(double a,double b)double h=b-a;dou

20、ble 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(x1e-5)r1=r2;c1=c2;k+;h/=2.0;t1=t2;s1=s2;goto loop;return r2;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 28 页 -11.行列式计算语法：result=js(int s,int n)参数：s：行列式存储数组n：行列式维数，递归用返回值：行列式值注意：函数中常数N 为行列式维度，需自行定义源程序：int js(s,n)int

21、sN,n;int z,j,k,r,total=0;int bNN;/*bNN用于存放，在矩阵sNN 中元素 s0的余子式*/if(n2)for(z=0;zn;z+)for(j=0;jn-1;j+)for(k=0;k=z)bjk=sj+1k+1;else bjk=sj+1k;if(z%2=0)r=s0z*js(b,n-1);/*递归调用*/else r=(-1)*s0z*js(b,n-1);total=total+r;else if(n=2)total=s00*s11-s01*s10;return total;12.求排列组合数语法：result=P(long n,long m);/result

22、=long C(long n,long m);参数：m：排列组合的上系数n：排列组合的下系数返回值：排列组合数注意：符合数学规则：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 c;二、字符串处理1.字符串替换语法：replace(char str,char key,char swap);参数：str：在此源字符串进行替换操作key：被替换

23、的字符串，不能为空串swap：替换的字符串，可以为空串，为空串表示在源字符中删除key 返回值：null 注意：默认 str长度小于1000，如否，重新设定设定 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=strlen(swap);for(i=0;i=l1-l2;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 28 页 -flag=1;for(j=0;jl2;j

24、+)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);参数：str：在此源字符串进行查找操作key：被查找的字符串，不能为空串返回值：如果查找成功，返回 key在 str中第一次出现的位置，否则返回-1 注意：需要string.h 源程序：int strfind(char str,cha

25、r 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;jl)return 0;for(i=start;istart+len;i+)strbackk+=stri;strbackk=0;return 1;三、计算几何1.叉乘法求任意多边形面积语 法：result=polygonarea(Point*polygon,int N);参数：*polygon：多变形顶点数组N：多边形顶点数目返回值：多边形面积注意：支持任意多边形，凹、凸皆可多边形顶点输入时按顺时针顺序排列源程序：ty

26、pedef struct double x,y;Point;double polygonarea(Point*polygon,int N)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 28 页 -int i,j;double area=0;for(i=0;iN;i+)j=(i+1)%N;area+=polygoni.x*polygonj.y;area-=polygoni.y*polygonj.x;area/=2;return(area PI)dtheta-=PI*2;while(dtheta -PI)dtheta+=PI*2;return(dtheta);4.两点距离（2D、3

27、D）语法：result=distance_2d(float x1,float x2,float y1,float y2);参数：x/y/z1 2：各点的 x、y、z 坐标返回值：两点之间的距离注意：需要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)*

28、(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 28 页 -5.射向法判断点是否在多边形内部语法：result=insidepolygon(Point*polygon,int N,Point p);参数：*polygon：多边形顶点数组N：多边形顶点个数p：被判断点返回值：0：点在多边形内部；1：点在多边形外部注意：若 p 点在多边形顶点或者边上，返回值不确定，需另行判断需要 math.h 源程序：#define MIN(x,y)(x y?x:y)typedef struct double x,y;

29、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 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

30、(OUTSIDE);else return(INSIDE);6.判断点是否在线段上语法：result=Pointonline(Point p1,Point p2,Point p);参数：p1、p2：线段的两个端点p：被判断点返回值：0：点在不在线段上；1：点在线段上注意：若 p 线段端点上返回1 需要math.h 源程序：#define MIN(x,y)(x y?x:y)typedef struct double x,y;Point;int FC(double x1,double x2)if(x1-x2-0.000002)return 1;else return 0;int Pointonli

31、ne(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)return 0;if(MIN(p1.x,p2.x)=p.x&p.x=MAX(p1.x,p2.x)&名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 28 页 -(MIN(p1.y,p2.y)=p.y&p.y=MAX(p1.y,p2.y)return 1;else return 0;7.判断两线段是否相交语 法：result=sectinte

32、rsect(Point p1,Point p2,Point p3,Point p4);参数：p1 4：两条线段的四个端点返回值：0：两线段不相交；1：两线段相交；2 两线段首尾相接注意：p1!=p2;p3!=p4;源程序：#define MIN(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.

33、y=p3.y)|(p2.x=p4.x&p2.y=p4.y)return 2;/快速排斥试验if(MIN(p1.x,p2.x)p3.x&p3.xMAX(p1.x,p2.x)&MIN(p1.y,p2.y)p3.yMAX(p1.y,p2.y)|(MIN(p1.x,p2.x)p4.x&p3.xMAX(p1.x,p2.x)&MIN(p1.y,p2.y)p3.y=0)return 1;else return 0;8.判断线段与直线是否相交语 法：result=lineintersect(Point p1,Point p2,Point p3,Point p4);参数：p1、p2：线段的两个端点p3、p4：直

34、线上的两个点返回值：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=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

35、)=0)return 1;else return 0;9.点到线段最短距离语 法：result=mindistance(Point p1,Point p2,Point q);参数：p1、p2：线段的两个端点q：判断点返回值：点 q 到线段 p1p2 的距离注意：名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 28 页 -需要 math.h 源程序：#define MIN(x,y)(x y?x:y)typedef struct double x,y;Point;double mindistance(Point p1,Point p2,Point q)int flag=1;doub

36、le 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=MAX(p1.x,p2.x)return sqrt(q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y);else return MIN(sqrt(q.x-p

37、1.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.求两直线的交点语 法：result=mindistance(Point p1,Point p2,Point q);参数：p1 p4：直线上不相同的两点*p：通过指针返回结果返回值：1：两直线相交；2：两直线平行注意：如需要判断两线段交点，检验 k 和对应k1（注释中）的值是否在01 之间，用在 01 之间的那个求交点源程序：typedef struct double x,y;Point;int linecorss(Po

38、int 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.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)*(

39、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;/有交点 11.判断一个封闭图形是凹集还是凸集语法：result=convex(Point*p,int n);参数：*p：封闭曲线顶点数组n：封闭曲线顶点个数返回值：1：凸集；-1：凹集；0：曲线不符合要求无

40、法计算注意：默认曲线为简单曲线：无交叉、无圈源程序：名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 28 页 -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;in;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|=2;if(flag=3)return 1;/CONCAVE if

41、(flag!=0)return 1;/CONVEX else return 0;12.Graham扫描法寻找凸包语 法：Graham_scan(Point PointSet,Point ch,int n,int&len);参数：PointSet：输入的点集ch：输出的凸包上的点集，按照逆时针方向排列n：PointSet 中的点的数目len：输出的凸包上的点的个数返回值：null 源程序：struct Point float x,y;float multiply(Point p1,Point p2,Point p0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x

42、)*(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,Point ch,int n,int&len)int i,j,k=0,top=2;Point tmp;for(i=1;in;i+)if(PointSeti.yPointSetk.y)|(PointSeti.y=PointSetk.y)&(PointSeti.xPointSetk.x)k=i;tmp=PointSet0;Po

43、intSet0=PointSetk;PointSetk=tmp;for(i=1;in-1;i+)k=i;for(j=i+1;j0)|(multiply(PointSetj,PointSetk,PointSet0)=0)&(distance(PointSet0,PointSetj)distance(PointSet0,PointSetk)k=j;tmp=PointSeti;PointSeti=PointSetk;PointSetk=tmp;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 28 页 -ch0=PointSet0;ch1=PointSet1;ch2=PointSet2

44、;for(i=3;i=0)top-;ch+top=PointSeti;len=top+1;四、数论1.x的二进制长度语法：result=BitLength(int x);参数：x：测长的 x 返回值：x 的二进制长度源程序：int BitLength(int x)int d=0;while(x 0)x=1;d+;return d;2.返回 x 的二进制表示中从低到高的第i 位语法：result=BitAt(int x,int i);参数：x：十进制x i：要求二进制的第i 位返回值：返回 x的二进制表示中从低到高的第 i 位注意：最低位为第一位源程序：int BitAt(int x,int i

45、)return(x&(1 0;i-)y=(y*y)%n;if(BitAt(b,i)0)y=(y*a)%n;return y;4.求解模线性方程语法：resultmodular_equation(int a,int b,int n);参数：a、b、n：ax=b(mod n)的对应参数返回值：方程的解源程序：int ext_euclid(int a,int b,int&x,int&y)/求 gcd(a,b)=ax+by int t,d;if(b=0)x=1;y=0;return a;d=ext_euclid(b,a%b,x,y);t=x;x=y;y=t-a/b*y;return d;名师资料总结-

46、精品资料欢迎下载-名师精心整理-第 15 页，共 28 页 -void modular_equation(int a,int b,int n)int e,i,d;int x,y;d=ext_euclid(a,n,x,y);if(b%d0)printf(No answer!n);else e=(x*(b/d)%n;for(i=0;i0 且 Wi与 Wj互质,求 a 源程序：int ext_euclid(int a,int b,int&x,int&y)/求 gcd(a,b)=ax+by int t,d;if(b=0)x=1;y=0;return a;d=ext_euclid(b,a%b,x,y);

47、t=x;x=y;y=t-a/b*y;return d;int China(int B,int W,int k)int i;int d,x,y,a=0,m,n=1;for(i=0;ik;i+)n*=Wi;for(i=0;i0)return a;else return(a+n);6.筛法素数产生器语法：result=prime(int a,int n);参数：a：用于返回素数的数组n：产生 n 以内的素数，按升序放入a中返回值：n 以内素数的个数注意：其中 W,B已知，Wi0 且 Wi与 Wj互质,求 a 源程序：int prime(int a,int n)int i,j,k,x,num,*b;n

48、+;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;j2;j+)x=2*(i+j)-1;while(bx=0)anum+=x;for(k=x;k=2*n;k+=x)bk=1;return num;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 28 页 -7.判断一个数是否素数语法：result=comp(int n);参数：n：判断 n 是否素数返回值：素数返回1，否则返回0 源程序：int comp(int n)in

49、t i,flag=1;for(i=2;i=sqrt(n);i+)if(n%i=0)flag=0;break;if(flag=1)return 1;else return 0;五、图论1.Prim 算法求最小生成树语法：prim(Graph G,int vcount,int father);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father：用来记录每个节点的父节点返回值：null 注意：常数 max_vertexes为图最大节点数常数 infinity 为无穷大源程序：#define infinity 1000000#define max_vertexes 5 typede

50、f int Graphmax_vertexesmax_vertexes;void prim(Graph G,int vcount,int father)int i,j,k;int lowcostmax_vertexes,closesetmax_vertexes,usedmax_vertexes;for(i=0;ivcount;i+)lowcosti=G0i;closeseti=0;usedi=0;fatheri=-1;used0=1;for(i=1;ivcount;i+)j=0;while(usedj)j+;for(k=0;kvcount;k+)if(!usedk)&(lowcostklowc