《算法设计与分析大作业报告》
班级：
学号：
姓名：
分治法大作业报告
问题陈述：
编程实现归并排序算法和快速排序算法，输出排序结果。输入10组相同的数据，验证排序结果和完成排序的比较次数。
分治法基本思想：
分治法的基本思想是将问题分解成若干个子问题，然后求解子问题。子问题较原问题要容易些，先得出子问题的解，由此得出原问题的解，这就是所谓“分而治之”的思想。
算法描述：
当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 1.归并排序的思想：将A（1），……，A（N）分成两个集合，对每个集合单独分类，然后将已分类的两个序列归并成一个含N个元素分好类的元素 2.快速排序的思想：选取A的某个元素做为划分元素，然后将其他元素重新排列，使在划分元素以前出现的元素都小于或等于它，在划分元素之后出现的划分元素都大于等于它。程序代码： #include #include #include void MergeSort(int *data,int x,int y,int *temp) { int p,q,m,i=x; if (y-x>1) {m = x+(y-x)/2; p = x; q = m; MergeSort(data,x,m,temp); MergeSort(data,m,y,temp); while(p { if (q>=y||(p {temp[i++] = data[p++];} else {temp[i++] = data[q++];} } for(i=x;i data[i] = temp[i]; } } void HoareSort(int *data,int x,int y) { int p=x,q=y-1,temp; while(p while (q>p&&data[q]>=data[p]) q--; if (q>p) { temp = data[p],data[p] = data[q],data[q] =temp; p++; } while(q>p&&data[p]<=data[q]) p++; if (p { temp = data[p],data[p] = data[q],data[q] =temp; q--; } if (p==q) { HoareSort(data,x,p); HoareSort(data,p+1,y); }}} int main() { int data[10],i; int temp[10]; srand(time(NULL)); for (i=0;i<10;i++) { data[i] = rand()%100; } printf("未排序排序的数据为：\n"); for (i=0;i<10;i++) {printf("%d ",data[i]);} printf("\n"); printf("归并排序的顺序为： \n"); MergeSort(data,0,10,temp); for (i=0;i<10;i++) {printf("%d ",data[i]); } printf("\n"); printf("快速排序的顺序为： \n"); HoareSort(data,0,10); for (i=0;i<10;i++) {printf("%d ",data[i]);} printf("\n"); return 0; } 运行结果： 结论分析： 归并排序和快速排序都是递归排序，但是归并排序是稳定的排序方法，快速排序是不稳定的排序方法。（1）此问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（2）利用该问题分解出的子问题的解可以合并为该问题的解；（3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 动态规划大作业报告 问题陈述： 定义0-1背包问题为：}y v max{n 1i i i ∑=。限制条件为：c y w n 1i i i ≤∑=，且n i {0,1},1y i ≤≤∈。i v 和i w 分别表示第i 个物品的价值和重量，c 为背包容量。 动态规划基本思想： 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 算法描述： 刻画0-1背包问题的最优解的结构。 可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n ，即xn=1，那么其余x1，x2，...，x(n-1)一定构成子问题1，2，...，n-1在容量W-wn 时的最优解。如果这个最优解不包含物品n ，即xn=0，那么其余x1，x2，...，x(n-1)一定构成子问题1，2，...，n-1在容量W 时的最优解。递归定义最优解的值，根据上述分析的最优解的结构递归地定义问题最优解。设c[i,w]表示背包容量为w 时，i 个物品导致的最优解的总价值，得到下式。显然要求c[n,w]。 程序代码： #include using namespace std; void Path(int n, int W, int c[][100], int *v, int *wei) { memset(*c, 0, (W+1)*sizeof(int)); for (int i = 1; i <= n; i++) { c[i][0] = 0; for (int w = 1; w <= W; w++) { if (wei[i-1] > w) { c[i][w] = c[i-1][w]; } else { int temp = c[i-1][w-wei[i-1]] + v[i-1]; if (c[i-1][w] > temp) { c[i][w] = c[i-1][w]; } else c[i][w] = temp; }}}} void find(int c[][100], int *x, int *wei, int n, int W) { int w = W; for (int i = n; i >= 2; i--) { if (c[i][w] == c[i-1][w]) { x[i-1] = 0; } else { x[i-1] = 1; w = w - wei[i-1]; } } if (c[1][w] == 0) x[0] = 0; else x[0] = 1; } int main() int n = 5; int W = 100; int w[] = {10,48,35,23,25,30}; int v[] = {40,10,20,30,50}; int c[6][100] = {0}; Path(n, W, c, v, w); cout<<"最优的总价值为："; cout< int x[5]; find(c, x, w, n, W); cout<<"用0表示不装入，1表示装入，情况如下："< for (int i = 1; i < n+1; i++) {cout<<"第"< cout< return 0; } 运行结果： 结论分析： 上述代码的时间复杂度为O(nw)。能表示出装入或者不装入但计算出装入后的总价值有点问题，程序还不够完善有待改进。动态规划问题的的实质就是寻求一个最优解的过程，实质就是为问题寻求一个最优算法，这个最优算法解出来的值是运用所有算法中最接近实际值的解。一般对一个问题，不会运用多种算法，而只会选取其中的一种来求解（但实际问题中常常需要不同算法的结合，不过一般是处理不同方面的算法）不同的算法对待不同的问题总是有利有弊。 贪心法大作业报告 问题陈述： 给定n种物品和一个背包.物品i的重量是Wi,其价值为Vi,背包的容量为C。在选择物品i装入背包时，可以选择物品i的一部分，1<= i <=n。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 贪心法基本思想： 贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质： 1.整体的最优解可以通过局部的最优解来求出； 2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。 算法描述： 对于背包问题,若它的一个最优解包含物品j,则从该最优解中拿出所含的物品j的那部分重量w,剩余的将是n-1个原重物品1,2,…,j-1,j+1,…,n及重为Wj-W的物品j中可装入容量为c-w的背包且具有最大价值的物品。 程序代码： #include struct goodinfo { float p; float w; float X; int flag; }; void Insertionsort(goodinfo goods[],int n) { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } } void bag(goodinfo goods[],float M,int n) { float cu; int i,j; for(i=1;i<=n;i++) goods[i].X=0; cu=M; for(i=1;i { if(goods[i].w>cu) break; goods[i].X=1; cu=cu-goods[i].w; } if(i<=n) goods[i].X=cu/goods[i].w; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].flag { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } cout<<"最优解为:"< for(i=1;i<=n;i++) { cout<<"第"< cout< }} void main() { cout<<"运用贪心法解背包问题"< int j; int n; float M; goodinfo *goods; while(j) { cout<<"请输入物品的总数量："; cin>>n; goods=new struct goodinfo [n+1]; cout<<"请输入背包的最大容量："; cin>>M; cout< int i; for(i=1;i<=n;i++) { goods[i].flag=i; cout<<"请输入第"< cin>>goods[i].w; cout<<"请输入第"< cin>>goods[i].p; goods[i].p=goods[i].p/goods[i].w; cout< } Insertionsort(goods,n); bag(goods,M,n); cout<<"请问您还要继续运行此程序吗？请用Y或者N回答。"< cin>>j; if(j=='N') break; }} 运行结果： 结论分析： 程序较完整，算法复杂度为O（N*N）。但有一点点小小的不足并没有算出物品装入后的重量，也没有展示最优解的价值为多少。 回溯法大作业报告 问题陈述： 在n×n格的棋盘上放置彼此不受攻击的n个皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。要求在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 回溯法基本思想： 从一条路往前走，能进则进，不能进则退回来，换一条路再试。当我们遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。算法描述： 解向量：(x1, x2, … , xn) 显约束：xi = 1,2, … ,n 隐约束： 1)不同列：xi != xj 2)不处于同一正、反对角线：|i-j| != |x(i)-x(j)| 解空间：满N叉树 程序代码： #include #include using namespace std; class queen { struct q_place { int x; int y; q_place () : x(0),y(0) {} }; public: queen(int qc) : q_count (qc), sum_solution (0) { curr_solution.resize (q_count); } void backtrack () { __backtrack (0); } private: void __backtrack (int t) { if (t >= q_count) { ++ sum_solution ; for (size_t i = 0;i < curr_solution.size(); ++ i) { cout << "x = " << curr_solution[i].x << " y = " << curr_solution[i].y << endl; } cout << "解决方案有" << sum_solution <<"个"<< endl; } else { for (int i = 0;i < q_count; ++ i) { curr_solution[t].x = i; curr_solution[t].y = t; if (__place(t)) { __backtrack (t + 1); } } } } bool __place (int k) { for (int i = 0; i < k; ++ i) { if ((abs(curr_solution[i].x - curr_solution[k].x) == abs(curr_solution[i].y - curr_solution[k].y)) || curr_solution[i].x == curr_solution[k].x) { return false; } } return true; } private: vector const int q_count; int sum_solution; }; int main() { int i; cout<<"请输入皇后的个数："< cin>>i; queen q(i); cout<<"各个皇后在不同位置时，对应的解决方案个数如下："< return 0; } 运行结果： 结论分析： n后问题主要在于可行解，一个一个的试，（t）能走通就往(t+1)下走，走不通就倒回去(t-1)换条走，再不行再回走。就要不停的尝试，不停的回溯，直到找全可行解，或者一个也没有就停止。还有重要的事约束条件，两个皇后不能在同行同列或者斜线上。这题需要理解程序设计的顺序结构基本思想，掌握顺序结构语句特点。并且学会用算法分析问题，能够使用顺序结构编写简单的程序解决具体问题。 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 目录 一、设计题目 二、目标和需求分析 三、开发工具 四、应用平台 五、程序模块 1、游戏盒子 2、2048 3、扫雷 4、贪吃蛇 六、开发日志 七、程序调试及运行 八、程序开发总结 总结：虽然做出来的东西真的没什么技术水平，但是我们尽量把这个东西的每个方方面面做完整。 目标和需求分析一个小的游戏盒子，可以用来启动其它游戏，当然，其它游戏也是我们大作业的编写内容，平时可以玩玩用来打发时间 用到的工具VS2005 Easyx图形库 Pthread线程库 Hge 分工 秦贤康 组织大家，编写主程序，及构思计划，技术指导 王尧 所有的文件处理，数据算法方面优化 王懿晨 合作2048模块 杨梓晗 图片资源加工，音乐裁剪，按钮制作 程维驰 合作扫雷模块 应用平台：WINDOWS X64 程序功能模块： 一、 安装包：（写入开始菜单快捷方式，桌面快捷方式，开机启动等）//pascal 脚本编写 #define MyAppName "C 大作业" #define MyAppVersion "2.0" #define MyAppPublisher "五人小组" #define MyAppExeName "1.exe" [Setup] AppId={{49DB1DB4-FAE9-4ACB-A4B9-E5C420C5F10B} AppName={#MyAppName} AppVersion={#MyAppVersion} ;AppVerName={#MyAppName} {#MyAppVersion} AppPublisher={#MyAppPublisher} DefaultDirName={pf}\{#MyAppName} DisableDirPage=yes DefaultGroupName={#MyAppName} DisableProgramGroupPage=yes （剩余代码未全部给出） 安装包 内嵌：C 语言报告 游戏盒子 开机启动，桌面快捷方式等 进入动画，左侧动画 启动模块 通知，和显示游戏信息 2048 扫雷 贪吃蛇 主界面信息显示 通知栏信息显示 意见箱 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 《供配电技术课程大作业》 报告书 题目：高低压电气设备的 维护与故障处理指导教师： 姓名： 学号： 日期： 机电工和系2013-2014学年第2学期 报告书格式要求： 一、报告前置部分 （一）摘要内容包括研究目的、方法、结果、结论（300字~400字）四部分 （二）格式要求 1．中文摘要： “摘要”（黑体三号，居中），摘要正文（居左，首行缩进两字，宋体五号）。“关键词”（黑体小四号，居左顶格，单独占行），关键词正文（宋体五号），关键词为报告研究内容3～8核心专有名词，词与词之间用分号间隔。 2．外文摘要：独占一页 “Abstract”（Times New Roman，三号，加粗，居中），Abstract正文（居左顶格，Times New Roman，五号）； “Key words”（Times New Roman，小四号，加粗，居左顶格，单独占行），Key words正文（居左顶格，Times New Roman，五号）,与中文关键词对应，词与词之间用分号间隔。 二、报告主体部分 （一）正文格式要求 1．页眉（宋体，五号，居中），由“学生姓名：论文题目”格式构成。 2．页码（页面底端（页脚），右侧）。 3．章条序码（阿拉伯数字，小圆点间隔，末尾不加小圆点，左顶格，编号后空一个字距）第一级0，1， 2， 3，…（黑体，小二号） 第二级1.1,1.2,… 2.1,2.2,… 3.1,3.2,……（黑体，小三号） 第三级 1.1.1,1.1.2,…1.2.1,1.2.2,…2.1.1,2.1.2,…2.2.1, 2.2.2,… 3.1.1,3.1.2,…3.2.1,3.2.2,……（黑体，四号） 如在条以下仍需分层，则通常用a，b，…或1),2),…编序，左空2个字距。 4．前言、引言不编序号 （二）图、表及公式格式要求 1．图表字体（宋体、五号），图表名（中外文对照、宋体、五号、居中），图表按章编号（如图1-1、表2-2等），图编号及图名置下，表编号及表名置上。 插图宽度不宜超过10cm，有刻度的坐标图不加箭头，标值线朝里，其标值数字尽量不超过3位数（如用30km代替30000m）或小数以后不多于一个“0”(如用5μg 代替0.005mg)；标目中的物理量的符号用斜体，单位符号用正体，纵坐标标目、标值逆时针旋转九十度书写；图中坐标线、尺寸线、引线0.5磅，轮廓线、函数线等主要部分0.75磅；文中图片要清晰。 表格的绘制均用三线表，表内无斜线、竖线，结构比较复杂的表可增加不通长的辅助线；表头中量的写法要规范，量的表示法不允许出现两条斜线（如：动量矩单位kg.m2/s，在表中应为L/kg.m2.s-1）；表中“空白”代表未测或无此项，“-”代表未发现，“0”代表实测数据为零。 2．公式。公式统一用Microsoft公式3.0在系统默认状态下编辑，居中放置，其前的“解”、“假设”等文字顶格书写，公式序号按章排，加圆括号，居行尾。如“（1-1）”、“（2-1）”。公式换行书写时与等号对齐，凡正文中未提到的公式可不排序。 （三）引用和注释 1．引用。引用参考文献，在正文引用位置右上角标“[1]”、“[2]”，依据出现先后次序流水编号，相同文献多处引用，统一用首次编号。 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析 1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 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、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 有限元分析大作业报告 试题1： 一、问题描述及数学建模 图示无限长刚性地基上的三角形大坝，受齐顶的水压力作用，试用三节点常应变单元和六节点三角形单元对坝体进行有限元分析，并对以下几种计算方案进行比较： （1）分别采用相同单元数目的三节点常应变单元和六节点三角形单元计算； （2）分别采用不同数量的三节点常应变单元计算； （3）当选常应变三角单元时，分别采用不同划分方案计算。 该问题属于平面应变问题，大坝所受的载荷为面载荷，分布情况及方向如图所示。 二、采用相同单元数目的三节点常应变单元和六节点三角形单元计算 1、有限元建模 （1）设置计算类型：两者因几何条件和载荷条件均满足平面应变问题，故均取Preferences 为Structural （2）选择单元类型：三节点常应变单元选择的类型是Solid Quad 4 node182；六节点三角形单元选择的类型是Solid Quad 8 node183。因研究的问题为平面应变问题，故对Element behavior（K3）设置为plane strain。 （3）定义材料参数：弹性模量E=2.1e11，泊松比σ=0.3 （4）建几何模型：生成特征点；生成坝体截面 （5）网格化分：划分网格时，拾取lineAB和lineBC，设定input NDIV 为15；拾取lineAC，设定input NDIV 为20，选择网格划分方式为Tri+Mapped，最后得到600个单元。 （6)模型施加约束：约束采用的是对底面BC 全约束。大坝所受载荷形式为Pressure ，作用在AB 面上，分析时施加在L AB 上，方向水平向右，载荷大小沿L AB 由小到大均匀分布。以B 为坐标原点，BA 方向为纵轴y ，则沿着y 方向的受力大小可表示为： }{*980098000)10(Y y g gh P -=-==ρρ 2、 计算结果及结果分析 （1） 三节点常应变单元 三节点常应变单元的位移分布图 三节点常应变单元的应力分布图 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 学院XX学院 目录 1 摘要 (3) 1.1设计题目 (3) 1.2设计容 (3) 1.3开发工具 (3) 1.4应用平台 (3) 2 详细设计 (3) 2.1程序结构 (3) 2.2主要功能 (3) 2.3函数实现 (3) 2.4开发日志 (4) 3 程序调试及运行 (4) 3.1程序运行结果 (4) 3.2程序使用说明 (4) 3.3程序开发总结 (4) 4 附件（源程序） (4) 1 摘要 1.1 设计题目 （A）求最大数;（B）高次方数的尾数 1.2 设计容 （A）求555555的约数中最大的三位数; (B)求13的13次方的最后三位数1.3 开发工具 Visual C++ 6.0和Win32。 1.4 应用平台 Windows XP 32位 2 详细设计 2.1 程序结构 (A)求最大数 定义变量a、b、c，a从100至999递增，b为555555，用b除以a，判断是否可以整除，若可以，则把a的值赋给c，a自加1；若不可，a自加1。重复以上步骤，直到a>999，输出c。循环语句采用for 循环。 （B）高次方数的尾数 定义变量i、j，i从1至13递增，j初值为1。用j乘以13，用得到的乘积除以1000并取其余数，赋给j，i自加1。重复以上步骤，直到i>13，输出j。循环语句采用for循环。 2.2 主要功能 程序功能：（A）求555555的约数中最大的三位数; (B)求13的13次方的最后三位数。 原理和方法： （A）题目的原理和方法：因为要求的是三位数，就用555555从小到大依次除以100到999的所有数，并判断能否整除，最后一个可以整除555555的数即为所求。循环语句采用for循环。 （B）题目的原理和方法：乘积的最后三位数只与乘数和被乘数的后三位数有关，因此用1乘以13，再除以1000并取余数，用余数乘以13，再除以1000并取余数，依次进行下去，累乘13个13后除以1000取得的余数即为所求。循环语句采用for循环。 2.3 函数实现 （A）求最大数 int a,b=555555,c; /*定义变量，赋初值*/ for(a=100;a<=999;a++) /*FOR循环*/ { if(b%a==0) /*利用IF语句判断b是否可以被a整除*/ c=a; /*将555555的约数赋给c*/ } printf("%d\n",c); /*输出c*/ (B)高次方数的尾数 int i,j=1; /*定义变量，赋初值*/ for(i=1;i<=13;i++) /*FOR循环*/ { j=j*13%1000; /*将j乘以13的乘积的后三位数赋给j*/ } printf("%d\n",j); /*输出j*/ 2.4 开发日志 （A）选定这个题目后，我先分析此题用何种算法完成，确定了使用FOR循环并限定除数围，然后画出程序框图，再一步步编写源代码。调试过程很顺利，只有一个地方忘加了“；”。运行程序后，结果非常满意。 （B）这个题目不难，但是也不简便，我想到只取三位数的方法，并使用FOR循环，然后画出程序框图，再一步步编写源代码。调试过程发现对其中一个变量的初值是1还是13有待解决，分析程序后发现应该用1，然后进一步调试，运行，直至结果正确。 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai算法设计与分析考试题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
C语言大作业报告
算法设计与分析实验报告贪心算法
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
大作业报告格式
算法设计与分析课程设计报告样本
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
有限元分析大作业报告
算法设计与分析试卷及答案
C语言大作业报告范文
算法设计与分析课程设计报告
算法设计与分析期末试题答案解析
算法设计与分析课程报告
算法设计与分析试卷及答案.doc
算法设计与分析实验报告
算法设计与分析试题与答案
相关主题
文本预览