常熟理工学院
《算法分析与设计》实验指导与报告书__________学年第____学期
专业：___________________________________
学号：___________________________________
姓名：___________________________________
实验地点：___________________________________ 指导教师：_______ _ ____刘在德 _________
计算机科学与工程学院
2014.08.31
目录
实验一、求最大公约数 (1)
一、实验目的 (1)
二、预习内容 (1)
三、实验内容 (1)
四、实验步骤 (1)
五、运行结果 (3)
实验二、斐波那契数列 (6)
一、实验目的 (6)
二、预习内容 (6)
三、实验内容 (6)
四、实验步骤 (6)
五、运行结果 (8)
实验三、霍纳法则和二进制幂 (11)
一、实验目的 (11)
二、预习内容 (11)
三、实验内容 (11)
四、实验步骤 (11)
五、运行结果 (13)
实验四、求解非线性方程 (15)
一、实验目的 (15)
二、预习内容 (15)
三、实验内容 (15)
1
四、实验步骤 (15)
五、运行结果 (18)
实验五、字符串匹配问题 (19)
一、实验目的 (19)
二、预习内容 (19)
三、实验内容 (19)
四、实验步骤 (19)
五、运行结果 (21)
实验六、Warshall算法和Floyd算法 (22)
一、实验目的 (22)
二、预习内容 (22)
三、实验内容 (22)
四、实验步骤 (22)
五、运行结果 (25)
2
实验一、求最大公约数
一、实验目的
（1）求两个自然数m和n的GCD (Greatest Common Divisor)；
（2）掌握并应用算法的数学分析和后验分析方法；
（3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。
二、预习内容
P2 1.1 什么是算法
三、实验内容
（1）设计出3个版本的求最大公约数的算法；
（2）采用C实现算法，利用计数法记录基本语句的执行次数；
（3）分析3种算法的时间复杂性；通过分析对比，得出结论。
四、实验步骤
方法一：欧几里得法
#include
#include
int main()
{
int m,n,k,temp,count=0;
printf("请输入两个整数：");
scanf("%d %d",&m,&n);
if(m { temp=m; m=n; n=temp; } while(n!=0) 1 { k=m%n; m=n; n=k; count=count+1; } printf("最大公约数是：%d\n",m); printf("执行次数是：%d\n",count); return 0; } 方法二：连续检测法 #include int main(){ int m,n,i,temp,count=0; printf("请输入两个数："); scanf("%d %d",&m,&n); if(m==0||n==0){ printf("输入的数字非法！"); } else{ if(m temp=m; m=n; n=temp; } for(i=n;i>0;i--){ count=count+1; if(m%i==0&&n%i==0){ printf("最大公约数是：%d\n",i); printf("执行次数是：%d",count); break; } } } return 0; } 方法三：循环相减 #include 2 int main(){ int m,n,count=0; printf("请输入两个整数：\n"); scanf("%d %d",&m,&n); if(m==0||n==0){ printf("输入的数字非法！"); } else{ while(m!=n){ if(m>n){ m=m-n; } else{ n=n-m; } count=count+1; } printf("最大公约数是：%d\n",m); printf("执行次数是：%d\n",count); } return 0; } 五、运行结果 欧几里得算法运行结果： 3 连续整数检测运行结果： 4 循环相减法运行结果： 5 实验二、斐波那契数列一、实验目的 （1）求斐波那契数列； （2）区分递归和递推思想。 二、预习内容 P60 2.5 例题：斐波那契数列 三、实验内容 （1）设计出3个版本的求斐波那契数列的算法； （2）采用C实现算法； （3）分析3种算法的时间复杂性；通过分析对比，得出结论。 四、实验步骤 方法一：递归算法 #include #include int main() { int n; while(scanf("%d",&n)==1){ printf("%d \n",fib1(n)); } return 0; } int fib1(int x){ if(x==0||x==1) return x; else{ return fib(x-1)+fib(x-2); } } 6 方法二：迭代算法 #include #include int main() { int n; while(scanf("%d",&n)==1){ printf("%d \n",fib2(n)); } return 0; } int fib2(int x){ int a=0,b=1; if(x==0) return 0; if(x==1) return 1; int i=0; int temp; for(i=2;i<=x;i++){ temp=a+b; a=b; b=temp; } return temp; } 方法三：矩阵 #include #include int main() { int n; while(scanf("%d",&n)==1){ printf("%d \n",fib3(n)); } return 0; } int fib3(int x){ int data[2][2]={0,1,1,1}; 7 int f1=data[0][0],f2=data[0][1],f3=data[1][1]; if(x==0) return 0; while(x>1){ f1=data[0][0]*0+data[0][1]*1; f2=data[0][0]*1+data[0][1]*1; f3=data[1][0]*1+data[1][0]*1; data[0][0]=f1; data[0][1]=f2; data[1][0]=f2; data[1][1]=f3; x--; } return f2; } 五、运行结果 递归算法运行结果： 8 迭代算法运行结果： 矩阵算法运行结果： 9 10 实验三、霍纳法则和二进制幂一、实验目的 （1）实现计算多项式的霍纳法则； （2）实现从左至右和从右至左二进制幂算法； （3）理解变治法的思想。 二、预习内容 P176 6.5 霍纳法则和二进制幂 三、实验内容 （1）采用C实现计算多项式的霍纳法则； （2）采用C实现计算an的从左至右和从右至左二进制幂算法；（3）分析霍纳法则的时间复杂度，并与蛮力法比较，得出结论。 四、实验步骤 霍纳法则 #include int horner(int* P, int x,int n); int main() { int P[] = {-5,1,3,-1,2}; int n = sizeof(P) / sizeof(int); printf("the result is %d",horner(P, 3,n)); getchar(); return 0; } int horner(int* P, int x,int n) { int result = *(P + n - 1),i; for (i = n - 1; i >= 1; i--) { 11 result = x*result + *(P + i - 1); } return result; } 从左至右二进制幂： #include int RightLeftBinaryExponentiation(int a, int b[],int n); int main() { int a = 2; int b[] = {1,0,1,1}; int n = sizeof(b) / sizeof(int); printf("the result is %d", RightLeftBinaryExponentiation(a, b,n)); system("pause"); } int RightLeftBinaryExponentiation(int a, int b[],int n) { int term,product,i; term = a; if (b[0] == 1) product = a; else product = 1; for (i = 1; i < n;i++) { term *= term; if (b[i] == 1) { product *= term; } } return product; } 从右至左二进制幂： 12 #include int RightLeftBinaryExponentiation(int a, int b[],int n); int main() { int a = 2; int b[] = {1,0,1,1}; int n = sizeof(b) / sizeof(int); printf("the result is %d", RightLeftBinaryExponentiation(a, b,n)); system("pause"); } int RightLeftBinaryExponentiation(int a, int b[],int n) { int term,product,i; term = a; //n = 4; if (b[0] == 1) product = a; else product = 1; for (i = 1; i < n;i++) { term *= term; if (b[i] == 1) { product *= term; } } return product; } 五、运行结果 霍纳法则计算P177例一结果： 13 从左至右计算213的结果： 从右至左计算213的结果： 14 实验四、求解非线性方程一、实验目的 （1）采用平分法、试位法和牛顿法求解非线性方程； （2）理解近似算法求解某些问题的思路。 二、预习内容 P342 12.4 解非线性方程的算法 三、实验内容 （1）采用C实现求方程近似解的平分法、试位法和牛顿法；（2）分析三种算法的时间复杂度，比较三种算法的优缺点。 四、实验步骤 平分法、试位法和牛顿法计算书P345例一： #include #include double quest(double x); double fun(double a, double b, double esp, int N); double fun2(double a, double b, double esp, int N); double fun3(double x, double esp, int N); int main() { double a, b, esp; int N; a = 0; b = 2; esp = 0.01; N = 10; printf("平分法的结果为%lf\n", fun(a, b, esp,N)); printf("试位法结果为%lf\n", fun2(a, b, esp, N)); printf("牛顿法的结果为%lf", fun3(b, 0.001, N)); 15 getchar(); getchar(); } double quest(double x) { return (x*x*x - x - 1); } double quest2(double x) { return (3 * x*x - 1); } double fun(double a, double b, double esp, int N) //平分法{ int n = 1; double x,fval; if (quest(a)*quest(b) > 0) { printf("There are no roots in this area!\n"); return 0; } while (n<=N) { x = (a + b) / 2; if (x - a < esp) return x; fval = quest(x); if (fval == 0) return x; if (fval*quest(a) < 0) { b = x; } else { a = x; } n++; } return -1; } 16 double fun2(double a, double b, double esp, int N) //试位法{ int n = 1; double x, fval; if (quest(a)*quest(b) > 0) { printf("There are no roots in this area\n"); return 0; } while (n <= N) { x = (a*quest(b)-b*quest(a))/(quest(b)-quest(a)); if (x - a < esp) return x; fval = quest(x); if (fval == 0) return x; if (fval*quest(a) < 0) { b = x; } else { a = x; } n++; } return -1; } double fun3(double x, double esp, int N) //牛顿法 { int n = 1; double a; while (n <= N) { a = x; x = x - quest(x) / quest2(x); if (quest(x) == 0) return x; 17 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 南华大学 实验报告 实验项目名称：基桩动测 班级学号姓名同组人 实验教师实验日期审批 一、实验介绍 基桩反射波法是一种主要用于检测桩身结构完整性的无损检测技术，一般用于评价桩基混凝土质量、检验工程桩桩身完整性、判断缺陷位置，并协助设计、施工单位对所存在的缺陷提出消除措施。也可以用来对不同地质条件下的桩进行检测评价，指出其对本工程不利的因素以及评价工程桩竖向承载能力。 二、实验目的 1. 熟悉RS-1616K(s)基桩动测仪的操作； 2.检测混凝土灌注桩的桩身缺陷及其位置； 3.判定桩身完整性类别。 三、实验原理 基桩反射波法检测桩身结构完整性的基本原理是：通过在桩顶施加激振信号产生应力波，该应力波沿桩身传播过程中，遇到不连续界面（如蜂窝、夹泥、断裂、孔洞等缺陷）和桩底面时，将产生反射波，检测分析反射波的传播时间、幅值和波形特征，就能判断桩的完整性。 检测设备及现场联接图如下： 三、实验仪器设备 1．混凝土灌注桩：桩径Φ300，桩长6m，混凝土强度等级C25；2．RS-1616K(s)基桩动测仪主机、传感器、力锤； 3．Windows平台分析处理软件； 4．耦合剂； 5．其他附件。 四、实验内容 1．根据提供的实验桩选择传感器和力锤； 2．完成传感器的连接与安装； 3．采集信号并在分析仪上进行数据分析； 4．传输数据至计算机，利用软件进行数据分析和处理。 五、实验步骤 1．连接分析仪主机与传感器，清理桩头，安装传感器； 2．开机，输入工程信息并设置工作参数； 3．用力锤敲击桩头，检查波形的重复性和可鉴别性； 4．进入分析页面，对波形进行处理，判读桩身缺陷类型和位置； 5．关机，插入U盘，重新开机，进行数据传输； 6．将测试数据导入计算机，利用软件对数据进行进一步处理和分析，生成测试 报告。 六、测试结果 经现场测试，由武汉岩海专用软件输出桩基测试曲线如下图： 由图上得出?t=3.42ms，V=2L/?t=2?6/3.42=3510m/s ?t1=1.13ms，L q=V?t/2=3510?1.13/2/1000=2.0 m 七、结论 经测试得出如下结论： 1.所测试桩基桩身砼波速为3510m/s； 2. 所测试桩在约2.0m处有轻微缺陷存在； 3.根据规范《建筑基桩检测技术规范（JGJ106-2003）》和测试结果，所测试桩被判断为Ⅱ类桩。 计算机网络实验报告 专业计算机科学与技术 班级计102 学号109074057 姓名王徽军 组号一组D 指导教师毛绪纹 安徽工业大学计算机学院 二○一二年十二月 目录 实验总体说明 (3) 实验一以太网帧的构成 (3) 实验三路由信息协议RIP (8) 实验四传输控制协议TCP (10) 实验五邮件协议SMTP、POP3、IMAP (12) 实验六超文本传输协议HTTP (14) 实验总体说明 1．实验总体目标 配合计算机网络课程的教学，加强学生对计算机网络知识（TCP/IP协议）的深刻理解，培养学生的实际操作能力。 2．实验环境 计算机网络协议仿真实验室： 实验环境：网络协议仿真教学系统（通用版）一套 硬件设备：服务器，中心控制设备，组控设备，PC机若干台 操作系统：Windows 2003服务器版 3．实验总体要求 ●按照各项实验内容做实验，记录各种数据包信息，包括操作、观察、记录、分析， 通过操作和观察获得直观印象，从获得的数据中分析网络协议的工作原理； ●每项实验均提交实验报告，实验报告的内容可参照实验的具体要求，但总体上应包 括以下内容：实验准备情况，实验记录，实验结果分析，算法描述，程序段，实验过程中遇到的问题以及对思考问题的解答等，实验目的、实验原理、实验步骤不需要写入实验报告中。 实验一以太网帧的构成 实验时间：_____________ 成绩：________________ 实验角色：_____________ 同组者姓名：______________________________ 练习一：领略真实的MAC帧 q....U 00000010: 85 48 D2 78 62 13 47 24 58 25 00 00 00 00 00 00 .H襵b.G$X%...... 00000020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 00000030: 00 00 00 00 00 00 00 00 00 00 00 00 ............ 练习二：理解MAC地址的作用 ●记录实验结果 表1-3实验结果 本机MAC地址源MAC地址目的MAC地址是否收到，为什么 主机B 8C89A5-7570BB 8C89A5-757113 8C89A5-7570C1 是，主机A与主机B接在同一共享模块 主机D 8C89A5-771A47 8C89A5-757113 8C89A5-7570C1 是，主机C与主机D接在同一共享模块 主机E 8C89A5-757110 无无否，与主机A、C都不在同一共享模块 主机 F 8C89A5-7715F8 无无否，与主机A、C都不在同一共享模块 练习三：编辑并发送MAC广播帧 ●结合练习三的实验结果，简述FFFFFF-FFFFFF作为目的MAC地址的作用。 答：该地址为广播地址，作用是完成一对多的通信方式，即一个数据帧可发送给同一网段内的所有节点。 练习四：编辑并发送LLC帧 ●实验结果 帧类型发送序号N（S）接受序号N（R） LLC 001F 0 ●简述“类型和长度”字段的两种含义 答：一是如果字段的值小于1518，它就是长度字段，用于定义下面数据字段的长度；二是如果字段的值大于1536，用于定义一个封装在帧中的PDU分组的类型。 思考问题： 1.为什么IEEE802标准将数据链路层分割为MAC子层和LLC子层？ 答：出于厂商们在商业上的激烈竞争，IEEE的802委员会未能形成一个统一的、最佳的局域网标准，而是被迫制定了几个不同标准，如802.4令牌总线网、802.5令牌环网等。为了使数据链路层能更好地适应多种局域网标准，802委员会就将局域网的数据链路层拆成两个子层，即逻辑链路控制 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 二密度试验 2.1基本原理： 土(体)的密度是指土的单位体积的质量，单位是g/cm3或kg/m3，土的密度可分为天然密度（湿密度）和干密度两种。 2.2试验方法及适用围 ⑴环刀法：一般适用于原状样中的细粒土，未受扰动的砂土，以 及形状规则的土体。 ⑵蜡封法：适用于具有不规则形状的易碎裂的难以切割的土体。 ⑶灌砂法，灌水法：用于对粗粒土密度的测试，主要用于施工现 场的测试。 2.3 仪器设备 ⑴环刀法：环刀，天平，切土刀，钢丝锯，凡士林等 ⑵蜡封法：架盘天平（最大称量500克，感量0.01克），蜡，烧 杯，细线，针，切土刀等 ⑶灌水法：台称（最大称量20千克，感量1克，最大称量50千 克，感量5克），水平尺，铁铲，塑料薄膜，盛水桶， 装土器具等 2.4试验步骤 (环刀法) ⑴称量所使用环刀的质量和体积。 ⑵取待测试的土样，整平其两端，在环刀壁均匀地涂上一薄层 凡士林，然后将环刀刀口向下放在土样上。 ⑶将土样削成略大于环刀直径的土柱，然后将环刀向下压，边 压边削，至土样露出环刀为止，将两端余土削平修平，并取 剩余代表土样测定含水率。 ⑷擦干环刀外壁，称量环刀和土的总质量。 ⑸计算ρ0 = m /v ρd = ρ0/(1+0.01w) ⑹本试验需进行两次平行测定，其平行差值应不大于0.03g/cm3， 否则应重新测定，取两次的平均值作为该土样的密度值。 实验数据的计算过程 环刀号：315 环刀质量：42.92g 环刀＋土重：160.98g 环刀体积 60cm3 密度：（160.98g－42.92g）／60cm＝1.97g／cm3 环刀号：280 环刀质量：42.91g 环刀＋土重：164.19g 环刀体积60cm3密度：（164.19g－42.91g）／60cm＝2.02g／cm3 平均密度：（1.97+2.02）／2=1.995g/cm3 指标应用： （1）密度是土的基本物理指标之一，可用来计算土的干密度，孔隙比指标等。 (2) 用来计算土的自重应力。 (3) 用来计算地基稳定性和地基承载力。 专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日 48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类 从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法 算法的五个重要的特性 （1） 有穷性：在有穷步之后结束。 （2） 确定性：无二义性。 （3） 可行性：可通过基本运算有限次执行来实现。 （4） 有输入 表示存在数据处理 （5） 有输出 伪代码 程序设计语言（PDL ），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n 阶方阵的相加C=A+B 的算法如下，分析其时间复杂度。 #define MAX 20 ∑∑∑∑-=-=-=-=====102101010*11n i n i n i n j n n n n n n n n )O()1O(1O(11i i j i j ==∑∑==）)O(N )21O()O()O(21N 1=+=∑=∑==)(N N i i N i i 赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max （TS1,TS2 ,..., TSm ）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n). 土工实验指导书及实验报告编写毕守一 安徽水利水电职业技术学院 二OO九年五月 目录 实验一试样制备 实验二含水率试验 实验三密度试验 实验四液限和塑限试验 实验五颗粒分析试验 实验六固结试验 实验七直接剪切试验 实验八击实试验 土工试验复习题 实验一试样制备 一、概述 试样的制备是获得正确的试验成果的前提，为保证试验成果的可靠性以及试验数据的可比性，应具备一个统一的试样制备方法和程序。 试样的制备可分为原状土的试样制备和扰动土的试样制备。对于原状土的试样制备主要包括土样的开启、描述、切取等程序；而扰动土的制备程序则主要包括风干、碾散、过筛、分样和贮存等预备程序以及击实等制备程序，这些程序步骤的正确与否，都会直接影响到试验成果的可靠性，因此，试样的制备是土工试验工作的首要质量要素。 二、仪器设备 试样制备所需的主要仪器设备，包括： （1）孔径0.5mm、2mm和5mm的细筛； （2）孔径0.075mm的洗筛； （3）称量10kg、最小分度值5g的台秤； （4）称量5000g、最小分度值1g和称量200g、最小分度值0.01g的天平； （5）不锈钢环刀（内径61.8mm、高20mm；内径79.8mm、高20mm或内径61.8mm、高40mm）； （6）击样器：包括活塞、导筒和环刀； （7）其他：切土刀、钢丝锯、碎土工具、烘箱、保湿器、喷水设备、凡士林等。 三、试样制备 （一）原状土试样的制备步骤 1、将土样筒按标明的上下方向放置，剥去蜡封和胶带，开启土样筒取土样。 2、检查土样结构，若土样已扰动，则不应作为制备力学性质试验的试样。 3、根据试验要求确定环刀尺寸，并在环刀内壁涂一薄层凡士林，然后刃口向下放在土样上，将环刀垂直下压，同时用切土刀沿环刀外侧切削土样，边压边削直至土样高出环刀，制样时不得扰动土样。 4、采用钢丝锯或切土刀平整环刀两端土样，然后擦净环刀外壁，称环刀和土的总质量。 5、切削试样时，应对土样的层次、气味、颜色、夹杂物、裂缝和均匀性进行描述。 6、从切削的余土中取代表性试样，供测定含水率以及颗粒分析、界限含水率等试验之用。 习题及实验（一） 第一部分习题 一、简答题 1计算机的发展阶段： 四个发展阶段： 第一个发展阶段：1946-1956年电子管计算机的时代。1946年第一台电子计算机问世美国宾西法尼亚大 学，它由冯·诺依曼设计的。占地170平方，150KW。运算速度慢还没有人快。是计算机发展历史上的一个里程碑。（ENIAC）（electronic numerical integator and calculator)全称叫“电子数值积分和计算机”。 第二个发展阶段：1956-1964年晶体管的计算机时代：操作系统。 第三个发展阶段：1964-1970年集成电路与大规模集成电路的计算机时代 （1964-1965）（1965-1970） 第四个发展阶段：1970-现在：超大规模集成电路的计算机时代。 第一代计算机 1946 1957 电子管运算速度较低，耗电量大存储容量小。 第二代计算机 1958 1964 晶体管体积小，耗电量较少，运算速度高，价格下降。第三代计算机 1965 1971 中小规模集成电路体积功能进一步减少，可靠性及速度进一步提高。 第四代计算机 1972年至今大规模及超大规模集成电路性能到规模提高，价格大幅度降低，广泛应用于社会生活的各个领域，走进办公室和家庭 2.主要应用：计算机的应用极其广泛，早期的计算机主要体现在科学计算机，数据处理，计算机控制等几个方面．随着微型计算机的发慌和迅速普及，计算机的应用 已渗透到国民经济各个总门及社会生活的各个方面现代计算机除了传统的应用外，还应用于以下几个大方面． 1．办化自动化 2．计算机辅助系统 3．虚拟现实 4．人工智能 5．电子商务 3. 1．管理系统中的各种资源，包括硬件资源和软件资源。 1）监视资源 2）决定分配资源策略 3）分配资源 4）回收资源 2．为用户提供友好的界面。 1）命令行界面 2）图形化界面 4．操作系统大致可分为6种类型。 简单操作系统。分时系统。实时操作系统。网络操作系统。分布操作系统。智能操作系。目前微机上常见的操作系统有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。 5. 系统软件，应用软件。 系统软件：用以实现计算机系统的管理、控制、运行、维护，并完成应用程序的装入、编译等任务的程序。系统软件是开发和运行应用软件的平台，系统软件的核心是操作系统。 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： XXXX 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (10) 题目2 切割木材 (12) 2.1题目描述 (12) 2.2算法文字描述 (12) 2.3算法程序流程 (13) 2.4算法的程序实现代码 (18) 题目3 设计题 (20) 3.1题目描述 (20) 3.2 输入要求 (20) 3.3输出要求 (20) 3.4样例输入 (20) 3.5样例输出 (20) 3.6测试样例输入 (21) 3.7测试样例输出 (21) 3.8算法实现的文字描述 (21) 3.9算法程序流程 (22) 3.10算法的程序实现代码 (23) 算法分析与设计课程总结 (26) 参考文献 (27) 题目1电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1 土工测试 实验报告书 1.分级连续加载条件下的粘性土蠕变试验 2.三轴压缩实验测土的抗剪强度参数 3.duncan-chang模型参数的确定 4.通过标准固结试验测固结系数 5.剑桥模型的推导 1分级连续加载条件下的粘性土蠕变试验 实验目的： 通过测定试样在分级连续加载条件下固结引起的变形随时间的变化，分析试样得蠕变特性及相应的模型。 实验器材：（试样采用非饱和的细粒土） 固结容器：由刚性底座、护环、环刀、上环、透水板、加压上盖和密封圈组成。（1）环刀：直径61.8mm，高度20mm，一端有刀刃，应具有一定刚度，内壁应保持较高的光洁度，宜涂一薄层硅脂和聚四氟乙烯。 （2）透水板：由氧化铝或不受腐蚀的金属材料制成。渗透系数应大于试样的渗透系数。试 样上部透水板直径宜小于环刀内径0.2~0.5mm，厚度5mm。（3）变形量测设备：量表，单位为0.1mm。（4）加荷设备：砝码、杠杆加压设备。 实验步骤： 1.制备土样将土块加水饱和，尽量搅拌至各处含水率均匀，备用。用电子秤秤环刀的 重量。 2.取土样用环刀切取已准备好的土样，用工具沿环刀高度切平土面，去掉多余的土、 用水浸湿，将滤纸盖在土样的两边，再次称量重量。 3.安装土样将环刀和土样一起放入固结盒，在土样上下各放置一块透水石，盖上加压 盖，安装到加载装置上。 4.调平将加压杠杆调平，装好量表，调至零点。 5.分级加载分为4个荷载等级加载：60kpa,120kpa,180kpa,240kpa，分别为并在每 级荷载下记录0s,15s,2min15s,4min,6min15s,9min,12min15s,16min2 20min15s时的量表读数。 6.实验结束清理仪器，整理数据。 数据整理及实验分析： 室内分级加载固结蠕变实验结果如表1及图1所示： 表1 各级荷载下土的应变（mm） 图1 各种荷载作用下的蠕变曲线 蠕变是在恒定应力作用下变形随时间增长的现象。图1是土样在各种荷载作用下的蠕变曲线，在各级荷载作用下，土体的蠕变曲线非常相似。经历了加载时的瞬时变形、随时间急剧的变形，如果时间够长，还可以观察到随时间缓慢增加并趋于稳定的阶段，且荷载越大，变形越大，达到稳定的时间越长。从而粘性土的蠕变ε、应力σ与时间t的关系：ε＝f(σ,t) 且为非线性蠕变关系。 基本流变元件有虎克弹簧、牛顿粘壶及圣维南刚塑体三种，计算模型都是由以上三种线性基本元件组合而成。由于应变随时间最后达到稳定状态，则可以用麦钦特（merchant）模型来描述，该模型由虎克弹簧和伏埃脱体串联而成，如图2所示。在常应力作用下，有如下关系： ε＝σ／e0 +σ（1-exp(-e1t/k1)）/e1 图2 merchant模型 2三轴压缩实验测土的抗剪强度参数 试验目的： 实验 3、分组讨论并确定小组管理信息系统的题目，并给出题目的具体功能和要求。心得体 会：（可以从以下几个方面来总结：你在上机过程中遇到了哪些难题？你是怎么克服的？你的收获有哪些？你有什么没有解决的问题等） 实验 书E 选脚 ■1. 订盼蔚豆 建立学生表 则剩余不够的部分还须向其他书商订购，同时 在订购信息中添加该教材在另一个书商中订购的信息。 1、请画出上述内容的 E-R 图。 2、把E-R 图转换成合理的关系模式： 学 生（学号，姓名，性别，院系，年龄） 教 材（书号，书名，出版社，出版日期, 书商（商号，电话，联系人，商名） 山膿E 軀 nanie = ^Buy_Booksdb ， j filename - J E: \Buy_Bcoksdb* mdf', size = 5j maxsize - 20, f llegrovrth = 1 ) log on ( rtajne-' Buy^Bookslog 1、 f ilenajue~， E:\Buy_Bcakslog. ldf'. size=2_, maxsize! 8, fllegrawth-1 ] Go 口. ■号, 3、在SQL Serve r （或Access ）中建立数据库和表（截图） 建立数据库： create database Buy Books on primary 主键为学号 主编） 主键为书号 主键为商号 ' —i r - ! 見意「腿 性别 商号 1 ---------- 戟条人 CREATE TABLE St udent ( Sno char 9- primary key. Sname char (20 i unique, Ssex char (2), Sage smallint. Sdept char (2Q 1 ) f -f 建立教材表 CREATE TABLE Books ( Eno char 9) primary key Btitle char (40), Bauthor char ^20), Bpress char 40 Bdate datetime ): 建立书商表 -CREATE TABLE SSellcr BSno char 9[ priinaty key, BSnane char 201 . Tel char 30；. Person char (201 feedback char '40 1 鼻 /*书号* /車书名*/ 八作者于/ /廉也版社康/ " 由版日期柑 《算法分析与设计》2020年03月考试考前练习题 一、简答题 附：参考答案 1. 何谓P、NP、NPC问题。 解答: P（Polynomial问题）：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 2. 动态规划算法的基本思想是什么？它和分治法有什么区别和联系？ 解答: 动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复子问题，为了避免子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可构造出所求问题的最优解。 分治法也是将待求解的大问题分成若干个规模较小的相同子问题，即该问题具有最优子结构性质。规模缩小到一定的程度就可以容易地解决。所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；利用该问题分解出的子问题的解可以合并为该问题的解。 3. 贪心算法和动态规划算法都要求问题具有共同的性质是？ 解答: 最优子结构性质。 4. 为什么用分治法设计的算法一般有递归调用？ 解答: 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。 5. 简述分治法所能解决的问题一般应具有的特征。 解答: 1）该问题的规模缩小到一定的程度就可以容易地解决； 2）该问题具有最优子结构性质； 3）利用该问题分解出的子问题的解可以合并为该问题的解； 4）该问题所分解出的各个子问题是相互独立的。 6. 在回溯法中，为了避免无效的搜索，通常采用哪两种剪枝策略？ 解答: 约束剪枝，限界剪枝。 7. 给定如下二分搜索算法，请分析算法的复杂性。 int BinarySearch(Type a[], const Type& x, int l, int r){ while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } 算法分析与设计习题集 基础篇 1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？ 2、算法的时间复杂度指的是什么？如何表示？ 3、算法的空间复杂度指的是什么？如何表示？ 4、设某一函数定义如下： 编写一个递归函数计算给定x的M（x）的值。 本函数是一个递归函数，其递归出口是： M（x）= x-10x>100 递归体是： M（M（x+11））x ≤100 实现本题功能的递归函数如下： intm ( intx ) { int y; if ( x>100 )return(x-10 ); else { y =m(x+11) ; return (m (y )); } } 5、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相 同的元素。 本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下： voiddel ( seqlist*a ) { inti=0, j; while ( i ①计算结点总数 int CountNode(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&rooot->rchild==Null) return(1); else { num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } } ②计算叶子总数 int CountLeafs(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&root->rchild==Null) return(1); else { num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2); } } 分治术 7、有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假 的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。 8、利用分治策略，在n个不同元素中找出第k个最小元素。 9、设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 （1）每个选手必须与其它n-1选手各赛一次； （2）每个选手一天只能赛一次。 10、已知序列{503，87，512，61，908，170，897，275，652，462}，写一个自底向上的 归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。 void Merge(ElemType *r，ElemType *rf，int u，int v，int t) { f or(i=u，j=v，k=u；i 土工试验报告 班级：建工三班 专业：建筑工程技术 组号：第五组 姓名：路兆兆刘昕 刘势豪刘向辉 2014年12月 试验四 压缩试验（杠杆式压缩仪法） 一、试验目的 测定试样在侧限与轴向排水条件下的变形和压力或空隙比和压力的关系曲线。并根据孔隙比与压力的关系曲线计算出压缩系数和压缩模量等土的压缩性指标，以便判断土的压缩性和计算基础沉降时用。 二、试验方法 快速固结试验法 三、仪器设备 （1）固结容器；由环刀（内径61.8mm ，高度为20mm ），护环，透水版，水槽，加压上盖等组成。 （2）加压设备；可采用量程为5~10KN 的杠杆式，磅秤式或其他加压设备。 （3）变形量测设备；可采用量程为10mm ，最小分度值为0.01的百分表，也可采用准确度为全量程0.2%的位移传感器。 （4）其他；刮土刀，钢丝锯，天平，秒表，滤纸等。 四、操作步骤 （1）根据工程需要，切取原状土试样或人工制备扰动土的试样。 （2）从固结容器中取出环刀，按密度实验方法切取试样，然后称环刀和式样的总质量，扣除环刀质量既得湿式样的质量，并计算出土的密度。 （3）用切去试样时修下的土测定含水率。 （4）在固结容器内放置呼唤，透水板和薄型滤纸，将带有试样的环刀装入护环内，放上导环，试样上依次放上博型滤纸，透水板和加压上盖，并将固结容器置于加压框架正中，使加压上盖与加压框架中心对准，安装百分表或位移传感器。 （5）检查加压设备是否灵活。 （6）施加1KN 的预压力使试样与仪器上下各部件之间接触，将百分表或传感器调整到零位或测度初读数。 （7）确定需要施加的各级压力，压力等级宜为12.5,25,50,100,200,400,800,1600,3200KPA 。第一等级压力的大小应使土的软硬程度而定，宜为12.5,25，或50KPA 。最后一级压力应大于土的自重应力与附加应力之和。只需测定压缩系数时，最大压力不小于400KPA. （1）四、试验注意事项 1．首先装好试样，再安装量表。在装量表的过程中，小指针需调至整数位，大指针调至零，量表杆头要有一定的伸缩范围，固定在量表架上。 2．加荷时，应按顺序加砝码；试验中不要震动实验台，以免指针产生移动。 五、成果整理 1.按下式计算试样的初始孔隙比e 0 1 )1(e 0 00-+ρρW S W G ＝算法分析与设计复习题及参考答案
算法分析与设计总结
土工实验报告标准
计算机网络实验报告 答案讲解
算法设计与分析复习题目及答案
土工实验报告
算法分析与设计
算法分析与设计
土工实验指导书及实验报告
郑大计算机实验报告答案
算法分析与设计习题集整理
算法设计与分析基础课后习题答案
算法分析与设计-课程设计报告
土工试验实训报告
管理信息系统实验报告答案要点
算法分析与设计
算法分析与设计习题集
土工实验报告
相关主题
文本预览