菜鸟天堂

     摘要: 本文是《数据结构与程序设计（c++语言描述）》中关于二分搜索的学习笔记，二分搜索的思想很简单，但是要实现一个正确最优的算法确不是那么容易。第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现，所以，认真点＋留神点～ ^_^

首先，介绍一下二分搜索的思想：对于一个有序表而言，要查找某个关键字，首先比较表中央的那个节点，如果该节点的关键字与目标关键字相同，则找到。若比目标小，则目标关键字肯定出现在该点的右半段内。反之则出现在左半段。这样，每次比较后就能丢去一半的节点，对于一般的有序线性表而言，其搜索效率大大高于顺序查找。

第一个版本的二分搜索：
根据算法，我们设置三个位置指示器：low, high, mid，分别指向当前搜索范围的最低位置、最高位置和中间位置，中间位置由mid = (low+high)/2决定。首先将mid处的关键字与key比较，相同则返回mid；若key较大，令low＝mid＋1继续搜索右半段；若key较小，令high＝mid－1继续搜索左半段。这样，搜索范围不断减小，high－low也越来  阅读全文

     摘要: 实现一个最简单的顺序查找算法，如下所示：
template
int sequential_search( Record *r, const int & size, const Key & k )
{
for(int i=0; i if( r[i] == k )
return i;
return -1;
}
有几点需要注意的：
1）如果在数组的最低或最高单元加上一个哨兵元素（sentinel），则可以在每次迭代中少一个判断（i2）在仅考虑搜索成功以及等概率搜索的前提下，顺序查找的的关键字比较次数为n*(n+1)/2。
3）常见搜索算法的时间复杂度是以关键字比较的次数来进行度量的。
4）与二分搜索不同，顺序搜索可以针对无序表进行。
5）顺序查找的搜索树是一颗单链树，有n＋1个叶子节点，其中n个成功节点，1个失败节点。
  阅读全文

     摘要: n皇后问题的时间代价除了递归和回溯需要的外，在每一步判断加入的皇后是否与当前棋盘格局冲突也需要不少时间，guarded函数需要扫描所在列以及两条对角线。然而我们可以通过改进数据结构来使后者的时间代价降低为O(1)。

对于n皇后问题来说，每一行每一列每条对角线上最多有一个皇后，那么对于这样的每个元素（行、列或对角线）我们可以用一个bool值来表示是否已经有皇后在该元素上，这样判断是否冲突就变得十分简单，只需要读取一个bool值。另外需要记录棋盘的格局，考虑到一行只有一个皇后，可以建议一个一维数组保存每一行的皇后占用的列号。

这样基本就OK了，只是对于行而言，我们采用了回溯法（剪枝函数）保证了每行只有一个皇后，这样行的bool数组就可以省略了。

  阅读全文

     摘要: n皇后问题是递归和回溯法的一个典型应用。问题描述如下：对于一个n×n的棋盘，要求在其中放入互不攻击的n个皇后。皇后的攻击范围包括：
1) 同一行
2) 同一列
3) 同一对角线（包括两个方向）

分析后可见，皇后之间互不攻击当且仅当满足下列条件：
1) 每一行只能有一个皇后
2) 每一列只能有一个皇后
3) 任意条对角线上面只能有一个皇后

若按照从左到右从上到下的顺序手动摆放皇后，会发现算法遵循的是回溯法的思想。于是我们遵循top-down design的顺序来设计整个算法和程序。

  阅读全文

     摘要: 本文从递归函数参数的角度来分析，递归函数调用时递归工作栈中工作记录减肥的可能性。

用最简单的求阶层函数来举例：
n! = n*(n-1)*(n-2)***2*1

常见的递归实现如下：
int fun(int n)
{
if( n<=1 ) return 1;
return n*fun(n-1);
}
不用多说，这个实现下每次递归调用都会在当前层的工作记录中分配一个4字节（IBM兼容机）的空间来存放n的值。若栈的深度为DEPTH，那么一共需要DEPTH×4个字节存放参数。

  阅读全文