C常用算法总结

1、常用算法总结1分段函数的计算（如数学分段函数、一元二次方程求解， if-else）x<11x<10x10例1：有一函数：写程序分别求当x=0.5, x=5.975, x=101.25, x=356.75时，y的值。#include <iostream.h>void main( )float x,y;cin>>x;if (x<1) y=x*x;else if(x<10)y=3*x-2;else y=x*x*x-10*x*x+28;cout<<"x="<<x<<",y="&l

2、t;<y<<endl;例2：输入系数a、b和c，求ax2+bx+c=0 的解。#include <iostream.h>#include <math.h>void main( ) float a, b, c, disc, x1, x2, realpart, imagpart; cin>>a>>b>>c; cout<<"The equation" if (fabs(a)<=1e-6) / a=0 注意写法 cout<<" is not quadraticn&q

3、uot;else / 处理后三种情况 disc=b*b-4*a*c;if (fabs(disc)<=1e-6) / disc=0 cout<<" has two equal roots:"<<(-b/(2*a)<<endl;else if (disc>1e-6) / disc > 0 x1=(-b+sqrt(disc)/(2*a);x2=(-b-sqrt(disc)/(2*a);cout<<" has distinct real roots:"<<x1<<"

4、; and "<<x2<<endl;else / disc < 0 realpart=-b/(2*a);imagpart=sqrt(-disc)/(2*a);cout<<" has complex roots:n"cout<<realpart<<"+"<<imagpart<<"in"cout<<realpart<<"-"<<imagpart<<"in"

5、; 例1#include <math.h>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 注意写法 */printf(" is not quadraticn");else /* 处理后三种情况 */ disc=b*b-4*a*c;if (fabs(disc)<=1e

6、-6) /* disc=0 */ printf(" has two equal roots:%8.4fn,",-b/(2*a);else if (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"

7、;);printf("%8.4f+%8.4f in",realpart,imagpart); printf("%8.4f-%8.4f in",realpart,imagpart); 2多项式累加和、累乘积（1）根据通项大小结束（2）规定循环次数例1: 求：#include <iostream.h>#include <math.h>void main( )float x, t, sum; int n; cin>>x; n=1; t=1; sum=0; while( fabs(t)>1e-6 )sum += t;n=

8、n+1;t=t*(-1)*x*x/(2*n-3)/(2*n-2); cout<<"cos("<<x<<")="<<sum<<endl;例2：有一分数序列， 求出这个序列的前20项之和#include <iostream.h>void main( ) float a=2,b=1,sum=0,t; int i;for(i=1; i<=20;i+)sum+=a/b;t=a; a+=b; b=t;cout<<"sum="<<sum<&l

9、t;endl;3求素数例1：将96到100之间的全部偶数分解成两个素数之和#include <iostream.h>#include <math.h>void main( ) int i,j,m,k,n;for ( i=96;i<=100;i+=2 )for (m=3;m<i/2;m+=2) k=sqrt(m);for (j=2;j<=k;j+)if (m%j=0) break;if (j>=k+1) / m是素数 n=i-m;k=sqrt(n);for(j=2;j<=k;j+)if (n%j=0) break;if (j>=k+1)

10、 / n是素数 cout<<i<<'='<<m<<'+'<<n<<endl;例2：以下函数：判断 x 是否是素数，若是素数，返回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(

11、x); for(i=2; i<=k; i+) if(x%i=0) return(0); return(1);4牛顿迭代求a的平方根迭代公式为，要求前后两次求出的x 的差的绝对值小于10-5。#include <iostream.h>#include <math.h>void main( )float a,x0,x1;cin>>a;x0=a/2;x1=(x0+a/x0)/2;dox0=x1;x1=(x0+a/x0)/2;while(fabs(x1-x0)>=1e-5);cout<<"The square root of &qu

12、ot;<<a<<" is "<<x1<<endl;5求最大公约数、最小公倍数#include <iostream.h>int gys(int m, int n) / 用辗转相除法求最大公约数int d, x ,u ;d=m>n?m:n;x=m<n?m:n;u=d%x;while(u!=0) d=x; x=u; u=d%x; return(x);int gys(int m, int n) / 用辗转相除法求最大公约数的优化算法int r;while(r=m%n)!=0) m=n; n=r; return(

13、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<n?m:n;for(i=x; i>=1; i-)if(m%i=0 && n%i=0) break;return(i);int gbs(int m, int n) / 根据定义求最小公倍数int i,d;d=m>n?m:n;for(i=d; i<=m*n; i+)if(i%m=0 && i%n=0) br

14、eak;return(i);int gys(int m, int n) / 求最大公约数：大数减小数直至两数相等 while(m!=n)if(m>n)m=m-n;else n=n-m;return(m);void main( )int m,n;cin>>m>>n;cout<<"gong yue shu:"<<gys(m,n)<<endl;cout<<"gong bei shu:"<<gbs(m,n)<<endl;6数的分解（硬性分解、循环分解，如求解水仙

15、花数）例1：任意输入一个不多于五位整数，分别将该数各位数字正向、逆向输出。如输入7632，则输出：ws=47,6,3,22,3,6,7（1）用选择结构实现/* n=k5 k4 k3 k2 k1 ，其中k1表示个位，k2表示十位，其余依此类推 */#include <iostream.h>void main( ) long n; int ws, k5, k4, k3, k2, k1;cin>>n;if(n<10) ws=1;else if(n<100) ws=2;else if(n<1000) ws=3;else if(n<10000) ws=4;

16、else ws=5;cout<<"ws="<<ws<<endl;switch(ws) case 5: k5=n/10000; n=n%10000; cout<<k5<<','case 4: k4=n/1000; n=n%1000; cout<<k4<<','case 3: k3=n/100; n=n%100; cout<<k3<<','case 2: k2=n/10; n=n%10; cout<<k2<

17、<','case 1: k1=n; cout<<k1<<'n' switch(ws) case 1: cout<<k1<<endl; break;case 2: cout<<k1<<','<<k2<<endl; break;case 3: cout<<k1<<','<<k2<<','<<k3<<endl; break;case 4: cout&

18、lt;<k1<<','<<k2<<','<<k3<<','<<k4<<endl; break;case 5: cout<<k1<<','<<k2<<','<<k3<<','<<k4<<','<<k5<<endl; break;（2）使用数组和循环实现（循环分解到数组元素中，优点

19、：n的位数不限）#include <iostream.h>void main( ) long n; int a5, i=0, k;cin>>n;while(n>0) ai=n%10;n=n/10;i+; cout<<"ws="<<i<<endl;for(k=i-1; k>=0; k-) cout<<ak;cout<<'n'for(k=0; k<i; k+) cout<<ak;cout<<'n'（3）用递归实现（优点：n

20、的位数不限）#include <iostream.h>void printz(long); /函数原型说明void printd (long); /函数原型说明void main( ) long num;cin>>num;printz(num);cout<<"n"printd(num);cout<<"n"void printz(long n) / 正向输出 if(n>0)printz(n/10);cout<<n%10;void printd (long n) / 逆向输出if(n>0

21、)cout<<n%10;printd(n/10); 例2：打印出所有的“水仙花数”。（1）分解数字#include <iostream.h>#include <iomanip.h>void main( )int i,a,b,c; /* a百位，b十位，c个位 */for(i=100; i<1000; i+)a=i/100; b=i/10%10; c=i%10;if(a*a*a+b*b*b+c*c*c=i)cout<<setw(10)<<i;cout<<endl;（2）穷举法，三重循环#include <iost

22、ream.h>void main( ) int i,j,k; /* i百位，j十位，k个位 */for(i=1; i<10; i+) for(j=0; j<10; j+)for(k=0; k<10; k+)if( i*i*i+j*j*j+k*k*k = i*100+j*10+k )cout<<i<<j<<k<<endl;7数的合并（类似于乘权求和）例1: 已知 int a10, k i, n; 数组a中有k个值，分别是一个十进制整数的各位数字，将其合并成一个整数n，算法如下：n=0;for(i=0; i<k; i+)

23、 n = n*10 + ai;例2: 将一个八进制正整数作为字符串输入，如输入字符串“342”，输出其等值的十进制数。#include <iostream.h>void main( )char *p,s6; int n=0;cin>>s;for(p=s; *p!='0' p+) n=n*8+*p-'0'cout<<n<<endl; 例3：写一程序，将一个十六数字符串转换成相应的十进制数。#include <iostream.h>int htod(char *); /函数原型说明void main( )c

24、har s80;cin>>s;cout<<htod(s)<<endl;int htod(char s80)int i,n,num=0;for(i=0; si!='0' i+) if( si>='0' && si<='9') n = si-'0'else if( si>='a' && si<='f') n = si-'a'+10;else n = si-'A'+10;num =

25、num*16+n;return(num);8一维数组排序（选择法、冒泡法、*插入法（*前插、*后插）例1：将n个整数按由小到大排列#include <iostream.h>#include <iomanip.h>void sort(int a ,int n) / 选择法排序 int i,j,p,t;for(i=0; i<n-1; i+) p=i;for(j=i+1; j<n; j+)if(aj<ap) p=j;if(p!=i) t=ai; ai=ap; ap=t;void sort(int a ,int n) / 冒泡法排序 int i,j,t;for

26、(i=0; i<n-1; i+)for(j=0;j<n-1-i;j+)if(aj>aj+1) t=aj; aj=aj+1; aj+1=t;void main( )int i,n,a100;cin>>n;for(i=0;i<n;i+)cin>>ai;sort(a,n);for(i=0;i<n;i+)if(i%10=0)cout<<"n"cout<<setw(5)<<ai;cout<<endl;*例2: 插入排序法（主函数与例1一样）（1）前插算法void insertsort

27、(int *a, int n) /* 数组a有n个元素 */int i,j,k,t;for(i=1; i<n; i+)t=ai;for(j=0; j<i; j+) /* 找到待插位置 */if( t<aj ) break;for(k=i; k>j; k-) /* 将比t大的元素依次全部右移一个位置 */ak=ak-1;aj=t;（2）后插算法void insertsort2(int a, int n) /* 数组a有n个元素 */int i,j,t;for(i=1; i<n; i+) t=ai;j=i-1; while(j>=0 && t&l

28、t;aj) /* 将比t大的元素依次右移一个位置 */aj+1=aj;j-;aj+1=t;9一维数组逆置（含整型数组逆置和字符数组逆置等，变形：会判回文等）例1: 编一函数，将整型数组d中n个元素的次序倒置 #include <iostream.h>void reverse(int d , int n) / 解1 int i, j, t; i=0; j=n-1; while(i<j) t=di; di=dj; dj=t;i+; j-; void reverse( int *d, int n) / 解2，指针方式 int *p1, *p2, t; p1=d; p2=d+n-1;

29、 / p1、p2 是指针 while( p1<p2 ) 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 ;i<k ;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<9; i+)cout<<ai<<','cout<<a9<<end

30、l;例2：编一函数，判断输入的字符串是否为正向拼写与反向拼写都一样的"回文"，判断回文时，忽略大小写字母的区别、忽略空格及标点符号等。注意：isalpha(c)用于判断c是否是字母，如果是字母返回真，否则返回假。toupper(ch) 将ch字符转换成大写字母#include <iostream.h>#include <string.h>#include <ctype.h>palin(char s )char *head,*tail;head=s; tail=s+strlen(s)-1;while(head<tail) while(

31、!isalpha(*head) head+; /*去掉非字母字符*/ while(!isalpha(*tail) tail-; if(toupper(*head)=toupper(*tail) head+;tail-; else return(0);return(1);void main( )char s80;cin.getline(s, 80);cout<<s<<endl;if(palin(s) cout<<"Yes.n"else cout<<"No.n"10数组归并（或合并），指两个有序数组合并成一个有

32、序数组。例1：编写一程序，将已按升序排好序的两个字符串str1和str2中的字符，按升序合并到字符串str3中，如str1为"abd"，str2为"bc"，则将str1和str2合并后得"abbcd"。#include <iostream.h>void main( )char str1 ="bdfhjlnpq"char str2 ="acegikm"char str380;int i=0, j=0, k=0;while(str1i!='0' && st

33、r2j!='0') if(str1i<str2j) str3k=str1i;i+; else str3k=str2j;j+; k+; while(str1i!='0') str3k=str1i; k+; i+; ; while(str2j!='0') str3k=str2j; k+; j+; ; str3k='0'cout<<str3<<endl;此程序运行结果为：abcdefghijklmnpq11一维数组查找（顺序、折半）例1：编一函数，利用顺序查找法从数组a的10个元素中对关键字m进行查找。顺序

34、查找法的思路是：从第一个元素开始，从前向后依次与关键字比较，直到找到此元素或查找到数组尾部时结束。若找到，返回此元素的下标；若仍未找到，则返回1。#include <iostream.h>int search(int a , int n, int m) / a数组中有n个元素，查找值为m的元素下标int i;for(i=0; i<n; i+) if (ai=m) return(i); return(-1);void main( )int a10=2,14,6,12,8,17,9,15,-10,-20, m, no;cin>>m;no=search(a, 10, m

35、);if(no>=0) cout<<"OK Found! position:"<<no<<endl;else cout<<"Sorry Not Found!n"例2：编一函数，利用折半查找法从数组a的10个元素中对关键字m进行查找。折半查找法的前提是：数组元素值必须已排序。折半查找法的思路是：先确定待查元素的范围，将排好序的元素分成两半，然后测试位于中间点元素的值。如果该待查元素的值大于中间点元素，就缩小待查范围，只测试中间点之后的元素；反之，测试中间点之前的元素。若找到，返回其下标值；反之，返回1。

36、#include <iostream.h>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(m<amid) high=mid-1;else if(m>amid)low=mid+1;else return(mid);return(-1);void main( )int a10=2,4,6 ,8,10,12,14, 16,18,20, m, no;cin>>m;no=binary

37、(a, 10, m);if(no>=0) cout<<"OK Found! position:"<<no<<endl;else cout<<"Sorry Not Found!n"12一维数组：插入元素、删除元素例1：给定一维升序整型数组a10，其前7个值为0、2、4、6、8、10，12，编一程序，要求做3次循环分别将 -1、8、13插入到数组，使新数组仍为升序#include <iostream.h>void insert(int a , int n, int x) /解1：从后向前找插入

38、位置int i;if(n=0) a0=x;elsefor(i=n-1; i>=0; i-) / 找到应插入的位置if(x<ai) ai+1=ai; / 后挪一个元素else break;ai+1=x;void insert(int a , int n, int x) / 解2：用指针，从后向前处理int t,*p=a+n-1;if(n=0) *a=x;else*(a+n)=x;while(p>=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

39、,12 ;int i,n=7,x;cout<<"origin array: "for(i=0;i<n;i+) cout<<ai<<" "cout<<"n"for(i=0;i<3;i+) / 控制插入次数 cout<<"Please input a value:"cin>>x;insert(a,n,x);n+; cout<<"result array: "for(i=0;i<10;i+) cout

40、<<ai<<" "cout<<"n"例2：删除一维数组中值为c的元素。例：输入一个字符串s，输入一个字符c，删除字符串中出现的字符c后，输出余下的字符。例如输入字符串“warrior”及字符r，则结果字符串为“waio”#include <iostream.h>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' p

41、t+)*pt=*(pt+1);elsep+;cout<<s<<endl;13求一维数组最大、最小、平均值解1：通过全局变量返回数组的最大值和最小值，通过函数的返回值返回数组的平均值。#include <iostream.h>float max, min;float average(float array , int n) int i; float aver, sum;max=min=sum=array0;for (i=1; i<n; i+) if (arrayi>max)max=arrayi;else if (arrayi<min) min

42、=arrayi;sum=sum+arrayi;aver=sum/n;return(aver);void main( ) float ave, score10;int i;for (i=0; i<10; i+) cin>>scorei;ave=average(score, 10);cout<<"max="<<max<<endl;cout<<"min="<<min<<endl;cout<<"average="<<ave<

43、<endl;解2：通过指针做函数参数，返回数组的最大值、最小值和平均值。#include <iostream.h> / 推荐使用此方法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<n; i+) if (arrayi>*maxp)*maxp=arrayi;else if (arrayi<*minp) *minp=arrayi;sum=sum+a

44、rrayi;*averp=sum/n;void main( ) float score10, max, min, aver ;int i; for (i=0; i<10; i+) cin>>scorei;average(score, 10, &max, &min, &aver);cout<<"max="<<max<<endl;cout<<"min="<<min<<endl;cout<<"average="<

45、;<aver<<endl;解3：通过引用做函数参数，返回数组的最大值、最小值和平均值。#include <iostream.h> / 推荐使用此方法void average(float array , int n, float &maxv, float &minv, float &averv) int i; float sum;sum=array0;maxv=minv=array0;for (i=1; i<n; i+) if (arrayi>maxv)maxv=arrayi;else if (arrayi<minv) mi

46、nv=arrayi;sum=sum+arrayi;averv=sum/n;void main( ) float score10, max, min, aver ;int i; for (i=0; i<10; i+) cin>>scorei;average(score, 10, max, min, aver);cout<<"max="<<max<<endl;cout<<"min="<<min<<endl;cout<<"average="

47、<<aver<<endl;14扫描一维数组求满足条件的元素个数，如素数个数、偶数个数、正数个数等例1：统计一维数组中元素值为素数的元素个数，数组元素为大于1的自然数。素数的定义为：如果一个数的正因子只有和这个数本身，那么这个数就是素数。#include <iostream.h>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;f

48、or (i=0;i<20;i+)if( arrayi!=0 && isprime(arrayi) ) n+;cout<<arrayi<<endl;cout<<"total="<<n<<"n"15字符串操作（不用系统函数，完成strlen, strcpy, strcat, strcmp 功能）#include <iostream.h>int mystrlen(char *str) /* strlen函数功能 */char *p1=str, *p2=p1;while

49、(*p2) p2+;return(p2-p1);char* mystrcpy(char *to,char *from) /* strcpy函数功能 */int i;for(i=0;fromi!='0'i+)toi=fromi;toi='0'return(to);char* mystrcat(char *s1,char *s2) /* strcat函数功能 */int i=0,j=0;while (s1i+!='0') ; i= i-1 ; while (s2j!='0') s1i+=s2j+ ; s1i='0' ;

50、 return(s1);int mystrcmp(char *s,char *t) /* strcmp函数功能 */ for( ; *s=*t; s+,t+)if(*s='0') return(0);return(*s-*t);void main( )char s180,s280;int r;cout<<"input sting1:" cin.getline(s1, 80);cout<<"input sting2:" cin.getline(s2, 80);cout<<"s1 length=&

51、quot;<<mystrlen(s1)<<"n"cout<<"s1 compare with s2: "r=mystrcmp(s1,s2);if(r>0) cout<<"s1>s2n"else if(r<0) cout<<"s1<s2n"else cout<<"s1=s2n"mystrcat(s1,s2);cout<<"s1 catenate with s2 is: "

52、<<s1<<endl;cout<<"copy s2 to s1: "<<mystrcpy(s1,s2)<<endl;16求二维数组最大、最小、平均值注意：（1）通过参数返回最大值、最小值和平均值。（2）二维数组做参数时，形式参数的三种写法。#include <iostream.h>#define N 4void average(int (*p)N,int *maxp,int *minp, double *averp)/ 或：void average(int pNN, int *maxp, int *mi

53、np, double *averp)/ 或：void average(int p N, int *maxp, int *minp, double *averp) int i,j;double sum=0;*maxp=*minp=*(*(p);for (i=0; i<N; i+)for (j=0;j<N; j+ ) if (*(*(p+i)+j)>*maxp) *maxp=*(*(p+i)+j);else if (*(*(p+i)+j)<*minp) *minp=*(*(p+i)+j);sum+=*(*(p+i)+j);*averp=sum/(N*N);void main

54、( ) int aNN=3,6,4,6,8,3,1,3,4,7,1,2,2,9,5,3; int max,min,*maxp=&max, *minp=&min; double aver,*averp=&aver; average(a,maxp, minp, averp); cout<<"max="<<max<<", min="<<min<<",average="<<aver<<endl;17二维数组转置（变种：判是否主对角线对称

55、、求左下右上三角形元素之和）以下为在数组自身上转置的算法：void turn(int a44) /* 注意：左下(右上)三角形元素下标满足什么条件 */ int i, j, t;for(i=0; i<4; i+)for(j=0; j<4; j+)if(i<j) /* 注意：此行可改为 i>j */t=aij;aij=aji; aji=t;void turn(int a44) /* 对左下(右上)三角形元素循环，对称元素交换位置 */int i, j, t;for(i=0; i<4; i+)for(j=0; j<i; j+) /* 注意：此行可改为for(j=

56、i+1; j<4; j+) */t=aij;aij=aji; aji=t;18二维数组对角线元素之和。二维数组若为奇数阶，本例累加中心点元素。#include <iostream.h>#define N 4int fsum(int (*)N,int); / 函数原型说明 void main( ) int i,j,aNN=3,6,4,6,8,3,1,3,4,7,1,2,2,9,5,3;for(i=0;i<N;i+) for (j=0;j<N;j+) cout<<aij<<" " cout<<"n&qu

57、ot;cout<<"sum="<<fsum(a,N)<<endl;int fsum(int aNN,int n) / 子函数解法1 int i,j,sum=0;for (i=0;i<n;i+)for (j=0;j<n;j+)if (i=j|i+j=n-1)sum+=aij;if (N%2=1) sum+=aN/2N/2; return sum;int fsum(int aNN,int n) / 子函数解法2 int i,sum=0;for (i=0;i<n;i+)sum += aii+aiN-i-1;return sum;19二维数组周边元素之和#include &