《算法设计与分析》实验指导书
计算机学院信息安全系
毕方?/p>
本书是为配合
《算法分析与设计实验教学大纲?/p>
而编写的上机指导?/p>
其目的是使学生消
化理论知识,
加深对讲授内容的理解?/p>
尤其是一些算法的实现及其应用?/p>
培养学生独立编程
和调试程序的能力,使学生对算法的分析与设计有更深刻的认识?/p>
上机实验一般应包括以下几个步骤?/p>
?/p>
1
?/p>
、准备好上机所需的程序。手编程序应书写整齐,并经人工检查无误后才能上机?/p>
?/p>
2
?/p>
、上机输入和调试自己所编的程序。一人一组,独立上机调试,上机时出现的问题,最
好独立解决?/p>
?/p>
3
?/p>
、上机结束后,整理出实验报告。实验报告应包括:题目、程序清单、运行结果、对?/p>
行情况所作的分析?/p>
本书共分阶段
4
个实验,
每个实验有基本题和提高题。基本题必须完成,提高题根据自己
实际情况进行取舍。题目不限定如下题目,可根据自己兴趣爱好做一些与实验内容相关?/p>
其他题目,如动态规划法中的图象压缩,回溯法中的人机对弈等?/p>
其具体要求和步骤如下?/p>
实验一
分治与递归?/p>
4
学时?/p>
基本题一:基本递归算法
一、实验目的与要求
1
?/p>
熟悉
C/C++
语言的集成开发环境;
2
?/p>
通过本实验加深对递归过程的理?/p>
二?/p>
实验内容?/p>
掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法?/p>
三、实验题
任意输入一个整数,输出结果能够用递归方法实现整数的划分?/p>
四、实验步?/p>
1
?/p>
理解算法思想和问题要求;
2
?/p>
编程实现题目要求?/p>
3
?/p>
上机输入和调试自己所编的程序?/p>
4
?/p>
验证分析实验结果?/p>
5
?/p>
整理出实验报告?/p>
基本题二:棋盘覆盖问?/p>
一、实验目的与要求
1
、掌握棋盘覆盖问题的算法?/p>
2
、初步掌握分治算?/p>
二、实验题?/p>
盘覆盖问题:在一?/p>
2
k
×
2
k
个方格组成的棋盘中,恰有一个方格与其它方格不同,称?/p>
方格为一特殊方格?/p>
且称该棋盘为一特殊棋盘?/p>
在棋盘覆盖问题中?/p>
要用图示?/p>
4
种不同形