7.1简单枚举
例题7.1
fghij = n * abcde，
所以并不需要直接枚举10个数，而是枚举其中的一半即可。
枚举方式为从最小值（0）1234递增最大值98765。
这之中有一个值得注意的问题是 判断这个数是否有重复出现的数字。
由于这个数字最大为5位，所以复杂度是还是
问题不大，但是如果这个数是一个元素极大的数组，我们就需要考虑算法的问题了。
这也曾是今日头条的一道面试题，下面链接中对具体方法有详细说明：
https://blog.csdn.net/chender_sysu/article/details/64906546
我也将其抄录到了我的代码中。
#include<iostream>
#include<vector>
using namespace std;
const int Max = 98765;
const int Min = 1234;
//是否重复
bool Isrepeat(int a, int b){
// 检查a b自身是否重复。
int count[10] = {0};
while(a!=0){
int enda = a%10;
a = a/10;
if(count[enda]!=0)
return true;
count[enda]++;
}
while(b!=0){
int endb = b%10;
b = b/10;
if(count[endb]!=0)
return true;
count[endb]++;
}
return false;
}
//时间复杂度为O(n)，空间复杂度为O(1)
bool repeat(vector<int> &v) {
for (int i = 0; i < v.size(); i++) {
while (v[i] != i){ //v[i] 和 i未对应
int temp = v[i];
if (v[i] == v[temp])//i 与 temp不同值，如果两个不同值下标对应了同一个值，则说明这个数组中存在相同元素。
return true;
else { // 假设v[1] = 2, v[2] = 10 这一步操作在 v[1] = 10, v[2] = 2(值存储的位置虽然变化，但值2,10并没有丢失)
int t = v[i];
v[i] = v[temp];
v[temp] = t;
}
}
}
return false;
}
int main(){
int n;
while(cin>>n&&n!=0){
int ae;
for(int i=Min;i<Max;i++){
ae = i*n;
if(ae<Max)
if(!Isrepeat(ae,i))
cout<<ae<<endl<<i<<endl;
}
}
return 0;
}
7.2枚举排列
7.2.1生成1~n的排列
合上书照自己的理解写了一下，特别注意A的意义，它到底存储了什么，先前阅读的时候忽略了书本开头部分内容的说明，导致看的时候有些疑惑。
void print_permutation(int n, int *A, int cur){// n为输入数字，A存储着已经排列好的数，cur为A的长度
int i,j;
if(cur == n){// n和cur相等，意味着A中已经存储着n个已经排列好的数，此时函数目的达成，直接输出。
for(int i=0; i<n; i++)
cout<<A[i];
cout << endl;
}
else
for(i=1;i<=n;i++){//从所有能选的数字(1~n)中选择能使用的数字
for(j=0;j<cur;j++)//所有数字中，需排除已经排列好的数字
if(A[j] == i)
break;
if(j==cur){//j-cur循环正常退出，说明i尚未排列
A[cur] = i;//将i排列入A
// cur = cur + 1;
// print_permutation(n, A, cur);这样写是错的，为什么
print_permutation(n, A, cur+1);
}
}
}
7.2.2生成可重集的排列
在7.2.1中，待排列数是数字1到n，而这里待排列数为一个数组P。
这里主要解决一个问题：P中如果有重复元素怎么办？
当P中有重复元素时，这段检查是否已排列的代码显然不适用。
for(j=0;j<cur;j++)//所有数字中，需排除已经排列好的数字
if(A[j] == i)
break;
书中已经给出了详细的修改方法，这里不再赘述。
解释一个我在阅读过程中疑惑的问题：
为什么第一步修改后，会输出27个1 1 1 ？
——因为没有正确处理重复，第一个位置上可以填1 1 1， 第二个位置上也可以填1 1 1， 第三个位置还是可以填1 1 1（都满足c1 < c2的条件，每次都可以从头从待取用的数P中取得第一个1）确实会输出3x3x3个1 1 1。类比一下，假设P中的元素为1 2 3，则取完1 后，只能从2开始取，而不能重复取1。（我已经尽力表述了...）
7.2.3解答树
从“什么都没做”到逐步生成完整解的过程，叫“解答树”。
解答树上的结点数几乎全部来自于最后一二层，与之相比，其它的可以忽略不计。
7.2.4下一个排列
C++的STL中有个“next_permutation”函数可以直接求“下一个排列”，而且适用于可重集，试了一下，非常好用。
#include<iostream>
#include<algorithm>//next_permutation在此库中
using namespace std;
int main(){
int n=4,p[4];
for(int i=0;i<n;i++)
cin>>p[i];
do{
for(int i=0;i<n;i++)
cout<<p[i];
cout<<endl;
}while(next_permutation(p, p+n));
getchar();
getchar();
return 0;
}
7.3子集生成
7.3.1增量构造法
这个当时理解了好久，简单画了一下当n=3时候的解答树就清楚多了。（未画完）
当n=3时的解答树.png
void print_subset(int n, int *A, int cur){ //0到n为待选数
for(int i=0; i<cur; i++)
printf("%d ", A[i]);
cout<<endl; // 由于cur初始值为0，输出首行会为空行。
int s= cur?A[cur-1]+1 : 0; //经测试，三目运算法优先级比赋值语句高
//s从最小的元素开始，
//什么叫做最小元素呢？就是比之前输出的最大的元素大1.
//显然，刚输出的最大的元素就是最后输出的那个元素，即A[cur-1],所以就从最小元素A[cur-1]+1开始选择啦。
for(int i=s; i<n; i++){
A[cur] = i;
print_subset(n, A, cur+1);
}
}
7.3.2位向量法
这个就非常好理解了，构造01向量，来表示具体元素是否存在。
每一个元素都只有两种状态，存在和不存在。
所以代码中让B[cur] = 1，递归，B[cur] = 0，递归。
7.3.3二进制法
用二进制的01来表示集合元素存在与否的状态。
对于包含从1~n的集合来说，它的子集个数用二进制可以表示为从1递增到n（假设n为3，那么它的子集可以表示为 001 010 011 100 101 110 111）
这样，枚举出全部的子集就变得非常容易，如书上所说：“枚举子集和枚举整数一样简单”。
这里简单解释一下输出子集的代码：
//枚举子集之后就要输出，这个函数的作用是将二进制数转化成对应的子集输出，比如111， 你要将其输出为集合{2,1,0}
void print_subset(int n, int s){ //s为一个二进制数，表示当前待输出子集（比如111， 就表示 集合{2,1,0}）
for(int i=0;i<n; i++)// 这个循环的目的，就是控制输出s的每一位
if(s&(1<<i)) printf("%d ", i);//1<<i，表示将0000 0001（假设为8位） 左移i位补0，&上s，就是单独提取出s每一位二进制的具体值
printf("\n");
}
7.4回溯法
7.4.1八皇后问题
思路不难理解，相关细节我都注释在了代码中。
判断是否在同一条对角线大家可以直接参照书上的图观察，
对角线/上所有的点，它们横纵坐标的差是相等的，
对角线\上所有的点，它们横纵坐标的和是相等的。
再加上对纵坐标的比较，就可以得出该坐标上是否可以放置皇后了。
int C[100];
int tot = 0; //总共的解的个数
void search(int n, int cur){
if(cur == n) tot ++;//当前行等于n,则说明皇后已处理到最后一行，此时解已经求得。
else for(int i=0;i<n;i++){
C[cur] = i;//cur行的皇后放在i列
//判断放在该列是否可以
int ok = 1;
for(int j=0;j<cur;j++)
if(cur+C[cur] == j+C[j] || cur-C[cur] == j-C[j] || C[cur] == C[j]){
ok = 0;
break;
}
if(ok)
search(n, cur+1);
}
}
利用二维数组vis[2][]以提高效率
int tot = 0; //总共的解的个数
int vis[3][100];
void search_vis(int n, int cur){
if(cur==n) tot++;
else
for(int i=0;i<n;i++)
//vis[0][]记录了列的标致，vis[1][]记录了/对角线的标志，vis[2][]记录了\对角线的标志
if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]){//+n是为防止出现负数溢出，+n并不会改变该数字的标志功能。
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;//对所选择的皇后位置 所能影响的范围进行标记。
search_vis(n, cur+1);//如果函数回朔至此处，则说明这一步选择的位置不行，得抹掉它的数据，包括它存取的列，主副对角线标志，故下一步对其进行清0还原
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;//如果函数未回朔到此处，则说明这一步选择的位置正确，也不会执行该语句。
}
}
7.4.2其它应用举例
例题7-4素数环
由于题目要求从整数1开始逆时针排列，所以我在A数组初始化时直接给A[0]赋值为1，这时候cur便不再是从0开始，而是从1开始，一定要注意，如果写成从0开始，就不会有任何输出了，这里耽误了我大把时间，那种明明和书上一样为什么我的错了的感觉（kuT.T）。
#include<iostream>
#include<math.h>
using namespace std;
//素数判断 可以使用打表法，因为百度过程中此种方法未曾见过所以用了，具体自己百度
bool Isprime(int a){
if(a == 2 || a == 3 || a == 5)
return true;
if(a%6!=1 && a%6!=5)
return false;//大于6不与6的倍数相邻，一定不是质数
for(int i=5; i<sqrt(a); i+=6)
if(a%i==0 || a%(i+2)==0) // 和6的倍数相邻的数，6n-1 和 6n-1 + 2
return false;
return true;
}
int A[10] = {1,0};//存放排列好的数字，形成最终的素数环，题目要求从1开始所以A[0]=1
int vis[10] = {1,0};//存放数字1-n是否使用过的标志，0已经使用过了所以vis[0]=1
int n;//从1开始整数的个数
void PrimeRing(int cur){
if(cur==n && Isprime_(A[0] + A[n-1])){ //cur到末尾且首尾相接，cur走到n,实际上A数组的最大下标是n-1(因为下标从0开始，下标到n-1意味着数组存了n个数)
for(int k=0;k<n;k++){//输出数组A
cout << A[k];
}
cout<<endl;
}
else
for(int i=2;i<=n;i++){
if(!vis[i] && Isprime_(A[cur-1] + i)){ //符合条件：数字i未使用过，且i与前个数相加为素数
A[cur] = i;
vis[i] = 1;
PrimeRing(cur+1);
vis[i] = 0; //函数回朔，说明此值实际不和条件，将它已经使用过的标志清除
}
}
}
int main(){
cin >> n;
PrimeRing(1);//A中已经预先存了1这个数，所以cur是从1开始而不是从0开始。
getchar();
getchar();
return 0;
}
例题7-5 困难的串
思路不难，按字典序枚举每一位的可能的值，当字典序达到题目要求数时结束。
难的是怎样判断当前串是简单串还是困难串。
书中说我们只需要判断当前串的后缀，意思是我们选取当前串倒数2 4 6···2j，（2j<当前串长cur），依次判断其是否由重复串组成，这之中如有任何一个有重复，则该串为简单串，不符合组成字典序排列的条件。具体比较步骤可以参照下图：
比较示意图.PNG
#include<iostream>
using namespace std;
int tot;//第tot个困难的串
int A[50]={0};//存储困难的串
int n;
int L;
int dfs(int cur){//cur是串的位数，第cur位串可能不止能填一个值
if(tot++ == n){//函数每执行一次，cur不一定增加（返回值为1的情况），但tot一定增加
for(int i=0;i<cur;i++){
printf("%c ", 'A'+A[i]);
}
cout<<endl;
return 0;
}
else{
for(int i=0;i<L;i++){
A[cur] = i;//尝试将i放入
int ok=1;
for(int j=1; j*2<=cur+1; j++){
int equal = 1;
for(int k=0;k<j;k++)
if(A[cur-k] != A[cur-j-k]){//不相等就有戏，说明不是重复的
equal = 0;
break;
}
if(equal){
ok = 0;
break;
}
}
if(ok)//如果合适，在下一个位置（cur）继续放（按照字典序，如果这个位置既可以放A，也可以放B，则应该先放A，字典序ABAC 在ABC前）
if(!dfs(cur+1)) return 0;//如果在放置的过程中，所遍历的字典序已经达到了题目要求的n,则应退出函数。
}
return 1;//从0到L-1全部都无法组成困难的串时返回1
}
}
int main(){
tot = 0;
cin>>n>>L;
dfs(0);
getchar();
getchar();
return 0;
}
例题7-6宽带
参考链接：https://blog.csdn.net/richenyunqi/article/details/100695488
开始题目意思都没看懂，参考链接后收益匪浅，对C++处理字符串有了全新的认识。
#include<iostream>
#include<stdio.h>
#include<map>
#include<unordered_map>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
string input, ans;
map<char, vector<char>> graph;
int MinWidth = 100;
void getdata(){
graph.clear();
input = input + ";";
for(int i=0, j=0; i<input.size(); i=j+1){
j = input.find(';', i); //查找给定位置i后的字符串
for(char c : input.substr(i+2, j-(i+2))){//substr(i,j)的功能类似于一个切片,选取从i开始往后j个数
graph[input[i]].push_back(c);//顶点i的邻接点
graph[c].push_back(input[i]);//顶点i(input[i])的邻接点为c,c的邻接点为i
//上两步操作会导致重复，比如A的邻接点为FBF，但是计算它们与A点的距离时，不过多算了一次而已，问题不大。
}
}
input="";
for(auto& i : graph)
input = input + i.first;//map<first, second>
}
int main(){
input = "A:FB;B:GC;D:GC;F:AGH;E:HD";
ans = "";
getdata();
do{
//记录当前排列下结点的位置
unordered_map<char, int> position;
for(int i=0;i<input.size();i++)
position[input[i]] = i;
//计算带宽width
int width = -1;
int ok = 1;
for(auto& i : graph){
int Nodewidth = -1;
for(char c : i.second){
Nodewidth = max(Nodewidth, abs(position[c]-position[i.first]));
}//计算该结点的带宽
width = max(width, Nodewidth);//计算该排列下图的带宽
if(Nodewidth > MinWidth){//如果该结点的带宽 大于 最小带宽，说明该排列不行，直接退出
ok = 0;
break;
}
}
if(ok)
if(width < MinWidth){
MinWidth = width;
ans = input;
}
}while(next_permutation(input.begin(), input.end()));//next_permutation()按字典序生成下一个排列
for(char c : ans)
cout<<c;
cout << endl;
getchar();
getchar();
return 0;
}
例题7-7天平难题
这题使用回溯，思路非常清晰。
使用数据表存储结点（挂坠），每次从结点集合中取出一个点，组成一颗二叉树，再取出一个点······直到所有的点都被取完，二叉树也就构造成功，从而可以计算天平总长度。
显然，这样的二叉树有s！种，好在s的值最大为6。
构造树的过程如书上图7-13。
该怎样计算天平总长度呢？
计算天平长度.PNG
如上图不难发现，天平的总长度，就等于顶上的长度1，加上挂在左边结点的左长度（红色部分），加上挂在右边结点的右长度（黄色部分）。
当一个天平与另一个天平结合时，被悬挂在左边和被悬挂在右边结果是不相同的。（被悬挂在左边时，被悬挂天平的左长度起作用，被悬挂在天平右边时，被悬挂天平的右长度起作用）
在已知左右重量的情况在，左右长度可以根据书上公式na = mb和一个天平长度为1求得。
另外，注意计算长度的时间。
当我们选取一个结点与原有结点形成二叉树时，形成的天平相当于上图中最顶上那个天平，此时，我们并不知道他会被悬挂在哪边，故我们无法判断它的左右长度哪个会起作用。
但是我们可以计算出他下面悬挂着的结点的有效长度，因为它们已经被悬挂。
#include<iostream>
using namespace std;
typedef struct treeNode{
double r = 0;//左端重量
double l = 0;//右端重量
int p = -1;
}treeNode;
double width_left = 0;
double width_right = 0;
treeNode Node[20];
double r = 2.0;
int s = 3;
int W[100] = {1,2,1};
double width = 0;
void treedfs(int weight, int pos){//weight是当前结点的重量，函数的作用是选择一个未使用的结点与该结点 结合，存入坐标pos中
int ok = 1;
for(int i=0;i<s;i++){ //遍历所有结点（不包括组成的新结点）
if(Node[i].p==-1){//i未使用过
ok = 0;
Node[i].p = pos;//该点未使用过，则该点的双亲结点设置为pos
//与该结点结合有两种组合方式，weight在左和在右
Node[pos].l = weight;
Node[pos].r = W[i];
if(pos-1 < s)
width_left = width_left + 0;//叶子结点所增加的长度为0,Node[s]之前存储的皆为叶子结点
else width_left = width_left + (Node[pos-1].r)/(Node[pos-1].l + Node[pos-1].r);//上一个二叉树的左长度外露
treedfs(weight+W[i], pos+1);//递归选择下一个点
width_left = width_left - (Node[pos-1].r)/(Node[pos-1].l + Node[pos-1].r);
//上一步选择结束后，开始尝试调换方向放置
Node[pos].r = weight;
Node[pos].l = W[i];
if(pos-1 < s)
width_right = width_right + 0;
else width_right = width_right + (Node[pos-1].l)/(Node[pos-1].l + Node[pos-1].r);
treedfs(weight+W[i], pos+1);
width_right = width_right - (Node[pos-1].l)/(Node[pos-1].l + Node[pos-1].r);
Node[i].p = -1;//递归结束后记得还原
}
}
if(ok){//当结点全部使用过的时候，结束调用（挂坠已经全部挂完）
double width_temp = 1 + width_right + width_left;//总长度 = 1 + 左长度和+右长度和
if(width_temp>width && width_temp<r)
width = width_temp;//更新width
}
}
int main(){
for(int i=0;i<s;i++){//第一个放谁?谁都应该试一次
Node[i].p = s;
treedfs(W[i], s);//注意这里W[i]并不是两个结点的重量，但它属于叶子结点，函数中对此有具体处理，不用计算其长度
Node[i].p = -1;
}
printf("%.10f\n", width);
getchar();
getchar();
return 0;
}
网友评论