C++常用算法归纳

1、_C+ 常用算法归纳一、基本算法1、两数交换借助第三数例：任意读入2 个整数，然后按从小到大的顺序输出这两个数。【法 1】#include <iostream>using namespace std;void main()int a,b;cin>>a>>b;a<b?cout<<a<<','<<b:cout<<b<<','<<a;【法 2 ：让 a 中放较小数、b 中放较大数】#include <iostream>using namespa

2、ce std;void main()int a,b;cin>>a>>b;int t; / 中间变量a>b?(t=a,a=b,b=t):(a=a,b=b);cout<<a<<','<<b<<endl;精品资料_【算法解释： “t=a,a=b,b=t ”即可借助，t，将 a 和 b 的值交换。】2、累加例：求 1+2+3+ +100 的和。#include <iostream>using namespace std;void main()int s,i;s=0;i=1;while(i<=

3、100)s=s+i;i=i+1;cout<<"1+2+.+100="<<s;【分析：出循环时，i 为 101 ，其最后一个合法取值（终值）为100 ；本题中s 被称为累加器，它以“s=s+ ”的形式出现在循环中，该式被称为累加式，累加器在进入循环前必须获得合法初值，通常为0。 i 是一个特殊的累加器，每次递增1，又称为计数器。i 身兼二职：控制循环的次数，同时兼做累加式的通项。】3、累乘精品资料_例. 求 10!。【分析： 10！=1 ×2 ×3×10 ，累乘器在进入循环前必须获得合适初值；通常为1。累乘式格式“C=C*

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

5、一 :一重循环 ,难点 : 求出每位数字】#include <iostream>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)cout<<sxh<<endl;【结论：任意一个正整数的个位数字，都可以用“该数%10 ”求得！】【法二：三重循环】#include <iostream>using namespace std;void

6、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)cout<<b*100+s*10+g<<endl;【发现：核心语句if 被执行了 900 次】2、正整数的各数位上数字的获取例 1：任意读入一个正整数，依次输出其低位到高位上的每一位数字。例 2：任意读入一个整数，依次输出其低位到高位上的每一位数字及其符号位，但若是0 不输出符号位。3、迭代法例 1. 猴子吃桃问题。某猴子某天摘了

7、若干只桃子，吃了一半，不过瘾，又多吃一只；第二天又吃了一半，不过瘾，再多吃一只到第十天，发现只剩1 只桃子了。问第一天共摘了多少只桃子。#include <iostream>using namespace std;void main()int peach,day;peach=1;精品资料_for(day=9;day>=1;day-)peach=(peach+1)*2;cout<<" 第一天的桃子数:"<<peach;【归纳：类似于本题peach 变量的特点：其值不停地被新值替代（自身的原值变化而来），直到满足所求终止。 】【问题：能

8、否将上述程序稍作修改，输出每一天的桃子数。】#include <iostream>using namespace std;void main()int peach,day;peach=1;for(day=9;day>=1;day-)peach=(peach+1)*2;cout<<" 第 "<<day<<" 天的桃子数 :"<<peach<<endl;4、排序（ 1 ）冒泡排序法（起泡法）【算法要领： n 个数据最多处理n-1 趟，每一趟从头到尾（或从尾到头）两两相邻的元素进行比

9、较，升序排序时，若前者大后者小，则交换两数，每一趟比前一趟少比较一次。】例：任意读入10 个整数，升序排列后输出。精品资料_#include <iostream>using namespace std;void main()const int N=10;int aN,i,j;for(i=0;i<N;i+)cin>>ai;/外循环处理N-1 趟，控制趟数for(j=1;j<=N-1;j+)for(i=0;i<=N-1-j;i+)/内循环控制每趟比较次数if(ai>ai+1)int t;t=ai;ai=ai+1;ai+1=t;for(i=0;i<

