总结
本系列为C++算法学习系列，会介绍 算法概念与描述，入门算法，基础算法，数值处理算法，排序算法，搜索算法，图论算法， 动态规划等相关内容。本文为枚举算法与模拟算法部分。
大纲要求
【 1 】枚举法
【 1 】模拟法
枚举算法
在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。枚举是一个被命名的整型常数的集合！。
枚举思想
枚举:列出某些有穷序列集的所有成员，或者对一种特定类型对象的计数
①有限的范围
②所有的成员
③特定的类型
根据枚举的定义：
数图形的时候∶
只在一个大图中数。——有限的范围
要求在各种几何形状数图形——所有的成员
从中统计矩形的数量——特定的类型
有同学可能会问∶所有的成员为什么是各种几何图形，而不是所有的矩形呢?
归根结底就是枚举时宁可多，但不能漏!
如果能确定某个问题的答案在一定的范围内，那么我们就列举这个范围内的所有成员（或者确定能包括答案的特定成员)，再通过筛选和判断锁定特定类型，最后得出答案。
定范围
列成员
选类型
算答案
枚举举例
题目描述 统计因数
题目描述
任意一个自然数N都可以分解质因数，如果写出如下形式：
N = P 1 M 1 ∗ P 2 M 2 ∗ . . . ∗ P n M n N=P_{1}^{M1}*P_{2}^{M2}*...*P_{n}^{Mn}N=P1M1∗P2M2∗...∗PnMn
那么N一共有有( M 1 + 1 ) ∗ ( M 2 + 1 ) ∗ . . . ∗ ( M n + 1 ) (M1+1)*(M2+1)*...*(Mn+1)(M1+1)∗(M2+1)∗...∗(Mn+1)个因数，包括1和N本身
例如36 = 2 2 ∗ 3 2 36=2^{2}*3^{2}36=22∗32，那么36一共有(2+1)*(2+1)=9个因数，包括1和36.
解题思路
用枚举思想来验证：
- 定范围：36的因数一定是1到36之间的正整数
- 列成员 1 2 3 4 …36
- 选类型+算答案 1.2.3.4.6.9.12.18.36，共9个。
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { int s=0; for(int i =1; i<=36; i++ ) { if(36%i==0) { cout<<i<<" "; s++; } } cout<<endl<<s; return 0; }
输出为：
题目描述 质数判定
题目描述
如果一个数n，除了1和他本身，没有其他的因数，这个数就是质数
方法一：枚举所有可能是n的因数的数，统计有多少个因数，如果只有两个，那么这个数是质数，否则不是。
方法二：枚举2到n-1之间的自然数，如果存在n的因数，那么这个数可定不是质数，如果不存在n的因数，那么这个数是质数
那么我们怎么“定范围”?——按照方法一的话，范围就是1到这个数本身。
怎么列成员——列举所有的自然数
怎么选类型——判断是否能整除给定数字
怎么算答案——找到一个整除的，则统计因数增加一次，最后看有多少个因数。如果只有2个，那就是质数，否则是合数。
错误方法一：
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { int n=0; cin>>n; int flag = 1;//1表示是质数，0表示不是质数 for(int i =2; i<=n-1; i++ ) { if(n%i==0) { flag = 0; } else{ flag = 1; } } if(flag==1) cout<<"是质数"; else cout<<"不是质数"; return 0; }
优化方法1： 用break实现优化
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { int n=0; cin>>n; int flag = 1;//1表示是质数，0表示不是质数 for(int i =2; i<=n-1; i++ ) { if(n%i==0) { flag = 0; break; } } if(flag==1) cout<<"是质数"; else cout<<"不是质数"; return 0; }
质数判定的进一步优化∶平方根优化。其实我们还可以进一步缩小枚举的范围。过去我们枚举的范围是2到n-1，其实并不必要，只要枚举2-sqrt(n)即可。这是因为，如果n能够分解成两个数的乘积，那么其中一个必须≤sqrt(n)，另外一个≥sqrt(n);这里，sqrt(n)表示n的平方根。
测试2147483647
优化方法2： sqrt(n)
#include <iostream> #include<cmath> //#include<bits/stdc++.h> using namespace std; int main() { int n=0; cin>>n; int flag = 1;//1表示是质数，0表示不是质数 int t = sqrt(n); for(int i =2; i<=t; i++ ) { if(n%i==0) { flag = 0; break; } } if(flag==1) cout<<"是质数"; else cout<<"不是质数"; return 0; }
题目描述 水仙花数
题目描述
水仙花数是一种自幂数，有如下两个特点：
1.是三位数
2.各个数位上的数字的三次方和等于他本身，六日
153= 111 + 555 + 333
输入
无
输出
所有的水仙花数，每一个数字占一行。
样例输入
无
样例输出
153
…
解题思路
定范围：所有的三位数 100-999
列成员：100-999之间所有的自然数
选类型：符合各个数位上数字的三次方和等于本身的才是特点的类型
算答案：找到特点类型数字马上输出
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { for(int i =100; i<=999; i++ ) { int a=i/100,b=i/10%10,c=i%10; if(a*a*a+b*b*b+c*c*c==i) cout<<i<<endl; } return 0; }
输出入下：
题目描述 7744问题
题目描述
列出所有满足下列条件的数字
1.是四位数
2.是完全平方数
3.前2位数字相同，后2位数字也相同
输入
无
输出
每行一个符合条件的数字
样例输入
无
样例输出
7744
…
实现方法1
定范围：所有的四位数 1000-9999
列成员：100-9999之间所有的自然数
选类型：
符合完全平方数，即sqrt(i) = (int)sqrt(i);
且前2位数字相同，后两位数字相同
int a = i/1000,b=i/100%10,c=i/10%10,d=i%10;
if(a==b && c==d)
算答案：找到特点类型数字马上输出
#include <iostream> #include<cmath> //#include<bits/stdc++.h> using namespace std; int main() { for(int i =1000; i<=9999; i++ ) { if(sqrt(i)==(int)sqrt(i)) { int a=i/1000,b=i/100%10,c=i/10%10,d=i%10; if(a==b&&c==d) cout<<i<<endl; } } return 0; }
优化方法2
【7744问题-浮点数运算有误差，如果想避开浮点数应该如何做?】
列成员
用循环变量直接列举1000~9999的完全平方数;
枚举i*i的值，而不是仅枚举i，我们需要根据此需要确定i的范围
定范围
由10000>9999> =i*i>=1000推知:99> =i>=32 ;
for(int i=32;i<=99;i++){
int t=i*i;
}
选类型
前两位相同，后两位相同
把四个数位上数字分别取出再比较:
int a=t/1000,b=t/100%10,c=t/10%10,d =t%10;. if(a= =b&&c==d)则前两位相同，后两位相同;
算答案:
符合条件的t是答案
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { for(int i =32; i<=99; i++ ) { int t=i*i; int a=t/1000,b=t/100%10,c=t/10%10,d=t%10; if(a==b&&c==d) cout<<t<<endl; } return 0; }
题目描述 余数相同问题
题目描述
已知三个正整数a,b,c。
现有一个大于1的整数x，将其作为除数分别除a, b，c，得到的余数相同。请问满足上述条件的x的最小值是多少?
数据保证x有解。
输入
一行，三个不大于1000000的正整数a， b，c，两个整数之间用一个空格隔开。
输出
一个整数，即满足条件的x的最小值。
样例输入
300 262 205
样例输出
19
…
定范围：
数据保证有解，只需要求x最小的值。上限不需确定，找到解后，break就可。
保险起见，余数不会大于被除数和除数，范围可以设定位2到三个数字中的任意一个。
列成员：
从小到大列举范围内的整数
for(int i=2;i<=a;i++){
}
选类型：
分别除以a,b,c 得到的余数相同 a%i==b%i&&b%i==c%i
算答案：
找到特点类型数字i马上输出
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { int a,b,c; cin>>a>>b>>c; for(int i=2;i<=a;i++){ if(a%i==b%i && b%i==c%i){ cout<<i; break; } } return 0; }
题目描述 特殊自然数
题目描述
一个十进制自然数，他的七进制和九进制表示都是三位数，且七进制和九进制数码的表示顺序正好相反，编程求此自然数，并输出显示。
输入
无
输出
三行：
第一行是此自然数的十进制表示；
第二行是此自然数的七进制表示；
第三行是此自然数的九进制表示。
样例输入
无
样例输出
略
…
预备知识
十进制与N进制的互相转换：
N进制：位权为N的数制。
十进制：( 1234 ) 10 = 1 ∗ 1 0 3 + 2 ∗ 1 0 2 + 3 ∗ 1 0 1 + 4 ∗ 1 0 0 (1234)_{10}=1*10^{3}+2*10^{2}+3*10^{1}+4*10^{0}(1234)10=1∗103+2∗102+3∗101+4∗100
从低位到高位分别为第0位，第1位，第2位…
七进制：
( 1234 ) 7 = 1 ∗ 7 3 + 2 ∗ 7 2 + 3 ∗ 7 1 + 4 ∗ 7 0 (1234)_{7}=1*7^{3}+2*7^{2}+3*7^{1}+4*7^{0}(1234)7=1∗73+2∗72+3∗71+4∗70
把N进制的数字按照 位权 展开，计算得到的数字就是十进制的数字了。
N进制下的数位拆分：
十进制下，M%10=十进制表示下的最末尾。
N进制下，M%N=N进制表示下的最末尾。
( 1234 ) 7 = 1 ∗ 7 3 + 2 ∗ 7 2 + 3 ∗ 7 1 + 4 ∗ 7 0 (1234)_{7}=1*7^{3}+2*7^{2}+3*7^{1}+4*7^{0}(1234)7=1∗73+2∗72+3∗71+4∗70
( 1234 ) 7 % 7 = ( 1 ∗ 7 3 + 2 ∗ 7 2 + 3 ∗ 7 1 + 4 ∗ 7 0 ) % 7 = 4 (1234)_{7}\%7=(1*7^{3}+2*7^{2}+3*7^{1}+4*7^{0})\%7=4(1234)7%7=(1∗73+2∗72+3∗71+4∗70)%7=4余数定理
定范围：
在十进制下定范围，七进制和九进制下是三位数
七进制下的最大数位666，最小的三位数位100，转换为十进制得到范围为( 100 ) 7 = 49 , ( 666 ) 7 = 6 ∗ 49 + 6 ∗ 7 + 6 ∗ 1 = 342 (100)_{7}=49,(666)_{7}=6*49+6*7+6*1=342(100)7=49,(666)7=6∗49+6∗7+6∗1=342范围i为[49,342]
九进制下的最大数位888，最小的三位数位100，转换为十进制得到范围为( 100 ) 9 = 81 , ( 888 ) 9 = 8 ∗ 81 + 8 ∗ 9 + 8 ∗ 1 = 728 (100)_{9}=81,(888)_{9}=8*81+8*9+8*1=728(100)9=81,(888)9=8∗81+8∗9+8∗1=728范围i为[81,728]
取公共部分，这个数在十进制表示下，应属于[81,342]
列成员：
列举从81-342范围内的整数
for(int i=81;i<=342;i++){
}
选类型：
七进制和九进制下数字正好相反，设七进制下ABC，九进制下abc
int A=i/7/7%7,B=i/7%7,C=i%7;
int a=i/9/9%9,b=i/9%9,C=i%9;
如果A==c&&B==b&&C==c，那么i符合题意
算答案：
若符合提议，则输出答案，依次输出i,ABC,abc每个答案占据一行
#include <iostream> //#include<bits/stdc++.h> using namespace std; int main() { for(int i=81;i<=342;i++){ int A,B,C,a,b,c; A=i/7/7%7,B=i/7%7,C=i%7; a=i/9/9%9,b=i/9%9,c=i%9; if(A==c&&B==b&&C==a){ cout<<i<<endl; cout<<A<<B<<C<<endl; cout<<a<<b<<c<<endl; } } return 0; }
输出为：
枚举思想
枚举思想
枚举的一般解题步骤
运用枚举的思想解决因数统计、质数判断等问题质数判断的平方根优化
break和continue
N进制的定义
模拟法-一维数组
模拟算法就是模拟题目给的操作，用代码一步一步的描述出来即可。在过程中使用的都是我们已知的各种方法，如数组元素调用、排序、枚举等等，只是这些过程一般比较复杂。本次课程主要针对一位数组的模拟。
题目描述 开关灯
思路引导
因为灯只会出现O和1两种情况，我们可以使用数组元素来表示（类似桶)，随后只需要重复m次，每次寻找当前序号的倍数为下标的元素进行更改，如果是1就变成0，是O就变成1。
最后对数组元素进行判断，找出是0的元素，就行数组元素下标的输出。
输出时要注意的问题是用逗号隔开不同于用空格隔开。如果放在数据后面输出，那么最后一个数据后不应有逗号。这样不方便判断。可以反过来想一想，把逗号放在数据前输出怎么办?
#include<iostream> using namespace std; int a[1010];//全部是0，表示关闭 int main() { int n,m; cin>>n>>m; for(int i=2; i<=m; i++) //从第二个人开始操作 for(int j=i; j<=n; j+=i) //l编号对应倍数下标 if(a[j]==1)a[j]=0; else a[j]=1;//更改状态 int cnt=0; for(int i=1; i<=n; i++) if(a[i]==0) { cnt++;//引入计数器，用于确定第一个编号; if(cnt==1) cout<<i;//r第一个前面不需要逗号; else cout<<","<<i;//其他要间隔逗号输出 } return 0; }
题目描述 序列操作和查询
思路引导
对题目的要求一步一步的实行，先保证数组的输入以后，需要对三种情况进行分类处理。
第一种处理里面有输出，后面两种都是在操作。操作的要点是数组的插入和删除。
插入的话，就要求插入位置后面所有数字向后移动一步，数组长度增加，从后往前实现a[i+1]=a[i]的操作;
而删除则需要当前位置后面所有的数字向前移动一步，实现a[i]=a[i+1]。这里需要注意移动的方向。
#include<iostream> using namespace std; int a[1001]; int main() { int n,m,p,q,v; cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; cin>>m; for(int i=0; i<m; i++) { cin>>p; if(p==1) { cin>>q; cout<<a[q]<<endl; } else if(p==2) { cin>>q>>v; for(int j=n; j>=q; j--) //挨个向后移动 a[j+1]=a[j]; a[q]=v;//单独把插入的数字放入位置 n++;//数组长度加1 } else //p==3 { cin>>q; for(int j=q; j<n; j++) //挨个向前移动 a[j]=a[j+1]; n--;//数组长度减1} } } return 0; }
题目描述 数组折叠
思路引导
数组对折，需要把后半部分移动到前半部分对应位置进行数组相加，所以移动次数为n/2(即循环次数)，然后需要进行的就是数组加法，最后要对数组长度也做n/2的操作，但是这里需要注意的是，如果长度是奇数不能只是简单的n/2哦。
对称位置怎么找?如果数组下标从1开始，那么第i个元素的对称元素位置是谁?
找找规律:1对n ;2对n-1;3对n-2 ;i对什么?
#include<iostream> using namespace std; int a[10010]; int main() { int n,m; cin>>n>>m; for(int i=1; i<=n; i++)cin>>a[i]; for(int i=1; i<=m; i++) { for(int j=1; j<=n/2; j++) //第一个到中间会变化 a[j]+=a[n-j+1]; //当前位置元素加上中线对称的元素 if(n%2!=0) //长度为奇数的数组特殊处理 n++; n/=2; //数组长度对折 } for(int i=1; i<=n; i++) cout<<a[i]<<' '; return 0; }
题目描述 数字消除
#include<iostream> using namespace std; int s[10010]; int main() { int n,a,num; cin>>n>>a; for(int i=1;i<=n;i++) cin>>s[i]; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ //从i出发，找与a相同的 if(s[j]==a) num++; else break; } if(num>=3)//如果练习相同的超过3个 i=i+num-1;//将下标跳过 else cout<<s[i]<<" ";//否则正常输出 num=0;//计数器归零 } return 0; }
模拟法-图形模拟
通过代码实现图形的变化，如放大、缩小、旋转等。这里说的图形大多数可以看成是二维数组，主要是对二维数组行下标和列下标的深入研究。
题目描述 图像放大
#include<iostream> using namespace std; int a[110][110]; int ans[110][110]; int m,n,k; int main() { cin>>m>>n>>k; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; int x=(i-1)*k; int y=(j-1)*k; for(int u=x+1;u<=x+k;u++){ for(int v=y+1;v<=y+k;v++){ ans[u][v]=a[i][j]; } } } } for(int i=1;i<=m*k;i++){ for(int j=1;j<=n*k;j++){ cout<<ans[i][j]<<" "; } cout<<endl; } return 0; }
题目描述 图像旋转
将数组逆时针旋转90度
#include<iostream> using namespace std; const int N = 1005; int jpg[N][N]; int main() { int n ,m; cin>>n>>m; for(int i = 0; i < n; i ++) for(int j = 0; j < m; j++) cin>>jpg[i][j]; for(int i = m-1; i >= 0; i-- ) { for(int j = 0; j < n; j++) cout<<jpg[j][i]<<" "; cout<<endl; } return 0; }
题目描述 图像左右翻转
#include<iostream> using namespace std; const int N = 1005; int a[N][N],b[N][N]; int main() { int n,m; cin>>n>>m; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j++) { cin>>a[i][j]; b[i][m-j+1]=a[i][j]; } } for(int i =1; i <= n; i++ ) { for(int j = 1; j <= m; j++) cout<<b[i][j]<<" "; cout<<endl; } return 0; }
题目描述 二维数组回形遍历
给定一个row行col列的整数数组array，要求从array[0][0]元素开始，按回形从外向内顺时针顺序遍历整个数组。如图所示：
输入
输入的第一行上有两个整数，依次为row和col。
余下有row行，每行包含col个整数，构成一个二维整数数组。
（注：输入的row和col保证0 < row < 100, 0 < col < 100）
输出
按遍历顺序输出每个整数。每个整数占一行。
样例输入
4 4
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
样例输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream> using namespace std; int a[100][100]; int n,m,r1,r2,c1,c2; int main() { cin>>n>>m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>a[i][j]; r1=1; r2=n; c1=1; c2=m; while(r1<=r2&&c1<=c2) { for(int j=c1; j<=c2; j++) cout<<a[r1][j]<<endl; for(int i=r1+1; i<=r2; i++) cout<<a[i][c2]<<endl; if(r1!=r2) for(int j=c2-1; j>=c1; j--) cout<<a[r2][j]<<endl; if(c1!=c2) for(int i=r2-1; i>r1; i--) cout<<a[i][c1]<<endl; r1=r1+1; r2=r2-1; c1=c1+1; c2=c2-1; } return 0; }
