C++常用算法归纳.doc

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+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！=12310，累乘器在进入循环前必须获得合适初值；通常为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=13+53+33。【法一:一重循环,难点:求出每位数字】#include using 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+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=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趟，每一趟从头到尾（或从尾到头）两两相邻的元素进行比较，升序排序时，若前者大后者小，则交换两数，每一趟比前一趟少比较一次。】例：任意读入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个数的序列进行升序排列，算法步骤是：从数组存放的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=*(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;j=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; 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为N if(ai=9)break; if(iN) cout有endl; else cout无endl;【小技巧：定义一个逻辑量】#include using namespace std;void main()const int N=10; int aN,i; bool flag=false; /先假设无 for(i=0;iai; for(i=0;iN;i+)/正常出口出来，i为N if(ai=9)flag=true;break; if(flag!=false) cout有endl; else cout无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; else cout无endl;6、判断素数（质数）数学定义：“凡是只能被1和自身整除的大于1的整数，就称为质数，即素数。”【换句话，即“不能被2自身-1整除”】例1.任意读入一个大于1的整数，判断其是否为素数。【法一: 紧扣数学定义】#include using namespace std;void main()int x; do cout1:n; cinx; while(x=1); int k; for(k=2;k=x-1;k+) /穷举的思维 if(x%k=0)break; if(x=k) /判断难点 coutx是素数n; else coutx不是素数n;【用一个小技巧：借助一个“逻辑型”变量：“是素数时为true，否则为false”】#include using namespace std;void main()int x; do cout1: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; else coutx不是素数n;【用while改写】#include using namespace std;void main()int x,k; cinx; k=2; while(x%k!=0)k+; if(k=x) coutx是素数n; else coutx不是素数n;【变形一：用sqrt函数，求平方根】#include #include 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; else coutx不是素数n;7、插入、删除三、数值计算经典算法：1、辗转相除法求两正整数的最大公约数例：任意读入2个正整数，输出其最大公约数。#include using namespace std;void main()int x,y,r; do cout0、y0:n; cinxy; while(!(x0&y0); r=x%y; while(r!=0) x=y;y=r;r=x%y; coutyendl;【改写：用dowhile】#include using namespace std;void main()int x,y,r; do cout0、y0:n; cinxy; while(!(x0&y0); do r=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; 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;/能用整数，不用实数 do cout0xx; while(x=1|x=1e-6) s=s+ t; i+;t =pow(x,i); coutsendl;3、间接法求通项例1、读入0x1，计算x+x2+x3+xn+直到某项的值小于10-6为止。【法二：递推法（间接法）求通项：利用前项求后项。】【分析：本题中若前一项值为t，则后一项的值为t*x】#include using namespace std;void main()float x,s; do cout0xx; 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; coutf1 f2 ; 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列矩阵（即mn矩阵）的每一行转置成另一个nm矩阵的相应列。例、将以下23矩阵转置后输出。即将 1 2 3 转置成 1 4 4 5 6 2 5 3 6#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=aij; for(i=0;i3;i+) for(j=0;j2;j+) coutsetw(3)bij; coutendl; 5、杨辉三角形杨辉三