C++常用算法归纳

《C++常用算法归纳》由会员分享，可在线阅读，更多相关《C++常用算法归纳（25页珍藏版）》请在装配图网上搜索。

1、C+常用算法归纳一、基本算法1、两数交换借助第三数例：任意读入2个整数，然后按从小到大的顺序输出这两个数。【法1】#include using namespace std;void main()int a,b;cinab;ab?couta,b:coutb,a;【法2 ：让a中放较小数、b中放较大数】#include using namespace std;void main()int a,b;cinab;int t; /中间变量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

2、+3+100的和。#include using namespace std;void main()int s,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! =1X2MX10,累乘器在进入循环前必须获得合适初值

3、；通常为 1。累乘式格式C=C*”必须出现在循环中。注意，不要让累乘器溢出。】#include using namespace std;void main()long C;int i;C=1;i=1;while(i=10)C=C*i;i+;coutCendl;【思考：能否将本程序稍做修改，分别输出1!10 !】二、非数值计算常用经典算法1、穷举法对所有的可能性进行判断，凡是符合条件的做相应处理(输出、保存等) 。例：输出所有的“水仙花”数，即这样的三位正整数：其每一数位上的数字的立方之和等于该数本身。比如，153=1 3+53+33。【法一：一重循环，难点：求出每位数字】#include us

4、ing namespace std;void main()int sxh;int b,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”求得!】【法二：三重循环】#include using namespace std;void main()int b,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+

5、g*g*g=b*100+s*10+g)coutb*100+s*10+gendl;【发现：核心语句if被执行了 900次】2、正整数的各数位上数字的获取例1：任意读入一个正整数，依次输出其低位到高位上的每一位数字。例2：任意读入一个整数，依次输出其低位到高位上的每一位数字及其符号位，但若是0不输出符号位。3、迭代法例1.猴子吃桃问题。某猴子某天摘了若干只桃子，吃了一半，不过瘾，又多吃一只；第二天又吃了一半，不过瘾，再多吃一只到第十天，发现只剩1只桃子了。问第一天共摘了多少只桃子。#include using namespace std;void main()int peach,day;peach

6、=1;for(day=9;day=1;day-)peach=(peach+1)*2;cout第一天的桃子数：peach;【归纳：类似于本题peach变量的特点：其值不停地被新值替代(自身的原值变化而来)直到满足所求终止。】【问题：能否将上述程序稍作修改，输出每一天的桃子数。】#include using namespace std;void main()int peach,day;peach=1;for(day=9;day=1;day-)peach=(peach+1)*2;cout第day天的桃子数：peachendl;4、排序(1)冒泡排序法(起泡法)【算法要领：n个数据最多处理n-1趟，每

7、一趟从头到尾(或从尾到头)两两相邻的元素进 行比较，升序排序时，若前者大后者小，则交换两数，每一趟比前一趟少比较一次。例：任意读入10个整数，升序排列后输出。#include using namespace std;void main()const int N=10;int aN,i,j;for(i=0;iai;外循环处理N-1趟，控制趟数for(j=1;j=N-1;j+)for(i=0;iai+1)int t;t=ai;ai=ai+1;ai+1=t;for(i=0;iN;i+)coutai ;(2)选择法排序选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是：

8、从数组存放的n个数中找出最小数的下标(算法见下面的“求最值”)，然后将最小数与第1个数交换位置；除第1个数以外，再从其余 n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置；重复步骤n-1趟，即可完成所求。例：任意读入10个数，然后进行升序排列。【主函数一读入、调用、输出；子函数一排序。#include using namespace std;void PX(int *p,int n) / 【法 1:选择法】int i,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=

