《算法设计与分析》实验报告册

1、内江师范学晓算法设计与分析实验报告册编制算法设计课题组 审定曾意专业：信息与计算科学班级：级班学号：姓名：数学与信息科学学院2016年9月1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理 论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要 求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本 次实验，不得书写实验报告；2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过 程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师 提问等；若学生无故旷课，则本次实验等级计为d；3. 学生要认真工整地书写实验报告，实验

2、报告的内容要紧扣实验的要求和 目的，不得抄袭他人的实验报告；4实验成绩评定分为a+、a、a、b+、b、c、d各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如 下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合。实验名称：算法设计基础实验(实验一)指导教师： 牟廉明实验时数：4实验设备：安装了 vc+计算机实验日期： 2016 年9月2213实验地点：第三实验楼119实验室实验目的：掌握算法设计的基本原理，熟悉算法设计的基本步骤及具软件实现。实验准备：1. 在开始本实验之前，请复习相关实验内容；2. 需要一台准备安装windows

3、 xp professional操作系统和装有vc+6.0的计算机。实验内容：求n至少为多大时，n个1组成的整数能被2013整除。实验过程：1.1算法思想规律：两个相邻由1组成的数，第二个数是第一个数的十倍加上1；根据这个规律，由1开始，判断 是否能被2013整除，下一个数由1乘以10再加上1得到，设置一个计数器i,最后得到能够被2013整除 的由i个1组成的数。1.2算法步骤输入:i=l,临时变量temp=l输出：计数器i的大小1 由1开始判断是否能被2013整除2由1乘以10加上1得到下一个判断是否能被2013整出的数3计数器i由1变为24当临时变量temp能被2013整除时，返回i的大小

4、13算法实现(c+程序代码)#include<iostream>using namespace std;int main()int i=14emp=l;while(temp!=0)temp=temp * 10+1;temp=temp % 2013;i=i+l;cout«i«endl; return 0;1.4算法分析本算法的根本是找到了两个由1组成的数之间的规律，并根据此规律进行迭代判断，知道找出满足条件的 数，并返回计数器i的大小，比刚开始计划返回能整除2013的这个数本身更加合理。实验总结（由学生填写）：实验等级评定：实验名称：蛮力法实验一分式化简（实验二）

5、指导教师:牟廉明实验时数：4实验设备：安装了 vc+的计算机实验日期： 2016 年10月12日实验地点：第三实验楼119实验室实验目的：掌握蛮力法的基木思想和方法，熟悉搜索法的软件实现。实验准备：1. 在开始本实验z前，请回顾教材的相关内容；2. 需要一台准备安装windows xp professional操作系统和装有数学软件的计算机。实验内容：设计算法，将一个给定的真分数化简为最简分数形式，例如，将6/8化简为3/4 o实验过程：1.1算法思想先找出分子和分母的最大公约数，然后分子分母同时除以最大公约数，最后返回已除以最大公约数的分式。1.2算法步骤输入：未化简的分式输出：已化简的分式

6、1 编写求最大公约数函数max y；2分子存入n,分母存入m；3分子分母同时除以最大公约数将结果存入c, d；4输岀已化简的分式c/d；13算法实现(c+程序代码)#include <iostream>using namespace std;int maxy(int a,int b)int min, max;max=a>b?a:b;min=a<b?a:b;if(max%min=o)return min;elseretum maxy(min,max%min);int main()int x,mm,c,d;cout«m请输入分子"«endl;c

7、in> >n;cout«"请输入分母"«endl;cin»m;x=maxy(n,m);c=n/x;d=m/x;cout<<c«,7m«d«endl;return 0;1.4算法分析算法利用化简分式的核心思想：找出分子分母的最大公约数。利用最大公约数化简分式可以一步达到 目的，算法思想简单，程序结构清晰。实验等级评定：实验名称：分治法实验一循环移位（实验三）指导教师： 牟廉明实验时数：4实验设备：安装了 vc+的计算机实验日期： 2016 年 11 h 2 r实验地点：第三实验楼119实验室实

