Every array repeat search times: 10
Number of Elements 理论平均查找次数 实际平均查找次数
5
100 6.5 6.1 200 7.5 7.3 300 8.5 7.4 400 8.5 7.4 500 8.5 7.5 600 9.5 8.2 700 9.5 8.8 800 9 .5 8.7 900 9.5 8.8 1000 9.5 9.4
七、总结
二分查找在搜索有序表时，效率比较高。通过这次实验我对二分查找算法的认识又有了新的提高。本想写个图形界面，但由于种种原因，没有实现，下次做加密算法时，要写一个图形化界面。
6
指导教师对实验报告的评语
成绩：
指导教师签字：
年 月 日
7
实验二：分治法解决棋盘问题
一、实验时间：2013年10月22日，星期二，第一、二节地点：J13#328
二、实验目的及要求
1、 用c/c++语言实现分治法解决棋盘问题算法。 2、 实现棋盘化以及棋盘覆盖
三、实验环境
Windows 2007 操作系统 以及code blocks软件
四、实验内容
在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。
五、算法描述及实验步骤 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格 右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
六、调试过程及实验结果
8
七、总结
由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4k-1）/3，故此算法是一个在渐近意义下最优的算法。
9