素数环问题

输入一个整数n，输出所有由1~n排成的环，满足任意两个相邻数之和都是素数。
样例输入：
6 样例输出：
1 4 3 2 5 6
1 6 5 2 3 4
（注：输出都以1开头，其他循环的不用输出，如4 3 2 5 6 1）

思路：

1
2
3
4
5
6
7
8
9
10
11
输入n
状态选择：以环的前i个数为状态
void solve(int a[], int i) {
    if(i == n) {
        判断a是否符合素数环条件，符合就输出
    }
    for(a[i] = 1, i <= n; a[i]++) {
        solve(a, i + 1)
    }
}
调用solve(0)

solve和search是竞赛中最常出现的函数名称，意为用暴力方法解决问题。

题目的代码为：primering.cpp

本题目在判断某个数是否是素数时，存在重复的判断，可以进行优化，预先把1 ~ 2n-1的数是否是素数存到一个表中，在使用的时候，不需要再计算，直接查询即可。代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cmath>
#include <vector>
#include <ctime>

using namespace std;

vector<int> table;

int isPrime(int n) {    // 判断质数
    if (n==1 || n==2 || (n>2 && n%2==0)){
        return 0;
    }
    for (int i=3;i<=sqrt(n);i+=2){
        if (n%i==0){
            return 0;
        }
    }
    return 1;
}


// 回溯法遍历
void search(int data[],int n,int i) {
    /*
    cout<<"Seaching: "<<data[1]; // 日志
    for (int j=2;j<=i;j++){
        cout<<" "<<data[j];
    }
    cout<<endl;
     */
    
    if (i==n){    // 递归边界，n个数都确定了位置
        if (table[data[n]+data[1]]) {
            for (int j=1;j<=n;j++){  // 最后判断首尾和是不是素数，是的话就找到一个解
                cout<<data[j]<<" ";
            }
            cout<<endl;
        }
        return;
    }
    
    int tmp=data[i];
    for (int j=i;j<=n;j++){  // 枚举尚未确定的数字
        if (table[data[j]+data[i-1]]){ // 剪枝
            data[i]=data[j];    // 交换i,j位的数字
            data[j]=tmp;
            search(data,n,i+1);   // 递归搜索下一个数
            data[j]=data[i];    // 恢复第j位的数字
        }
    }
    data[i]=tmp;    // 恢复第i位的数字
}


int main(){
    int n;
    cin>>n;
    if (n%2==1) {   // 预判，也是一种优化
        cout<<"Impossible!"<<endl;
        return 0;
    }
    clock_t start, end;
    start = clock();
    table.reserve(2 * n);
    for(int i = 1; i < 2 * n; i++) {
        table[i] = isPrime(i);
    }
    int data[n+1];
    for (int j=1;j<=n;j++) {    // 初始化排列
        data[j]=j;
    }
    search(data,n,2);   // 为什么从2开始？因为循环对称性，第1位固定为1}
    end = clock();
    // 用来统计算法的执行时间
    cout << (end - start) / CLOCKS_PER_SEC << " s" << endl;
    return 0;
}

再谈小球下落问题

$2^D-1$个开关排列成深度为D的二叉树，最初都为关闭状态。有n个小球从顶端依次落下，并遵循如下规则：

如果经过一个关闭的开关，则开关打开，小球落向左侧；
如果经过一个打开的开关，则开关关闭，小球落向右侧；
输入D，n，输出最后一个小球最终落到的位置。
样例输入:
4 3
样例输出：
10

原来的方法是模拟小球下落的过程，具体代码见 初探二叉树的应用 一文。

  原模拟算法的时间复杂度很高。注意到有这样的规律，节点k左右子节点编号分别为2k和2k+1，每个小球都会落在根结点上，因此前两个小球必然是一个在左子树，一个在右子树。一般地，只需看小球编号的奇偶性，就能知道它是最终在哪棵子树中。对于那些落入根结点左子树的小球来说，只需知道该小球是第几个落在根的左子树里的，就可以知道它下一步往左还是往右了。依此类推，直到小球落到叶子上。
  对于编号为id的小球，如果id为奇数，它是往左走的第(id+1)/2个小球，如果id为偶数，它是往右走的第id/2个小球。这样就可以直接模拟出最后一个小球的路线：

