08 2006 档案

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

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

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

posted @ 2006-08-30 23:24 樱木 阅读(2256) | 评论 (1)  编辑 |

     摘要: 实现一个最简单的顺序查找算法,如下所示:
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个失败节点。
  阅读全文

posted @ 2006-08-30 16:03 樱木 阅读(206) | 评论 (0)  编辑 |

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

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

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

  阅读全文

posted @ 2006-08-28 18:45 樱木 阅读(280) | 评论 (0)  编辑 |

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

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

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

  阅读全文

posted @ 2006-08-28 18:44 樱木 阅读(420) | 评论 (0)  编辑 |

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

用最简单的求阶层函数来举例:
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个字节存放参数。

  阅读全文

posted @ 2006-08-28 18:41 樱木 阅读(1266) | 评论 (1)  编辑 |