C++常用算法總結(jié)

1．分段函數(shù)的計(jì)算（如數(shù)學(xué)分段函數(shù)、一元二次方程求解，）例：有一函數(shù)：x2y3x2x3x2寫(xiě)程序分別求當(dāng)x=0.5,x=5.975,x=101.25,x=356.75時(shí)，y的值。#include<iostream.h>voidmain(){floatx,y;cin>>x;if(x<1)y=x*x;elseif(x<10)y=3*x-2;elsey=x*x*x-10*x*x+28;cout<<"x="<<x<<",y="<<y<<endl;}例：輸入系數(shù)、b和，求ax2+bx+c=0的解。#include<iostream.h>#include<math.h>voidmain(){floata,b,c,disc,x1,x2,realpart,imagpart;cin>>a>>b>>c;cout<<"Theequation";if(fabs(a)<=1e-6)//a==0注意寫(xiě)法cout<<"isnotquadratic\n";else{//處理后三種情況disc=b*b-4*a*c;if(fabs(disc)<=1e-6)cout<<"hastwoequalroots:"<<(-b/(2*a))<<endl;//disc==0elseif(disc>1e-6)//disc>0{x1=(-b+sqrt(disc))/(2*a);x2=(-b-sqrt(disc))/(2*a);cout<<"hasdistinctrealroots:"<<x1<<"and"<<x2<<endl;}else//disc<0imagpart=sqrt(-disc)/(2*a);{realpart=-b/(2*a);cout<<"hascomplexroots:\n";cout<<realpart<<"+"<<imagpart<<"i\n";cout<<realpart<<"-"<<imagpart<<"i\n";}}}#include<math.h>main(){floata,b,c,disc,x1,x2,realpart,imagpart;scanf("%f,%f,%f",&a,&b,&c);equation");if(fabs(a)<=1e-6)printf("The/*a==0注意寫(xiě)法*/printf("isnotquadratic\n");else/*處理后三種情況*/{disc=b*b-4*a*c;if(fabs(disc)<=1e-6)/*disc==0printf("hastwoequalroots:%8.4f\n,",-b/(2*a));*/elseif(disc>1e-6){x2=(-b-sqrt(disc))/(2*a);realroots:%8.4fand%8.4f\n",x1,x2);}x1=(-b+sqrt(disc))/(2*a);printf("hasdistinctelse{realpart=-b/(2*a);imagpart=sqrt(-disc)/(2*a);printf("hascomplexroots:\n");printf("%8.4f+%8.4fi\n",realpart,imagpart);printf("%8.4f-%8.4fi\n",realpart,imagpart);}}2式累加和、累乘積（）根據(jù)通項(xiàng)大小結(jié)束（）規(guī)定循環(huán)次數(shù)x2x42n2x例1:x)12!4!(求：n1(2n2)!#include<iostream.h>#include<math.h>voidmain(){floatx,t,sum;intn;cin>>x;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);}cout<<"cos("<<x<<")="<<sum<<endl;}例2：有一分2358,,,,,數(shù)序列，求出這個(gè)序列的前20項(xiàng)之和,12358#include<iostream.h>voidmain(){floata=2,b=1,sum=0,t;inti;for(i=1;i<=20;i++){sum+=a/b;t=a;a+=b;b=t;}cout<<"sum="<<sum<<endl;}3．求素?cái)?shù)例：將96到100之間的全部偶數(shù)分解成兩個(gè)素?cái)?shù)之和#include<iostream.h>#include<math.h>voidmain(){inti,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是素?cái)?shù)//n是素?cái)?shù){n=i-m;k=sqrt(n);for(j=2;j<=k;j++)if(n%j==0)break;if(j>=k+1)cout<<i<<'='<<m<<'+'<<n<<endl;}}}例：以下函數(shù)：判斷x是否是素?cái)?shù)，若是素?cái)?shù)，返回；若不是素?cái)?shù)，返回。intisprime1(intx)/*解1*/{intk,i;k=sqrt(x);for(i=2;i<=k;i++)if(x%i==0)break;if(i==k+1)return(1);elsereturn(0);}intisprime2(intx){intk,i;/*解2*/k=sqrt(x);for(i=2;i<=k;i++)if(x%i==0)return(0);return(1);}4．牛頓迭代求a的平方根迭代公式為1，要求前后兩次求出的x的差的絕對(duì)值小于axxn12nxn10-5。#include<iostream.h>#include<math.h>voidmain(){floata,x0,x1;cin>>a;x0=a/2;x1=(x0+a/x0)/2;do{x0=x1;x1=(x0+a/x0)/2;}while(fabs(x1-x0)>=1e-5);cout<<"Thesquarerootof"<<a<<"is"<<x1<<endl;}5．求最大公約數(shù)、最小公倍數(shù)#include<iostream.h>intgys(intm,intn){//用輾轉(zhuǎn)相除法求最大公約數(shù)intd,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);}intgys(intm,intn)算法//用輾轉(zhuǎn)相除法求最大公約數(shù)的優(yōu)化{intr;while((r=m%n)!=0){m=n;n=r;}return(n);}intgbs(intm,intn){//求最小公倍數(shù)intmaxy;maxy=gys(m,n);return(m*n/maxy);}intgys(intm,intn){inti,x;//根據(jù)定義求最大公約數(shù)x=m<n?m:n;for(i=x;i>=1;i--)if(m%i==0&&n%i==0)break;return(i);}intgbs(intm,intn){inti,d;//根據(jù)定義求最小公倍數(shù)d=m>n?m:n;for(i=d;i<=m*n;i++)if(i%m==0&&i%n==0)break;return(i);}intgys(intm,intn)兩數(shù)相等{//求最大公約數(shù)：大數(shù)減小數(shù)直至while(m!=n)if(m>n)m=m-n;elsen=n-m;return(m);}voidmain(){intm,n;cin>>m>>n;cout<<"gongyueshu:"<<gys(m,n)<<endl;cout<<"gongbeishu:"<<gbs(m,n)<<endl;}6．?dāng)?shù)的分解（硬性分解、循環(huán)分解，如求解水仙花數(shù)）例：任意輸入一個(gè)不多于五位整數(shù)，分別將該數(shù)各位數(shù)字正向、逆向輸出。如輸入，則輸出：ws=47,6,3,22,3,6,7（）用選擇結(jié)構(gòu)實(shí)現(xiàn)/*n=k5k4k3k2k1，其中k1表示個(gè)位，k2表示十位，其余依此類(lèi)推*/#include<iostream.h>voidmain(){longn;intws,k5,k4,k3,k2,k1;cin>>n;if(n<10)ws=1;elseif(n<100)ws=2;elseif(n<1000)ws=3;elseif(n<10000)ws=4;elsews=5;cout<<"ws="<<ws<<endl;switch(ws){case5:k5=n/10000;n=n%10000;cout<<k5<<',';case4:k4=n/1000;n=n%1000;cout<<k4<<',';case3:k3=n/100;n=n%100;cout<<k3<<',';case2:k2=n/10;n=n%10;cout<<k2<<',';case1:k1=n;cout<<k1<<'\n';}switch(ws){case1:cout<<k1<<endl;break;case2:cout<<k1<<','<<k2<<endl;break;case3:cout<<k1<<','<<k2<<','<<k3<<endl;break;case4:cout<<k1<<','<<k2<<','<<k3<<','<<k4<<endl;break;case5:cout<<k1<<','<<k2<<','<<k3<<','<<k4<<','<<k5<<endl;break;}}（2）使用數(shù)組和循環(huán)實(shí)現(xiàn)（循環(huán)分解到數(shù)組元素中，優(yōu)點(diǎn)：n的位數(shù)不限）#include<iostream.h>voidmain(){longn;inta[5],i=0,k;cin>>n;while(n>0){a[i]=n%10;n=n/10;i++;}cout<<"ws="<<i<<endl;for(k=i-1;k>=0;k--)cout<<a[k];cout<<'\n';for(k=0;k<i;k++)cout<<a[k];cout<<'\n';}（）用遞歸實(shí)現(xiàn)（優(yōu)點(diǎn)：n的位數(shù)不限）#include<iostream.h>voidprintz(long);voidprintd(long);voidmain(){longnum;cin>>num;//函數(shù)原型說(shuō)明//函數(shù)原型說(shuō)明printz(num);cout<<"\n";printd(num);cout<<"\n";}voidprintz(longn){if(n>0)//正向輸出//逆向輸出{printz(n/10);cout<<n%10;}}voidprintd(longn){if(n>0){cout<<n%10;printd(n/10);}}例：打印出所有的“水仙花數(shù)”。（）分解數(shù)字#include<iostream.h>#include<iomanip.h>voidmain(){inti,a,b,c;/*a百位，b十位，c個(gè)位*/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;}（）窮舉法，三重循環(huán)#include<iostream.h>voidmain(){inti,j,k;/*i百位，j十位，k個(gè)位*/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．?dāng)?shù)的合并（類(lèi)似于乘權(quán)求和）例1:已知inta[10],ki,n;數(shù)組a中有k個(gè)值，分別是一個(gè)十進(jìn)制整數(shù)的各位數(shù)字，將其合并成一個(gè)整數(shù)，算法如下：n=0;for(i=0;i<k;i++)n=n*10+a[i];例2:將一個(gè)八進(jìn)制正整數(shù)作為字符串輸入，如輸入字符串“”，輸出其等值的十進(jìn)制數(shù)。#include<iostream.h>voidmain(){char*p,s[6];intn=0;cin>>s;for(p=s;*p!='\0';p++)n=n*8+*p-'0';cout<<n<<endl;}例：寫(xiě)一程序，將一個(gè)十六數(shù)字符串轉(zhuǎn)換成相應(yīng)的十進(jìn)制數(shù)。#include<iostream.h>inthtod(char*);//函數(shù)原型說(shuō)明voidmain(){chars[80];cin>>s;cout<<htod(s)<<endl;}inthtod(chars[80]){inti,n,num=0;for(i=0;s[i]!='\0';i++){if(s[i]>='0'&&s[i]<='9')n=s[i]-'0';elseif(s[i]>='a'&&s[i]<='f')n=s[i]-'a'+10;elsen=s[i]-'A'+10;num=num*16+n;}return(num);}8．一維數(shù)組排序（選擇法、冒泡法、插入法（前插、例：將n個(gè)整數(shù)按由小到大排列#include<iostream.h>#include<iomanip.h>voidsort(inta[],intn){inti,j,p,t;//選擇法排序for(i=0;i<n-1;i++){p=i;for(j=i+1;j<n;j++)if(a[j]<a[p])p=j;if(p!=i){t=a[i];a[i]=a[p];a[p]=t;}}}voidsort(inta[],intn){inti,j,t;//冒泡法排序for(i=0;i<n-1;i++)for(j=0;j<n-1-i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}}voidmain(){inti,n,a[100];cin>>n;for(i=0;i<n;i++)cin>>a[i];sort(a,n);for(i=0;i<n;i++){if(i%10==0)cout<<"\n";cout<<setw(5)<<a[i];}cout<<endl;}*例2:插入排序法（主函數(shù)與例1一樣）（）前插算法voidinsertsort(int*a,intn)/*數(shù)組a有n個(gè)元素*/{inti,j,k,t;for(i=1;i<n;i++){t=a[i];for(j=0;j<i;j++)if(t<a[j])break;for(k=i;k>j;k--)/*找到待插位置*//*將比t大的元素依次全部右移一個(gè)位置*/a[k]=a[k-1];a[j]=t;}}（）后插算法voidinsertsort2(inta,intn)/*數(shù)組a有n個(gè)元素*/{inti,j,t;for(i=1;i<n;i++){t=a[i];j=i-1;while(j>=0&&t<a[j])/*將比t大的元素依次右移一個(gè)位置*/{a[j+1]=a[j];j--;}a[j+1]=t;}}9．一維數(shù)組逆置（含整型數(shù)組逆置和字符數(shù)組逆置等，變形：會(huì)判回文等）例1:編一函數(shù)，將整型數(shù)組d中n個(gè)元素的次序倒置#include<iostream.h>voidreverse(intd[],intn){//解1inti,j,t;i=0;j=n-1;while(i<j){t=d[i];d[i]=d[j];d[j]=t;i++;j--;}}voidreverse(int*d,intn){int*p1,*p2,t;p1=d;p2=d+n-1;//p1、p2是指針while(p1<p2)//解，指針?lè)绞絳t=*p1;*p1=*p2;*p2=t;p1++;p2--;}}voidreverse(intd[],intn)//解3{intk,t,i;k=n/2;for(i=0;i<k;i++){t=d[n-1-i];d[n-1-i]=d[i];d[i]=t;}}voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,10},i;reverse(a,10);for(i=0;i<9;i++)cout<<a[i]<<',';cout<<a[9]<<endl;}例：編一函數(shù)，判斷輸入的字符串是否為正向拼寫(xiě)與反向拼寫(xiě)都一樣的"回文，判斷回文時(shí)，忽略大小寫(xiě)字母的區(qū)別、忽略空格及標(biāo)點(diǎn)符號(hào)等。注意：isalpha(c)用于判斷c是否是字母，如果是字母返回真，否則返回假。toupper(ch)將ch字符轉(zhuǎn)換成大寫(xiě)字母#include<iostream.h>#include<string.h>#include<ctype.h>palin(chars[]){char*head,*tail;head=s;tail=s+strlen(s)-1;while(head<tail){while(!isalpha(*head))head++;/*去掉非字母字符*/while(!isalpha(*tail))tail--;if(toupper(*head)==toupper(*tail)){head++;tail--;}elsereturn(0);}return(1);}voidmain(){chars[80];cin.getline(s,80);cout<<s<<endl;if(palin(s))cout<<"Yes.\n";elsecout<<"No.\n";}10例：編寫(xiě)一程序，將已按升序排好序的兩個(gè)字符串str1和str2中的字str3str1為"abd"str2為"bc"str1和str2合并后得"abbcd"。#include<iostream.h>voidmain(){charstr1[]="bdfhjlnpq";charstr2[]="acegikm";charstr3[80];inti=0,j=0,k=0;while(str1[i]!='\0'&&str2[j]!='\0'){if(str1[i]<str2[j]){str3[k]=str1[i];i++;}else{str3[k]=str2[j];j++;}k++;}while(str1[i]!='\0'){str3[k]=str1[i];k++;i++;};while(str2[j]!='\0'){str3[k]=str2[j];k++;j++;};str3[k]='\0';cout<<str3<<endl;}此程序運(yùn)行結(jié)果為：abcdefghijklmnpq11．一維數(shù)組查找（順序、折半）例：編一函數(shù)，利用順序查找法從數(shù)組a的10個(gè)元素中對(duì)關(guān)鍵字m進(jìn)行查找。順序查找法的思路是：從第一個(gè)元素開(kāi)始，從前向后依次與關(guān)鍵字比較，直到找到此元素或查找到數(shù)組尾部時(shí)結(jié)束。若找到，返回此元素的下標(biāo)；若仍未找到，則返回－。#include<iostream.h