1
2
3
4
5
6
7
8
9
10
int k = 1;
for(int i = 0; i < D - 1; i++) {
    if(n % 2) {
        k = k * 2;
        n = (n + １) / 2;
    } else {
        k = k * 2 + 1;
        n /= 2;
    }
}

八皇后问题

  This one is a classic in computer science. The goal is to assign eight queens to eight positions on an 8x8 chessboard so that no queen, according to the rules of normal chess play, can attack any other queen on the board.
In pseudocode, our strategy will be:

1
2
3
4
5
6
7
8
Start in the leftmost columm
If all queens are placed, return true
for (every possible choice among the rows in this column)
    if the queen can be placed safely there,
        make that choice and then recursively try to place the rest of the queens
        if recursion successful, return true
        if !successful, remove queen and try another row in this column
if all rows have been tried and nothing worked, return false to trigger backtracking

八皇后问题棋盘状态树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

const int NUM_QUEENS = 8;
template <typename T>
class Grid {
private:
    T v[NUM_QUEENS][NUM_QUEENS] = { {0} };
public:
    /*
     * 皇后是按列进行放置的，每列只有一个皇后，本函数是检查前col-1个皇后和现在放置在
     * (col, row) 上的皇后是否冲突
     */
    bool isSafe(int col, int row) {
        for (int i = 0; i < NUM_QUEENS; ++i) {
            for (int j = 0; j < col; ++j) {
                if (v[i][j] == 1) {
                    if ( i == row || abs(i - row) == abs(j - col) )
                        return false;
                }
            }
        }
        return true;
    }
    bool solve(int col) {
        // 进入该函数时，前col-1个皇后已经正确的放置在了棋盘上
        if (col >= NUM_QUEENS) {
            print();
            return true;
        }
        for (int rowToTry = 0; rowToTry < NUM_QUEENS; rowToTry++) {
            v[rowToTry][col] = 1;
            if (isSafe(col, rowToTry)) {
                solve(col + 1);     // recur to place rest
            }
            v[rowToTry][col] = 0;   // failed, remove, try again
        }
        return false;
    }
    void print() {
        static int count = 1;
        cout << "Case " << count++ << endl;
        for (int i = 0; i < NUM_QUEENS; i++) {
            for (int j = 0; j < NUM_QUEENS; j++) {
                v[i][j] == 1 ? printf("%c ", 2) : printf(". ");
            }
            cout << endl;
        }
        cout << endl;
    }

    void printSimply() {
        for (int i = 0; i < NUM_QUEENS; i++) {
            for (int j = 0; j < NUM_QUEENS; j++) {
                if(v[i][j] == 1)
                    cout << j + 1 << " ";
            }
        }
        cout << endl;
    }
};

int main() {
    Grid<bool> board;
    board.solve(0);
    return 0;
}

该算法可进行空间上的优化，初始化一个一维数组matrix[9]，对应的是棋盘中的8行，数组中元素的值代表放置皇后的列，比如如果matrix[i]的值不为0，就表示棋盘第i行，第matrix[i]列放置了一个皇后。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;

#define N 8

int matrix[N + 1] = {0};

bool isSafe(const int &row, const int &col) {
	for (int i = 1; i <= row - 1; ++i) {
		int j = matrix[i];
		if (  j == col || abs(i - row) == abs(j - col) )
			return false;
	}
	return true;
}

void print(void) {
	for (int i = 1; i <= N; i++) {
        cout << matrix[i] << " ";
	}
	cout << endl;
}

void solve(const int &row) {
	//	进入本函数时，在N*N的棋盘前row-1行已放置了互不攻击的row-1个棋子
	//	现从第row行起继续为后续棋子选择合适位置

	if (row > N)	//	输出当前的合法布局
		print();
	else {
		for (int j = 1; j <= N; ++j) {
			matrix[row] = j;
			if (isSafe(row, j))
				solve(row + 1);
			matrix[row] = 0;
		}
	}
}

int main(void) {
	solve(1);
	return 0;
}