9、*(p+i);*(p+i)=*(p+k);*(p+k尸t;void main()int a10,i;for(i=0;iai;PX(a,10);/为增大子函数灵活性，将元素个数传过去for(i=0;i10;i+)coutaiendl;【法2:以下冒泡法】#include #include using namespace std;void PX(int *p,int n)int i,j; int t;for(j=1产n-1;j+)for(i=0;i*(p+i+1)t=*(p+i);*(p+i)=*(p+i+1);*(p+i+1)=t;void main()int a10,i;for(i=0;iai

10、;PX(a,10);for(i=0;i10;i+)coutsetw(4)ai;5、查找：顺序查找(线性查找)例：任意读入10个数，查找其中有无9这个数。#include using namespace std;void main()const int N=10;int aN,i;for(i=0;iai;for(i=0;iN;i+) 正常出口出来，i 为 Nif(ai=9)break;if(iN)cout有endl;elsecout无endl;【小技巧：定义一个逻辑量】#include using namespace std;void main()const int N=10;int aN,i;

11、bool flag=false;先假设无for(i=0;iai;for(i=0;iN;i+) 正常出口出来，i 为 Nif(ai=9)flag=true;break;if(flag!=false)cout有endl;elsecout无endl;【用while改写】#include using namespace std;void main()const int N=10;int aN,i;for(i=0;iai;i=0;while(i=N-1&ai!=9)i+;if(i=N-1)cout有endl;cout无endl;6、判断素数(质数)数学定义：“凡是只能被1和自身整除的大于1的整数，就称为

12、质数，即素数。【换句话，即“不能被2自身-1整除”例1.任意读入一个大于1的整数，判断其是否为素数。【法一：紧扣数学定义】#include using namespace std;void main()int x;docout1:n;cinx;while(x=1);int k;for(k=2;k=x-1;k+) 穷举的思维if(x%k=0)break;if(x=k)判断难点coutx是素数 n;coutx不是素数 n;【用一个小技巧：借助一个“逻辑型”变量：“是素数时为true,否则为false】#include using namespace std;void main()int x;doc

13、out1:n;cinx;while(x=1);int k;bool flag;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改写】#include using namespace std;void main()int x,k;cinx;k=2;while(x%k!=0)k+;if(k=x)coutx是素数 n;elsecoutx不是素数 n;【变形一：用sqrt函数，求平方根】#include #inclu

14、de using namespace std;void main()int x,k;cinx;bool flag=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个正整数，输出其最大公约数。#include using namespace std;void main()int x,y,r;docout0、y0:n;cinxy;while(!(x0&y0);r=x%y;whi

15、le(r!=0)x=y;y=r尸x%y;coutyendl;【改写：用dowhile #include using namespace std;void main()int x,y,r;docout0、y0:n;cinxy;while(!(x0&y0);dor=x%y;x=y;y=r;while(r!=0);coutxendl;2.级数计算(展开式的求解)例1、求1 + 1/2!+1/3!+1/n!+，直到某项的值小于10-6为止。【法一：直接法(略)】【法二：间接法(递推法)前项 /项次=后项】#include using namespace std;void main()float s,t

16、;int i; /表示项次s=0; t=1; i=1;while(t=1e-6)s=s+t;i+;t=t/i;coutsendl;例2、读入0x1 ,计算x+x2+x3+xn +直到某项的值小于10-6为止。【法一：直接法：直接利用项次描述通项。】#include #include using namespace std;void main()float x,s,t;int i;能用整数，不用实数docout0xx;while(x=1|x=1e-6)s=s+ t;i+；t =pow(x,i);coutsendl;3、间接法求通项10-6为止。例1、读入0x1 ,计算x+x2+x3+xn +直到

17、某项的值小于【法二：递推法(间接法)求通项：利用前项求后项。】【分析：本题中若前一项值为t,则后一项的值为t*x】#include using namespace std;void main()float x,s;docout0xx;while(x=1|x=1e-6)s=s+t;t=t*x; coutsendl;例2、求斐比利斯数列的前20项。1、1、2、3、5、8、13(制定前两项，第三项开始总是前两项之和。)【分析：本题只能有间接法(递推法)，利用前2项求后1项。】#include using namespace std;void main()int f1,f2,f3;f1=f2=1;co

18、utf1f2n.int i;for(i=3;i=20;i+)f3=f1+f2;f1=f2;f2=f3;coutf3;例3、编程输出形如上图的等腰三角形(行数灵活读入)*#include using namespace std;void main()int h;cout=1h;int i=1,j;/用二重循环完成(循环的嵌套)while(i=h)/外循环控制行数for(j=1;j=h-i;j+)第一个循环输出每行的空格cout;for(j=1;j=2*i-1;j+) 第二个循环输出每行的星号cout*;coutendl;i+；4、矩阵转置矩阵转置的算法要领是：将一个m行n列矩阵(即mxn矩阵)的

19、每一行转置成另一个nXm矩阵的相应列。例、将以下2q矩阵转置后输出。即将 123转置成 144562536#include #include using namespace std;void main()int a23,b32,i,j,k=1;for(i=0;i2;i+)for(j=0;j3;j+)aij=k+；/将a转置到b中，穷举for(i=0;i2;i+) 以 a 为基准for(j=0;j3;j+)bji=aijfor(i=0;i3;i+)for(j=0;j2;j+)coutsetw(3)bij;coutendl;5、杨辉三角形杨辉三角形的每一行是（x+y）n的展开式各项的系数。例如第一

20、行是（x+y）,其系数为1; 第二行是（x+y）1,其系数为1,1;第三行是（x+y）2,其展开式为x2+2xy+y2,系数分别为1, 2, 1;直观形式如下：11 12 2113 311 464115101051分析以上形式，可以发现其规律：是 n阶方阵的下三角，第一列和主对角线均为1,其余各元素是它的上一行、同一列元素与上一行、前一列元素之和。例、编程输出杨辉三角形的前10行。#include #include using namespace std;void main()const int N=10;int aNN,i,j;给主对角线、第一列元素赋值for(i=0;iN;i+)aii=a

21、i0=1;/以下双循环完成其他元素赋值for(i=2;i=N-1;i+)for(j=1;j=i-1;j+)aij=ai-1j-1+ai-1j;for(i=0;iN;i+)for(j=0;j=i;j+)coutsetw(4)aij;coutendl;6、求最值(最大、最小)例、任意读入10个整数，输出其中的最大值。#include using namespace std;void main()const int N=10;int aN,i;int max;for(i=0;iai;max=a0;/假设第一个获最后一个最大for(i=1;imax)max=ai;coutMAX=maxendl;Welcome ToDownload !欢迎您的下载，资料仅供参考！