C++常用算法归纳

C++常用算法归纳一、基本算法1、两数交换借助第三数例：任意读入2个整数，然后按从小到大的顺序输出这两个数。【法1】#includeiostreamusingnamespacestd;voidmain(){inta,b;cinab;ab?couta','b:coutb','a;}【法2：让a中放较小数、b中放较大数】#includeiostreamusingnamespacestd;voidmain(){inta,b;cinab;intt;//中间变量ab?(t=a,a=b,b=t):(a=a,b=b);couta','bendl;}【算法解释：“t=a,a=b,b=t”，即可借助t，将a和b的值交换。】2、累加例：求1+2+3+……+100的和。#includeiostreamusingnamespacestd;voidmain(){ints,i;s=0;i=1;while(i=100){s=s+i;i=i+1;}cout1+2+...+100=s;}【分析：出循环时，i为101，其最后一个合法取值（终值）为100；本题中s被称为累加器，它以“s=s+……”的形式出现在循环中，该式被称为累加式，累加器在进入循环前必须获得合法初值，通常为0。i是一个特殊的累加器，每次递增1，又称为计数器。i身兼二职：控制循环的次数，同时兼做累加式的通项。】3、累乘例.求10!。【分析：10！=1×2×3……×10，累乘器在进入循环前必须获得合适初值；通常为1。累乘式格式“C=C*……”必须出现在循环中。注意，不要让累乘器溢出。】#includeiostreamusingnamespacestd;voidmain(){longC;inti;C=1;i=1;while(i=10){C=C*i;i++;}coutCendl;}【思考：能否将本程序稍做修改，分别输出1!~10！】二、非数值计算常用经典算法1、穷举法对所有的可能性进行判断，凡是符合条件的做相应处理（输出、保存等）。例：输出所有的“水仙花”数，即这样的三位正整数：其每一数位上的数字的立方之和等于该数本身。比如，153=13+53+33。【法一:一重循环,难点:求出每位数字】#includeiostreamusingnamespacestd;voidmain(){intsxh;intb,s,g;for(sxh=100;sxh=999;sxh++){b=sxh/100;s=sxh/10%10;g=sxh%10;if(b*b*b+s*s*s+g*g*g==sxh)coutsxhendl;}}【结论：任意一个正整数的个位数字，都可以用“该数%10”求得！】【法二：三重循环】#includeiostreamusingnamespacestd;voidmain(){intb,s,g;for(b=1;b=9;b++)//时针for(s=0;s=9;s++)//分针for(g=0;g=9;g++)//秒针if(b*b*b+s*s*s+g*g*g==b*100+s*10+g)coutb*100+s*10+gendl;}【发现：核心语句if被执行了900次】2、正整数的各数位上数字的获取例1：任意读入一个正整数，依次输出其低位到高位上的每一位数字。例2：任意读入一个整数，依次输出其低位到高位上的每一位数字及其符号位，但若是0不输出符号位。3、迭代法例1.猴子吃桃问题。某猴子某天摘了若干只桃子，吃了一半，不过瘾，又多吃一只；第二天又吃了一半，不过瘾，再多吃一只……到第十天，发现只剩1只桃子了。问第一天共摘了多少只桃子。#includeiostreamusingnamespacestd;voidmain(){intpeach,day;peach=1;for(day=9;day=1;day--)peach=(peach+1)*2;cout第一天的桃子数:peach;}【归纳：类似于本题peach变量的特点：其值不停地被新值替代（自身的原值变化而来），直到满足所求终止。】【问题：能否将上述程序稍作修改，输出每一天的桃子数。】#includeiostreamusingnamespacestd;voidmain(){intpeach,day;peach=1;for(day=9;day=1;day--){peach=(peach+1)*2;cout第day天的桃子数:peachendl;}}4、排序（1）冒泡排序法（起泡法）【算法要领：n个数据最多处理n-1趟，每一趟从头到尾（或从尾到头）两两相邻的元素进行比较，升序排序时，若前者大后者小，则交换两数……，每一趟比前一趟少比较一次。】例：任意读入10个整数，升序排列后输出。#includeiostreamusingnamespacestd;voidmain(){constintN=10;inta[N],i,j;for(i=0;iN;i++)cina[i];//外循环处理N-1趟，控制趟数for(j=1;j=N-1;j++)for(i=0;i=N-1-j;i++)//内循环控制每趟比较次数if(a[i]a[i+1]){intt;t=a[i];a[i]=a[i+1];a[i+1]=t;}for(i=0;iN;i++)couta[i]'';}（2）选择法排序选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是：①从数组存放的n个数中找出最小数的下标（算法见下面的“求最值”），然后将最小数与第1个数交换位置；②除第1个数以外，再从其余n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置；③重复步骤①n-1趟，即可完成所求。例：任意读入10个数，然后进行升序排列。【主函数—读入、调用、输出；子函数—排序。】#includeiostreamusingnamespacestd;voidPX(int*p,intn)//【法1：选择法】{inti,j,k,t;for(i=0;i=n-2;i++){k=i;for(j=i+1;j=n-1;j++)if(*(p+j)*(p+k))k=j;if(k!=i){t=*(p+i);*(p+i)=*(p+k);*(p+k)=t;}}}voidmain(){inta[10],i;for(i=0;i10;i++)cina[i];PX(a,10);//为增大子函数灵活性，将元素个数传过去for(i=0;i10;i++)couta[i]endl;}//【法2：以下冒泡法】#includeiostream#includeiomanipusingnamespacestd;voidPX(int*p,intn){inti,j;intt;for(j=1;j=n-1;j++)for(i=0;i=n-1-j;i++)if(*(p+i)*(p+i+1)){t=*(p+i);*(p+i)=*(p+i+1);*(p+i+1)=t;}}voidmain(){inta[10],i;for(i=0;i10;i++)cina[i];PX(a,10);for(i=0;i10;i++)coutsetw(4)a[i];}5、查找：顺序查找（线性查找）例：任意读入10个数，查找其中有无9这个数。#includeiostreamusingnamespacestd;voidmain(){constintN=10;inta[N],i;for(i=0;iN;i++)cina[i];for(i=0;iN;i++)//正常出口出来，i为Nif(a[i]==9)break;if(iN)cout有endl;elsecout无endl;}【小技巧：定义一个逻辑量】#includeiostreamusingnamespacestd;voidmain(){constintN=10;inta[N],i;boolflag=false;//先假设无for(i=0;iN;i++)cina[i];for(i=0;iN;i++)//正常出口出来，i为Nif(a[i]==9){flag=true;break;}if(flag!=false)cout有endl;elsecout无endl;}【用while改写】#includeiostreamusingnamespacestd;voidmain(){constintN=10;inta[N],i;for(i=0;iN;i++)cina[i];i=0;while(i=N-1&&a[i]!=9)i++;if(i=N-1)cout有endl;elsecout无endl;}6、判断素数（质数）数学定义：“凡是只能被1和自身整除的大于1的整数，就称为质数，即素数。”【换句话，即“不能被‘2~自身-1’整除”】例1.任意读入一个大于1的整数，判断其是否为素数。【法一:紧扣数学定义】#includeiostreamusingnamespacestd;voidmain(){intx;do{coutx1:\n;cinx;}while(x=1);intk;for(k=2;k=x-1;k++)//穷举的思维if(x%k==0)break;if(x==k)//判断难点coutx是素数\n;elsecoutx不是素数\n;}【用一个小技巧：借助一个“逻辑型”变量：“是素数时为true，否则为false”】#includeiostreamusingnamespacestd;voidmain(){intx;do{coutx1:\n;cinx;}while(x=1);intk;boolflag;flag=true;//首先假设x是素数！for(k=2;k=x-1;k++)//穷举的思维if(x%k==0){flag=false;break;}if(flag==true)coutx是素数\n;elsecoutx不是素数\n;}【用while改写】#includeiostreamusingnamespacestd;voidmain(){intx,k;cinx;k=2;while(x%k!=0)k++;if(k==x)coutx是素数\n;elsecoutx不是素数\n;}【变形一：用sqrt函数，求平方根】#includeiostream#includecmathusingnamespacestd;voidmain(){intx,k;cinx;boolflag=true;for(k=2;k=sqrt(x);k++)if(x%k==0){flag=false;break;}if(flag==true)coutx是素数\n;elsecoutx不是素数\n;}7、插入、删除三、数值计算经典算法：1、辗转相除法求两正整数的最大公约数例：任意读入2个正整数，输出其最大公约数。#includeiostreamusingnamespacestd;voidmain(){intx,y,r;do{cout输入x0、y0:\n;cinxy;}while(!(x0&&y0));r=x%y;while(r!=0){x=y;y=r;r=x%y;}coutyendl;}【改写：用do……while】#includeiostreamusingnamespacestd;voidmain(){intx,y,r;do{cout输入x0、y0:\n;cinxy;}while(!(x0&&y0));do{r=x%y;x=y;y=r;}while(r!=0);coutxendl;}