8、验目的：通过本次实验，讣学住学握分治法的基本思想和技巧，并学会如何用c+软件來实现.实验准备：1. 在开始本实验z前，请回顾教科卩的相关内容；2. 需要一台准备安装windows xp professional操作系统和装冇c+软件的计算机。实验内容：设计分治算法，实现将数组an中所有元素循环左移k个位置，要求时间 复杂度为o （n）,空间复杂度为o （do例如，对abcdefgh循环左移3位得到 defghabc。实验过程：1.1算法思想将数组元素左移n块，则将数组分成几块，然后将每一块进行编号，然后进行移动，序号相同的，前一段序号的那个数移到后-段序号的那个数即可。1.2算法步骤1. 实现

9、相邻两端相同编号的数进行移动2. 使用k个函数调用实现每个序号的数都进行移动3 输出数组1.3算法实现(c+程序代码)#include<iostream>#include<string>h> using namespace std;int main()chara100;int k;cout«m请输入数组:m«endl;cin»a;cout«'*请输入左移的位数k： n«endl;cin»k;converse(a,strlen(a),k);return 0;void reverse(char *a,

10、 int from, int to)for(int i=0;i<(to-from+l)/2;i+) char temp=afrom+i;a from+i=a to-i;ato-i=temp;void converse(char *a,int n,int k)reverse(a, 0, k-1);reverse(a, k, n-1);reverse(a, 0, n-1);cout«h移动后的数组为："vvendl;for(int i=0;i<n;i+)cout«ai;cout«endl;1.4算法分析 本算法将数组元素的移动采用分治法的思想将数

11、组分为两个部分，然后将前k位数的那个部分又划分为几 个部分进行移动，最终得到移动k位数之后的数组。实验总结（由学生填写）：实验等级评定：实验名称：回溯法一0/1背包问题(实验四)指导教师： 牟廉明实验时数：4实验设备：安装了 vc+的计算机实验日期： 2016 年11月16 口实验地点：第三实验楼119实验室实验目的：熟悉回溯法的基本思想和实现方法，掌握如何用c+实现相关算法。实验准备：1. 在开始本实验之前，请i叫顾教科书的相关内容；2. 需要一台准备安装windows xp professional操作系统和装有c+的计算机。实验内容：给定背包容量w=20,以及6个物品，重量分别为(5,

12、3, 2, 10, 4, 2), 价值分别为(11, 8, 15, 18, 12, 6)。请用回溯法求解上述0/1背包问题。 实验过程：1.1算法思想对6个物品进行0/1选择，0表示不放入，1表示放入，一共有26种可能，是一个完全二叉树。根据不超 过背包总容量的原则，深度优先原则先求出一个可行解，再根据不超过已有可行解大小的原则进行剪枝， 最后从所有可行解中找出最优解。1.2算法步骤输入：物品个数n,背包容量c,每个物品重量刚i,每个物品价值用。输出：总价值最大的选取方案的物品编号，选取物品总重量，选取物品总价值。1选取物品函数if当前已选取物品重量tv加上下一个物品重量wi不超过总容量c,则

13、当前总重量变为tw=tw+wi;当前总价值变为tv=tv+vi;将第i个物品是否选取的状态存入opi；在i=6时跳岀循环，使最大总重量maxw=tw;s大总价值maxv=tv;2回溯到上一步对第i个物品的选择，选取状态为与opi相反的状态，算出当前总重量tlwj,当前总价值 tv; if tv>maxv,则 maxv=tv,maxw=tw;§则不做改变。3继续回溯到对第il个物品的选择4搜索出所有可行解，将其中总价值最大的解输出。5输出最优解的选取方案，最优解的总重量，最优解的总价值。13算法实现(c+程序代码)#include <iostream>using na

14、mespace std;#define maxn 20int maxv;int maxw;考虑第个物品intxmaxn;void knap(int w,int v,int c,int n,int i,int tw,int tv,int op) int j；if(i>n)if(tw<=c && tv>maxv)maxv=tv;maxw=tw;for(j=l;j<=n;j+) xj=opj;elseif(tvv+wi<c)opi=l； knap(w,v,c,n,i+l,tw+wi,tv+vi,op);opi=0;knap(w,v,c,n,i+l,tw,tv,op);void disp(int x,int n)输入算出得答案int i;cout«h背包最佳方案是："vvcndl;for(i=l;i<=n;i+)if(xij=l)cout«m选取第k«i«h个物品h«endl;cout«h总重量为："vvmaxw; cout«h总价值：k«maxv;int main()int n=6;int c=20;int