tsvico的博客

好的代码像粥一样,都是用时间熬出来的

算法分析

一些简单的算法

八皇后问题

查找(哨兵)

八皇后问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 4 时问题有解。

问题解析:8*8棋盘上每行每列都有一个皇后,且任意两皇后不能处于同一行、同一列、同一斜线上

为了简化问题,下面讨论四皇后问题。回溯法从空棋盘开始,首先把皇后1摆放到它所在行的第一个位置,也就是第一行第一列,得到图8.7(a)。

对于皇后2,在经过第一列和第二列的尝试后,摆放到第二行第三列,得到图8.7(b)。

对于皇后3,摆放到第三行的哪一列都会引起冲突(即违反约束条件),进行回溯,回
到对皇后2的处理,把皇后2摆放到下一个位置,也就是第二行第四列,得到图8.7(d)。

对于皇后3,在经过第一列的尝试后,摆放到第三行第二列,得到图8.7(e)。

对于皇后4,摆放到第四行的哪一列上都会引起冲突,进行回溯,回到对皇后3的处
理;皇后3摆放到第三行的哪一列上都会引起冲突,再次进行回溯,但此时皇后2位于棋
盘的最后一列,继续回溯,回到对皇后1的处理,把皇后1摆放到第一行第一列,得到
图8.7(g)。

接下来,把皇后2摆放第二行第四列的位置,把皇后3摆放到第三行第一列的位置,把皇后4摆放到第四行第三列的位置,得到四皇后问题的一个解,如图8.7(j)所示。

image

算法

【算法】设函数Queen实现n皇后问题,皇后k摆放在k行 x[k]列的位置,算法用伪代码描述如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
算法8.3:回溯法求解n皇后问题Queen
输人:皇后的个数n
输出:n皇后问题的解x[n]
1.初始化解向量x[n]={-1};
2.k=1;
3.while(k>=1)
3.1 把皇后k摆放在下一列的位置,即x[k]++;
3.2 从x[k]开始依次考察每一列,如果皇后k摆放在x[k]位置不发生冲突,则转步骤3.3;
否则x[k]++试探下一列;
3.3 若n个皇后已全部摆放,则输出一个解,算法结束;
3.4 若尚有皇后没摆放,则k++,转步骤3摆放下一个皇后;
3.5 若x[k]出界,则回溯,x[k]=-1,k--,转步骤3重新摆放皇后k;
4.退出循环,说明n皇后问题无解;

实现

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
/***************

八皇后问题

************/
#include <iostream>
#include<stdlib.h>
using namespace std;
void Queen(int k);
const int n=8;
int x[n];
int main(){
Queen(n);
}
int Place(int k){ //考察皇后k放在 x[k]是否发生冲突
for (int i=0;i<k;i++)
{
if (x[i]==x[k] || abs(i-k)==abs(x[i]-x[k])) //abs() 求绝对值 ||违反约束条件
{
return 1; //冲突,返回1
}
}
return 0; //不冲突,返回0
}
void Queen(int n){ //求解n皇后问题
int k=0; //皇后
while (k>=0)
{
x[k]++; //在下一列排放皇后
while (x[k]<n && Place(k)==1) //发生冲突
{
x[k]++; //皇后k试探下一列
}
if (x[k]<n && k==n-1) //得到下一个解,输出
{
for(int i=0;i<n;i++){
for(int j=0;j<x[i];j++){
cout<<"□ ";
}
if(x[i]<9){
cout<<x[i]+1<<" "; //数组下标从0开始,打印的序号从1开始
}else{
cout<<x[i]+1; //数组下标从0开始,打印的序号从1开始
}

for(int j=n-1;j>x[i];j--)
{
cout<<"□ ";
}
cout<<endl;
}
cout<<endl;
return ; //只求出一个解
}
if(x[k]<n && k<n-1) //尚有皇后未摆放
k = k +1; //准备拜访下一个皇后
else
x[k--] = -1; //重置x[k],回溯,重新摆放皇后k
}
cout<<"无解"<<endl;
}

image

遍历查找(哨兵)

利用观察哨,则无需判断查找是否越界

较传统蛮力查找,设置观察哨他们的时间复杂度都是O(n),而系数相差一倍。实验表明,设置观察哨之后的算法在表长大于1000时,一次顺序查找的时间几乎一半

算法c++核心代码

1
2
3
4
5
6
7
8
int SeqSearch2(int r[],int n,int k) //数组r[1]~r[n]存放查找集合
{
int i=n; //从数组最高端开始查找
r[0] = k; //设置哨兵
while(r[i] != k)
i--;
return i;
}

以后想起来什么再写,先到这,继续写python

坚持原创技术分享,您的支持将鼓励我继续创作!