10、;N;i+)cout<<ai<<' '（2 ）选择法排序选择法排序是相对好理解的排序算法。假设要对含有n 个数的序列进行升序排列，算法步骤是：从数组存放的n 个数中找出最小数的下标（算法见下面的“求最值”），然后将最小数与第1个数交换位置；精品资料_除第 1 个数以外，再从其余n-1 个数中找出最小数（即n 个数中的次小数）的下标，将此数与第2 个数交换位置；重复步骤 n-1 趟，即可完成所求。例：任意读入10 个数，然后进行升序排列。 【主函数读入、调用、输出；子函数排序。】#include <iostream>using namespac

11、e 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;i<10;i+)cin>>ai;PX(a,10);/ 为增大子函数灵活性，将元素个数传过去for(i=0;i<10;i+)精品资料_cout<<ai<<endl;/【法 2

12、：以下冒泡法】#include <iostream>#include <iomanip>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<=n-1-j;i+)if(*(p+i)>*(p+i+1)t=*(p+i);*(p+i)=*(p+i+1);*(p+i+1)=t;void main()int a10,i;for(i=0;i<10;i+)cin>>ai;PX(a,10);for(i=0;i<10;i+)cout&l

13、t;<setw(4)<<ai;精品资料_5、查找：顺序查找（线性查找）例：任意读入10 个数，查找其中有无9 这个数。#include <iostream>using namespace std;void main()const int N=10;int aN,i;for(i=0;i<N;i+)cin>>ai;for(i=0;i<N;i+)/正常出口出来，i 为 Nif(ai=9)break;if(i<N)cout<<" 有 "<<endl;elsecout<<" 无

14、"<<endl;【小技巧：定义一个逻辑量】#include <iostream>using namespace std;void main()const int N=10;精品资料_int aN,i;bool flag=false;/先假设无for(i=0;i<N;i+)cin>>ai;for(i=0;i<N;i+)/正常出口出来，i 为 Nif(ai=9)flag=true;break;if(flag!=false)cout<<" 有 "<<endl;elsecout<<&quo

15、t; 无 "<<endl;【用 while 改写】#include <iostream>using namespace std;void main()const int N=10;int aN,i;for(i=0;i<N;i+)cin>>ai;i=0;while(i<=N-1&&ai!=9)i+;if(i<=N-1)cout<<" 有 "<<endl;精品资料_elsecout<<" 无 "<<endl;6、判断素数（质数）数学

16、定义：“凡是只能被 1 和自身整除的大于1 的整数，就称为质数，即素数。”【换句话，即“不能被2 自身 -1 整除】”例 1.任意读入一个大于 1 的整数，判断其是否为素数。【法一 : 紧扣数学定义】#include <iostream>using namespace std;void main()int x;docout<<"x>1:n"cin>>x;while(x<=1);int k;for(k=2;k<=x-1;k+)/穷举的思维if(x%k=0)break;if(x=k)/判断难点cout<<x<

17、;<" 是素数 n"精品资料_elsecout<<x<<" 不是素数 n"【用一个小技巧：借助一个“逻辑型”变量： “是素数时为 true ，否则为 false 】”#include <iostream>using namespace std;void main()int x;docout<<"x>1:n"cin>>x;while(x<=1);int k;bool flag;flag=true;/首先假设x 是素数！for(k=2;k<=x-1;k+)

18、 /穷举的思维if(x%k=0)flag=false;break;if(flag=true)cout<<x<<" 是素数 n"elsecout<<x<<" 不是素数 n"精品资料_【用 while 改写】#include <iostream>using namespace std;void main()int x,k;cin>>x;k=2;while(x%k!=0)k+;if(k=x)cout<<x<<" 是素数 n"elsecout<

19、;<x<<" 不是素数 n"【变形一：用sqrt 函数，求平方根】#include <iostream>#include <cmath>using namespace std;void main()int x,k;cin>>x;bool flag=true;精品资料_for(k=2;k<=sqrt(x);k+)if(x%k=0)flag=false;break;if(flag=true)cout<<x<<" 是素数 n"elsecout<<x<<&

