排列，组合，回溯法
ex.1
/*
* 打印出一个字符串的全部排列。
*/
void permutation(char * str, char *pBegin) {
if(*pBegin == '\0') {
printf("%s,",str);
} else {
for(char *pCh = pBegin;pCh != '\0';++pCh){
swap(pCh,pBegin);
permutation(str,pBegin+1);
swap(pCh,pBegin);
}
}
}
ex.2
/*
* 打印出一个字符串的组合。
*/
排列
- 全排列：从第一个数字起，每个数字分别与它后面的数字交换
- 去重全排列：从第一个数字起，每个数组分别与它后面非重复出现的数字交换
组合
- 基于递归
- 基于位图
ex.3
/*
* 输入一个含有8个数字的数组，判断有没有可能把这8个数字分配放到正方体
* 的8个顶点上，是得正方体上三组相对的面上的4个顶点的和都相等
*/
//求8个数字的全部排列，然后判断排列是否满足题目给出的条件
ex.4
/*
* 8皇后问题。在8*8的棋盘上拜放8个皇后，使其不能相互攻击，即8个皇后
* 不能处于同一行，同一列或者同一对角线上。
*/
//初始化一个columnIndex[8]数组，第i个数表示位于第i行的列数，因此用0-7来
//初始化数组，然后做全排列，逐个判断是否满足不同行、列、对角线的要求
//初始化一个columnIndex[8]数组，第i个数表示位于第i行的列数
// 使用回溯法，从第一行第一列初始化数组
回溯法
//8皇后
int C[8] = {0};
cout << search(0) << endl；
int tot = 0;
void search(int cur) {
if(cur == 8) tot++;
else for (int i = 0; i < 8;++i) {
int ok = 1;
C[cur] = i;
for(int j = 0; j< cur; ++j) {
if(C[cur]==C[j] || cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]){
of = 0; break;
}
}
if(ok) search(cur+1);
}
}
//矩阵中的路径
//从任意格子出发，检查是否满足路径，同数组表示访问的路径表示已经到达过的位置以及当前到达的位置
//先检查当前格子，是否满足条件，满足则向另外4个方向出发，不满足则返回
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
return false;
bool *visited= new bool[rows * cols];
memset(visited, 0, rows*cols*sizeof(bool));
int pathLength = 0;
for(int row = 0;row < rows;++row) {
for(int col = 0;col < cols;++col) {
if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited)) {
delete [] visited;
return true;
}
}
}
delete [] visited;
return false;
}
bool hasPathCore(char* matrix, int rows, int cols,int row,int col,
char* str,int& pathLength,bool* visited){
if(str[pathLength] == '\0')
return true;
bool hasPath = false;
if(row >= 0 && row < rows && col >=0 && col < cols
&& matrix[row * cols + col] == str[pathLength] && !visited[row * cols + col]) {
++pathLength;
visited[row * cols + col] = true;
hasPath = hasPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited)
|| hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited)
|| hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited)
|| hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited);
if(!hasPath) {
--pathLength;
visited[row * cols + col] = false;
}
}
return hasPath;
}
// 机器人的运行范围
// 使用一个数组来记录已访问的位置，
// 从(0，0)出发， 每次移动位置都要检查是否满足要求。
// 如果满足要求则设置记录数组，并且增加路程
int movingCount(int threshold, int rows, int cols)
{
if(threshold <= 0 || rows <= 0 || cols <= 0)
return 0;
bool *visited = new bool[rows * cols];
for(int i = 0; i < rows * cols; ++i)
visited[i] = false;
int count = movingCountCore(threshold,rows,cols,0,0,visited);
delete [] visited;
return count;
}
int movingCountCore(int threshold, int rows, int cols,int row,int col,bool *visited){
int pathLength = 0;
if(row >=0 && row < rows && col >= 0 && col < cols
&& !visited[row * cols + col] && checkOk(threshold, row, col)) {
visited[row * cols + col] = true;
pathLength = 1 + movingCountCore(threshold,rows,cols,row,col+1,visited)
+ movingCountCore(threshold,rows,cols,row+1,col,visited)
+ movingCountCore(threshold,rows,cols,row-1,col,visited)
+ movingCountCore(threshold,rows,cols,row,col-1,visited);
}
return pathLength;
}
bool checkOk(int threshold, int row, int col)
{
int tmp = 0;
while(row > 0){
tmp += row % 10;
row = row / 10;
}
while(col > 0){
tmp += col % 10;
col = col / 10;
}
if(tmp <= threshold)
return true;
return false;
}
CH0DUHF}M)@4486{PU4(WCH.png
//从最左列开始，按照规定从上，下，右三个方向出发，把所有路径找到找到最小跳数
//设置一个数组用来记录路径标注已经过的格子放置重复，
// 判断当前位置是否正确，以及是否能到达右边
网友评论