C++常用算法总结(共21页).doc

《C++常用算法总结(共21页).doc》由会员分享，可在线阅读，更多相关《C++常用算法总结(共21页).doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上常用算法总结1分段函数的计算（如数学分段函数、一元二次方程求解， if-else）x11x10x10例1：有一函数：写程序分别求当x=0.5, x=5.975, x=101.25, x=356.75时，y的值。#include void main( )float x,y;cinx;if (x1) y=x*x;else if(x10)y=3*x-2;else y=x*x*x-10*x*x+28;coutx=x,y=yendl;例2：输入系数a、b和c，求ax2+bx+c=0 的解。#include #include void main( ) float a, b, c,

2、 disc, x1, x2, realpart, imagpart; cinabc; coutThe equation; if (fabs(a)=1e-6) / a=0 注意写法 cout is not quadraticn;else / 处理后三种情况 disc=b*b-4*a*c;if (fabs(disc)=1e-6) / disc=0 cout has two equal roots:(-b/(2*a)1e-6) / disc 0 x1=(-b+sqrt(disc)/(2*a);x2=(-b-sqrt(disc)/(2*a);cout has distinct real roots:x

3、1 and x2endl;else / disc 0 realpart=-b/(2*a);imagpart=sqrt(-disc)/(2*a);cout has complex roots:n;coutrealpart+imagpartin;coutrealpart-imagpartin; 例1#include main() float a, b, c, disc, x1, x2, realpart, imagpart; scanf(%f,%f,%f, &a, &b, &c); printf(The equation); if (fabs(a)=1e-6) /* a=0 注意写法 */prin

4、tf( is not quadraticn);else /* 处理后三种情况 */ disc=b*b-4*a*c;if (fabs(disc)1e-6)x1=(-b+sqrt(disc)/(2*a);x2=(-b-sqrt(disc)/(2*a);printf( has distinct real roots:%8.4f and %8.4fn ,x1,x2);elserealpart=-b/(2*a);imagpart=sqrt(-disc)/(2*a);printf( has complex roots:n);printf(%8.4f+%8.4f in,realpart,imagpart);

5、 printf(%8.4f-%8.4f in,realpart,imagpart); 2多项式累加和、累乘积（1）根据通项大小结束（2）规定循环次数例1: 求：#include #include void main( )float x, t, sum; int n; cinx; n=1; t=1; sum=0; while( fabs(t)1e-6 )sum += t;n=n+1;t=t*(-1)*x*x/(2*n-3)/(2*n-2); coutcos(x)=sumendl;例2：有一分数序列， 求出这个序列的前20项之和#include void main( ) float a=2,b=1

6、,sum=0,t; int i;for(i=1; i=20;i+)sum+=a/b;t=a; a+=b; b=t;coutsum=sumendl;3求素数例1：将96到100之间的全部偶数分解成两个素数之和#include #include void main( ) int i,j,m,k,n;for ( i=96;i=100;i+=2 )for (m=3;mi/2;m+=2) k=sqrt(m);for (j=2;j=k+1) / m是素数 n=i-m;k=sqrt(n);for(j=2;j=k+1) / n是素数 couti=m+nendl;例2：以下函数：判断 x 是否是素数，若是素数，

7、返回1；若不是素数，返回0。int isprime1(int x) /* 解1 */ int k, i; k=sqrt(x); for(i=2; i=k; i+) if(x%i=0) break; if(i=k+1) return(1); else return(0); int isprime2(int x) /* 解2 */ int k, i; k=sqrt(x); for(i=2; i=k; i+) if(x%i=0) return(0); return(1);4牛顿迭代求a的平方根迭代公式为，要求前后两次求出的x 的差的绝对值小于10-5。#include #include void m

8、ain( )float a,x0,x1;cina;x0=a/2;x1=(x0+a/x0)/2;dox0=x1;x1=(x0+a/x0)/2;while(fabs(x1-x0)=1e-5);coutThe square root of a is x1endl;5求最大公约数、最小公倍数#include int gys(int m, int n) / 用辗转相除法求最大公约数int d, x ,u ;d=mn?m:n;x=mn?m:n;u=d%x;while(u!=0) d=x; x=u; u=d%x; return(x);int gys(int m, int n) / 用辗转相除法求最大公约数的

9、优化算法int r;while(r=m%n)!=0) m=n; n=r; return(n);int gbs(int m, int n) / 求最小公倍数int maxy; maxy=gys(m,n);return(m*n/maxy);int gys(int m, int n) / 根据定义求最大公约数int i,x;x=m=1; i-)if(m%i=0 & n%i=0) break;return(i);int gbs(int m, int n) / 根据定义求最小公倍数int i,d;d=mn?m:n;for(i=d; in)m=m-n;else n=n-m;return(m);void m

10、ain( )int m,n;cinmn;coutgong yue shu:gys(m,n)endl;coutgong bei shu:gbs(m,n)endl;6数的分解（硬性分解、循环分解，如求解水仙花数）例1：任意输入一个不多于五位整数，分别将该数各位数字正向、逆向输出。如输入7632，则输出：ws=47,6,3,22,3,6,7（1）用选择结构实现/* n=k5 k4 k3 k2 k1 ，其中k1表示个位，k2表示十位，其余依此类推 */#include void main( ) long n; int ws, k5, k4, k3, k2, k1;cinn;if(n10) ws=1;e

11、lse if(n100) ws=2;else if(n1000) ws=3;else if(n10000) ws=4;else ws=5;coutws=wsendl;switch(ws) case 5: k5=n/10000; n=n%10000; coutk5,;case 4: k4=n/1000; n=n%1000; coutk4,;case 3: k3=n/100; n=n%100; coutk3,;case 2: k2=n/10; n=n%10; coutk2,;case 1: k1=n; coutk1n; switch(ws) case 1: coutk1endl; break;ca

12、se 2: coutk1,k2endl; break;case 3: coutk1,k2,k3endl; break;case 4: coutk1,k2,k3,k4endl; break;case 5: coutk1,k2,k3,k4,k5endl; break;（2）使用数组和循环实现（循环分解到数组元素中，优点：n的位数不限）#include void main( ) long n; int a5, i=0, k;cinn;while(n0) ai=n%10;n=n/10;i+; coutws=i=0; k-) coutak;coutn;for(k=0; ki; k+) coutak;co

13、utn;（3）用递归实现（优点：n的位数不限）#include void printz(long); /函数原型说明void printd (long); /函数原型说明void main( ) long num;cinnum;printz(num);coutn;printd(num);cout0)printz(n/10);cout0)coutn%10;printd(n/10); 例2：打印出所有的“水仙花数”。（1）分解数字#include #include void main( )int i,a,b,c; /* a百位，b十位，c个位 */for(i=100; i1000; i+)a=i/

14、100; b=i/10%10; c=i%10;if(a*a*a+b*b*b+c*c*c=i)coutsetw(10)i;coutendl;（2）穷举法，三重循环#include void main( ) int i,j,k; /* i百位，j十位，k个位 */for(i=1; i10; i+) for(j=0; j10; j+)for(k=0; k10; k+)if( i*i*i+j*j*j+k*k*k = i*100+j*10+k )coutijkendl;7数的合并（类似于乘权求和）例1: 已知 int a10, k i, n; 数组a中有k个值，分别是一个十进制整数的各位数字，将其合并成

15、一个整数n，算法如下：n=0;for(i=0; ik; i+) n = n*10 + ai;例2: 将一个八进制正整数作为字符串输入，如输入字符串“342”，输出其等值的十进制数。#include void main( )char *p,s6; int n=0;cins;for(p=s; *p!=0; p+) n=n*8+*p-0;coutnendl; 例3：写一程序，将一个十六数字符串转换成相应的十进制数。#include int htod(char *); /函数原型说明void main( )char s80;cins;couthtod(s)=0 & si=a & si=f) n = s

16、i-a+10;else n = si-A+10;num = num*16+n;return(num);8一维数组排序（选择法、冒泡法、*插入法（*前插、*后插）例1：将n个整数按由小到大排列#include #include void sort(int a ,int n) / 选择法排序 int i,j,p,t;for(i=0; in-1; i+) p=i;for(j=i+1; jn; j+)if(ajap) p=j;if(p!=i) t=ai; ai=ap; ap=t;void sort(int a ,int n) / 冒泡法排序 int i,j,t;for(i=0; in-1; i+)fo

17、r(j=0;jaj+1) t=aj; aj=aj+1; aj+1=t;void main( )int i,n,a100;cinn;for(i=0;iai;sort(a,n);for(i=0;in;i+)if(i%10=0)coutn;coutsetw(5)ai;coutendl;*例2: 插入排序法（主函数与例1一样）（1）前插算法void insertsort(int *a, int n) /* 数组a有n个元素 */int i,j,k,t;for(i=1; in; i+)t=ai;for(j=0; ji; j+) /* 找到待插位置 */if( tj; k-) /* 将比t大的元素依次全部

18、右移一个位置 */ak=ak-1;aj=t;（2）后插算法void insertsort2(int a, int n) /* 数组a有n个元素 */int i,j,t;for(i=1; i=0 & taj) /* 将比t大的元素依次右移一个位置 */aj+1=aj;j-;aj+1=t;9一维数组逆置（含整型数组逆置和字符数组逆置等，变形：会判回文等）例1: 编一函数，将整型数组d中n个元素的次序倒置 #include void reverse(int d , int n) / 解1 int i, j, t; i=0; j=n-1; while(ij) t=di; di=dj; dj=t;i+;

19、 j-; void reverse( int *d, int n) / 解2，指针方式 int *p1, *p2, t; p1=d; p2=d+n-1; / p1、p2 是指针 while( p1p2 ) t=*p1; *p1=*p2; *p2=t; p1+; p2-; void reverse(int d ,int n) / 解3 int k,t,i ;k=n/2 ;for(i=0 ;ik ;i+) t=dn-1-i; dn-1-i=di; di=t; void main( )int a10=1,2,3,4,5,6,7,8,9,10, i;reverse(a, 10); for(i=0; i

20、9; i+)coutai,;couta9endl;例2：编一函数，判断输入的字符串是否为正向拼写与反向拼写都一样的回文，判断回文时，忽略大小写字母的区别、忽略空格及标点符号等。注意：isalpha(c)用于判断c是否是字母，如果是字母返回真，否则返回假。toupper(ch) 将ch字符转换成大写字母#include #include #include palin(char s )char *head,*tail;head=s; tail=s+strlen(s)-1;while(headtail) while(!isalpha(*head) head+; /*去掉非字母字符*/ while(!

21、isalpha(*tail) tail-; if(toupper(*head)=toupper(*tail) head+;tail-; else return(0);return(1);void main( )char s80;cin.getline(s, 80);coutsendl;if(palin(s) coutYes.n;else coutNo.n;10数组归并（或合并），指两个有序数组合并成一个有序数组。例1：编写一程序，将已按升序排好序的两个字符串str1和str2中的字符，按升序合并到字符串str3中，如str1为abd，str2为bc，则将str1和str2合并后得abbcd。#

22、include void main( )char str1 =bdfhjlnpq;char str2 =acegikm;char str380;int i=0, j=0, k=0;while(str1i!=0 & str2j!=0) if(str1istr2j) str3k=str1i;i+; else str3k=str2j;j+; k+; while(str1i!=0) str3k=str1i; k+; i+; ; while(str2j!=0) str3k=str2j; k+; j+; ; str3k=0;coutstr3endl;此程序运行结果为：abcdefghijklmnpq11一

23、维数组查找（顺序、折半）例1：编一函数，利用顺序查找法从数组a的10个元素中对关键字m进行查找。顺序查找法的思路是：从第一个元素开始，从前向后依次与关键字比较，直到找到此元素或查找到数组尾部时结束。若找到，返回此元素的下标；若仍未找到，则返回1。#include int search(int a , int n, int m) / a数组中有n个元素，查找值为m的元素下标int i;for(i=0; im;no=search(a, 10, m);if(no=0) coutOK Found! position:noendl;else coutSorry Not Found!n;例2：编一函数，利

24、用折半查找法从数组a的10个元素中对关键字m进行查找。折半查找法的前提是：数组元素值必须已排序。折半查找法的思路是：先确定待查元素的范围，将排好序的元素分成两半，然后测试位于中间点元素的值。如果该待查元素的值大于中间点元素，就缩小待查范围，只测试中间点之后的元素；反之，测试中间点之前的元素。若找到，返回其下标值；反之，返回1。#include int binary(int a , int n, int m) / a数组中有n个元素，查找值为m的元素下标int low=0,high=n-1,mid;while (low=high)mid=(low+high)/2;if(mamid)low=mid

25、+1;else return(mid);return(-1);void main( )int a10=2,4,6 ,8,10,12,14, 16,18,20, m, no;cinm;no=binary(a, 10, m);if(no=0) coutOK Found! position:noendl;else coutSorry Not Found!n;12一维数组：插入元素、删除元素例1：给定一维升序整型数组a10，其前7个值为0、2、4、6、8、10，12，编一程序，要求做3次循环分别将 -1、8、13插入到数组，使新数组仍为升序#include void insert(int a , in

26、t n, int x) /解1：从后向前找插入位置int i;if(n=0) a0=x;elsefor(i=n-1; i=0; i-) / 找到应插入的位置if(x=a)if(*p*(p+1)t=*p; *p=*(p+1); *(p+1)=t; p-; else break;void main( ) int a10=0,2,4,6,8,10,12 ;int i,n=7,x;coutorigin array: ;for(i=0;in;i+) coutai ;coutn;for(i=0;i3;i+) / 控制插入次数 coutx;insert(a,n,x);n+; coutresult array

27、: ;for(i=0;i10;i+) coutai ;coutn;例2：删除一维数组中值为c的元素。例：输入一个字符串s，输入一个字符c，删除字符串中出现的字符c后，输出余下的字符。例如输入字符串“warrior”及字符r，则结果字符串为“waio”#include void main( )char s80,c,*p, *pt; cin.getline(s, 80);cin.get(c);for(p=s; *p!=0; ) if(*p=c)for(pt=p; *pt!=0; pt+)*pt=*(pt+1);elsep+;coutsendl;13求一维数组最大、最小、平均值解1：通过全局变量返回

28、数组的最大值和最小值，通过函数的返回值返回数组的平均值。#include float max, min;float average(float array , int n) int i; float aver, sum;max=min=sum=array0;for (i=1; imax)max=arrayi;else if (arrayimin) min=arrayi;sum=sum+arrayi;aver=sum/n;return(aver);void main( ) float ave, score10;int i;for (i=0; iscorei;ave=average(score,

29、10);coutmax=maxendl;coutmin=minendl;coutaverage=aveendl;解2：通过指针做函数参数，返回数组的最大值、最小值和平均值。#include / 推荐使用此方法void average(float array , int n, float *maxp, float *minp, float *averp) int i; float sum;sum=array0;*maxp=*minp=array0;for (i=1; i*maxp)*maxp=arrayi;else if (arrayi*minp) *minp=arrayi;sum=sum+ar

30、rayi;*averp=sum/n;void main( ) float score10, max, min, aver ;int i; for (i=0; iscorei;average(score, 10, &max, &min, &aver);coutmax=maxendl;coutmin=minendl;coutaverage=averendl;解3：通过引用做函数参数，返回数组的最大值、最小值和平均值。#include / 推荐使用此方法void average(float array , int n, float &maxv, float &minv, float &averv)

31、int i; float sum;sum=array0;maxv=minv=array0;for (i=1; imaxv)maxv=arrayi;else if (arrayiminv) minv=arrayi;sum=sum+arrayi;averv=sum/n;void main( ) float score10, max, min, aver ;int i; for (i=0; iscorei;average(score, 10, max, min, aver);coutmax=maxendl;coutmin=minendl;coutaverage=averendl;14扫描一维数组求满

32、足条件的元素个数，如素数个数、偶数个数、正数个数等例1：统计一维数组中元素值为素数的元素个数，数组元素为大于1的自然数。素数的定义为：如果一个数的正因子只有和这个数本身，那么这个数就是素数。#include int isprime( int x ) int i; for( i=2; i=x/2; i+)if( x%i=0) return(0); return(1);void main( ) int array20=2,3,27,7,97,96,102,137;int i,n=0;for (i=0;i20;i+)if( arrayi!=0 & isprime(arrayi) ) n+;coutarrayiendl;couttotal=nn;15字符串操作（不用系统函数，完成strlen, strcpy, strcat, strcmp 功能）#include int mystrlen(char *str) /* strlen函数功能 */char *p1=str, *p2=p1;while(*p2) p2+;return(p2-p1);char* mystrcpy(char *to,char *from) /*