20、quot; 不是素数 n"7、插入、删除三、数值计算经典算法：1、辗转相除法求两正整数的最大公约数例：任意读入2 个正整数，输出其最大公约数。#include <iostream>using namespace std;void main()int x,y,r;docout<<" 输入 x>0 、y>0:n"cin>>x>>y;while(!(x>0&&y>0);r=x%y;精品资料_while(r!=0)x=y;y=r;r=x%y;cout<<y<<e

21、ndl;【改写：用do while 】#include <iostream>using namespace std;void main()int x,y,r;docout<<" 输入 x>0 、y>0:n"cin>>x>>y;while(!(x>0&&y>0);dor=x%y;x=y;y=r;while(r!=0);cout<<x<<endl;2级数计算（展开式的求解）精品资料_例 1、求 1+1/2!+1/3!+ +1/n!+ ，直到某项的值小于10 -6 为止

22、。【法一：直接法（略） 】【法二：间接法（递推法）前项/项次 =后项】#include <iostream>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;cout<<s<<endl;例 2、读入 0<x<1 ，计算 x+x 2+x 3+ xn +直到某项的值小于10 -6 为止。【法一：直接法：直接利用项次描述通项。】#include <iostream>#include <c

23、math>using namespace std;void main()精品资料_float x,s,t;int i;/ 能用整数，不用实数docout<<"0<x<1n"cin>>x;while(x>=1|x<=0);i=1;s=0.0;t=x;while(t >=1e-6)s=s+ t;i+;t =pow(x,i);cout<<s<<endl;3、间接法求通项例 1、读入 0<x<1 ，计算 x+x 2+x 3 + xn +直到某项的值小于10-6 为止。【法二：递推法（间接

24、法）求通项：利用前项求后项。】【分析：本题中若前一项值为t ，则后一项的值为t*x 】#include <iostream>精品资料_using namespace std;void main()float x,s;docout<<"0<x<1n"cin>>x;while(x>=1|x<=0);float t;/用 t 表示通项s=0.0;t=x;while(t>=1e-6)s=s+t;t=t*x; cout<<s<<endl;例 2、求斐比利斯数列的前20 项。 1 、1、2 、3

25、、5 、8、 13 （制定前两项，第三项开始总是前两项之和。 ）【分析：本题只能有间接法（递推法），利用前2 项求后 1 项。】#include <iostream>using namespace std;void main()int f1,f2,f3;f1=f2=1;精品资料_cout<<f1<<""<<f2<<""int i;for(i=3;i<=20;i+)f3=f1+f2;f1=f2;f2=f3;cout<<f3<<""例 3、编程输出形

26、如上图的等腰三角形（行数灵活读入）。*#include <iostream>using namespace std;void main()int h;cout<<" 读入行数 >=1"<<endl;cin>>h;int i=1,j;/ 用二重循环完成（循环的嵌套）while(i<=h)/ 外循环控制行数精品资料_for(j=1;j<=h-i;j+)/第一个循环输出每行的空格cout<<' 'for(j=1;j<=2*i-1;j+) /第二个循环输出每行的星号cout<&

27、lt;'*'cout<<endl;i+;4、矩阵转置矩阵转置的算法要领是：将一个 m 行 n 列矩阵（即m×n 矩阵） 的每一行转置成另一个n×m 矩阵的相应列。例、将以下2 ×3 矩阵转置后输出。即将123转置成144562536#include <iostream>#include <iomanip>using namespace std;void main()int a23,b32,i,j,k=1;for(i=0;i<2;i+)精品资料_for(j=0;j<3;j+)aij=k+;/将 a 转置到 b 中，穷举for(i=0;i<2;i+)/以 a 为基准for(j=0;j<3;j+)bji=aij;for(i=0;i<3;i+)for(j=0;j<2;j+)cout<&l