数据结构与算法设计课程设计

内江师范学院

数据结构与算法设计课程设计实验报告册

编制算法设计课题组审定曾意

数学与信息科学学院

2014年9月

1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告；

2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D；

3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告；

4. 实验成绩评定分为A+、A、A-、B+、B、C、D 各等级。根据实验准备、

实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符

合

实验名称：算法设计基础实验(实验一) 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC++计算机

实验日期：年_月_日实验地点：第五教学楼北802

实验目的：

掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。

实验准备：

1. 在开始本实验之前，请复习相关实验内容；

2. 需要一台准备安装Windows XP Professional操作系统和装有VC++6.0的计算机。

实验内容：

求n至少为多大时，n个1组成的整数能被2013整除。

实验过程：

1.1算法思想

2013=61*33,6个1能够整除33,寻找满足n个1能够整除61的n即可。

1.2算法步骤

1?定义变量y储存余数，i储存1的个数，m为被除数，初始化为111111；

2?如果被除数能够除尽61,输出i;

如果被除数不能够除尽61，while继续循环，m=y*1000000+111111,i++;

3?重复2，直到找到满足条件的m为止，输出i;

1.3算法实现(C++程序代码)

#in clude

using n amespace std;

int mai n()

{

int y,m,i;

i=6;

m=111111; while(y!=0){ m=y*1000000+111111;

y=m%61;

i=i+6; }

cout<

return 0;

1.4算法分析

时间复杂度为0(n);

实验总结(由学生填写):通过该实验发现，任何问题不要盲目的使用蛮力法，一定要化蛮力为巧力，这样既可以减少程序的时间复杂度，也能得到较精确的结果。并且在以后的解决问题的过程中，一定要多分析，多思考。

实验等级评定：__________

实验名称：蛮力法实验一分式化简（实验二）_________ 指导教师：牟廉明，刘芳

实验时数： 4 实验设备：安装了VC++的计算机

实验日期：_______ 年_月_日实验地点：第五教学楼北802

实验目的：

掌握蛮力法的基本思想和方法，熟悉搜索法的软件实现。

实验准备：

1在开始本实验之前，请回顾教材的相关内容；

2.需要一台准备安装Windows XP Professional操作系统和装有数学软件的计算机。

实验内容：

设计算法，将一个给定的真分数化简为最简分数形式，例如，将6/8化简为3/4。

实验过程：

1.1算法思想

首先对于普通整数；

可以先利用欧几里得算法求出最大公约数，然后再讲分子分母用最大公约数作除，即可求出最简真分数。

1.2算法步骤

输入：约分前的两个整数分子和分母

输出：约分后的分子分母

1. r=m% n;

2. 循环直到r=0;

3. m=n;n=r;r=m% n;

4. a/n;b/n;

5. 输出b/a;

1.3算法实现（C++程序代码）

#in clude

using n amespace std;

int mai n（）

{

long int a, b, r;

cout<<"请输入真分数的分母和分子：";

cin> >a?b;

long int m=a;

long int n=b;

{

a = b;

b= r;

r = a%b;

}

a=m/b;

b=n/b;

cout<<"原分数的最简分数为:"<

}

1.4算法分析时间复杂度为o(n).

实验总结（由学生填写）：此次实验较为简单，也较为基础。但需注意的是，即使是很简单的问题，也需要注意细节，尤其是在定义长整型的时候，不要单独的只定义为整型。

实验等级评定：