[复健计划][紫书]Chapter 7 暴力求解法

7.1 简单枚举

例7-1 Division uva725
输入正整数n，按从小到大的顺序输出所有形如abcde/fghij = n的表达式，其中a～j恰好为数字0～9的一个排列（可以有前导0），2≤n≤79。

枚举fghij，验证abcde是否有重复数字

例7-2 Maximum Product uva11059
输入n个元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数，应输出0（表示无解）。1≤n≤18，-10≤Si≤10。

枚举起点和终点

例7-3 Fractions Again?! uva10976
输入正整数k，找到所有的正整数x≥y，使得1/k=1/x+1/y。

在[1,2k]范围内枚举y

7.2 枚举排列

7.2.1 生成1~n的排列

递归

7.2.2 生成可重集的排列

递归

7.2.3 解答树

如果某问题的解可以由多个步骤得到，而每个步骤都有若干种选择（这些候选方案集可能会依赖于先前作出的选择），且可以用递归枚举法实现，则它的工作方式可以用解答树来描述。

7.2.4 下一个排列

7.3 子集生成

7.3.1 增量构造法

规定集合A中所有元素的编号从小到大排列，一次选出一个元素放到集合中

void get_subset(int n,int *A,int siz){for(int i=1;i<=siz;i++) printf("%d ",A[i]);printf("\n");int minn=siz?A[siz]+1:1;for(int i=minn;i<=n;i++){A[siz+1]=i;get_subset(n,A,siz+1);}
} 

解答树中，每个子集对应一个结点，一共有$2^n$个结点

7.3.2 位向量法

构造一个位向量B[i]，而不是直接构造子集A本身，其中B[i]=1，当且仅当i在子集A中

void get_subset(int n,int *B,int p){if(p>n){for(int i=1;i<=n;i++)if(B[i]) printf("%d ",i);printf("\n");return;}B[p]=0;get_subset(n,B,p+1);B[p]=1;get_subset(n,B,p+1);
} 

解答树上有$1+2+4+...+2^n=2^{n+1}-1$个结点，所有部分解（不完整的解）也对应着解答树上的结点，最后几层结点数占整棵树的绝大多数。

7.3.3 二进制法

以用二进制来表示{0, 1, 2,…,n-1}的子集S：从右往左第i位（各位从0开始编号）表示元素i是否在集合S中。
当用二进制表示子集时，位运算中的按位与、或、异或对应集合的交、并和对称差。

void print_set(int n,int s){for(int i=0;i<n;i++)if(s&(1<<i)) print("%d ",i);printf("\n");
}
for(int s=0;s<(1<<n);s++) //枚举子集 print_subset(n,s);