XI`AN TECHNOLOGICAL UNIVERSITY 课程设计报告
目录
一、问题描述 (2)
二、思路描述 (2)
三、源代码展示 (3)
四、函数介绍 (6)
1、判断输入的顶点是否存在矩阵中 (6)
2、着色函数 (7)
3、判断这个颜色能不能满足要求函数 (8)
五、调试运行 (8)
1、中国地图简略图 (8)
2、取地图一部分进行测试 (8)
3、运行结果 (9)
六、算法分析 (9)
七、总结 (11)
一、问题描述：
设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少。
二、思路描述：
已知中国地图，对各省进行着色，要求相邻省所用的颜色不同，并保证使用的颜色数最少，将各省进行编号，然后利用无向图的顶点之间的边来表示各省的相邻关系，将各编号进行逐一着色，利用循环语句遍历各省，判断语句判断是否符合要求；演示程序，以用户和计算机的对话方式进行，最后结果做出简单分析及总结。
三、源代码展示：
#include
#include
#define MAXedg 100
#define MAX 0
#define N 4
int color[30]={0};
struct Graph
{
char vexs[MAXedg];
int arcs[MAXedg][MAXedg]; int vnum,arcnum;
};
int LocateVex(Graph G,char u) {
int i;
for(i=1;i<=G.vnum;i++)
{
if(u==G.vexs[i])
return i;
}
if(i==G.vnum)
{
printf("Error u!\n");
exit(1);
}
return 0;
}
void CreateGraph(Graph &G) {
int i,j,k, w;
char v1,v2;
printf("输入图的顶点数和边数:\n");
scanf("%d%d",&G.vnum,&G.arcnum);getchar();
printf("输入图的各顶点：\n");
for(i=1;i<=G.vnum;i++)
{
scanf("%c",&G.vexs[i]); getchar();
}
for(i=0;i<=G.vnum;i++)
for(j=0;j<=G.vnum;j++)
G.arcs[i][j]=MAX;
printf("输入边的两个顶点和权值(均用1表示):\n"); for(k=0;k { scanf("%c", &v1);getchar(); scanf("%c", &v2);getchar(); scanf("%d", &w); getchar(); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=w; G.arcs[j][i]=w; } } void PrintGraph(Graph G) { int i,j; printf("图的各顶点：\n"); for(i=1;i<=G.vnum;i++) { printf("%c ",G.vexs[i]); }printf("\n"); printf("图的邻接矩阵：\n"); for(i=1;i<=G.vnum;i++) { for(j=1;j<=G.vnum;j++) printf("%d ",G.arcs[i][j]); printf("\n"); } } int colorsame(int s,Graph G) { int i,flag=0; for(i=1;i<=s-1;i++) { if(G.arcs[i][s]==1&&color[i]==color[s]) { flag=1;break; } } return flag; } void output(Graph G) { for(int i=1;i<=G.vnum;i++) { printf("%d ",color[i]); } printf("\n"); } void trycolor(int s,Graph G) { int i; if(s>G.vnum)/*递归出口*/ { output(G); exit(1); } else { for(i=1;i<=N;i++) { color[s]=i; if(colorsame(s,G)==0) trycolor(s+1,G); } } } int main() { Graph G; CreateGraph(G); PrintGraph(G); printf("着色方案:\n"); trycolor(1,G); return 0; } 四、函数介绍： 1、判断输入的顶点是否存在矩阵中： int LocateVex(Graph G,char u) { int i; for(i=1;i<=G.vnum;i++)/*从第一个结点开始到最后一个结点看是否存在*/ { if(u==G.vexs[i]) /*结点集合*/ return i; /找到并返回*/ } if(i==G.vnum) /*从第一个结点开始到最后一个结点都不存在*/ { printf("Error u!\n"); exit(1); } return 0; } 2、着色函数： void trycolor(int s,Graph G)/*s为开始图色的顶点，本算法从1开始*/ { int i; if(s>G.vnum)/*递归出口*/ { output(G); exit(1); } else { for(i=1;i<=N;i++)/*对每一种色彩逐个测试*/ { color[s]=i; if(colorsame(s,G)==0) { trycolor(s+1,G);/*进行下一块的着色*/ } } } } 3、判断这个颜色能不能满足要求函数： int colorsame(int s,Graph G)/*判断这个颜色能不能满足要求*/ { int i,flag=0; for(i=1;i<=s-1;i++)/*分别与前面已经着色的几块比较*/ if(G.arcs[i][s]==1&&color[i]==color[s]) { flag=1;break; } return flag; } 五、调试运行： 1、中国地图简略图 2、取地图一部分进行测试 有6个顶点，8条边。 各点相邻情况为：a-b ,a-e ,b-c ,b-d ,b-e ,c-d, d-e e-f 3、运行结果 六、算法分析： 地图着色主要使用回溯法，回溯法解题的一般步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。如果其中i个顶点已经着色，并且相邻两个顶点的颜色都不一样，就称当前的着色是有效的局部着色；否则，就称为无效的着色。 如果由根结点到当前结点路径上的着色，对应于一个有效着色，并且路径的长度小于n，那么相应的着色是有效的局部着色。这时，就从当前结点出发，继续探索它的儿子节点，并把儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为死结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有m个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为死结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为死结点，或者搜索路径长度等于n，并找到了一个有效的着色为止。 由于用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元一维数组C[i]来描述图的一种可能着色，表示赋予顶点i的颜色。例如，5元一维组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图（a）的一种着色，顶点a着颜色1，顶点b着颜色2，顶点c着颜色2，等等。如果在n元一维组C[i]中，所有相邻顶点都不会着相同颜色，就称此n元一维组为可行解，否则为无效解。容易看出，每个顶点可着颜色有m种选择，n个顶点就有m n种不同的着色方案，问题的解空间是一棵高度为n的完全m叉树，这里树高度的定义为从根节点到叶子节点的路径的长度。每个分支结点，都有m个儿子结点。最底层有m n个叶子结点。例如，表示用3种颜色为3个顶点 的图着色的状态空间树。如图所示，对第i（i>=1）层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。 七、总结： 对中国地图着色即图着色问题，用m种颜色来为无向图着色，其中顶点个数为n 。因此，用一个n元组来描述图的一种着色。在这种着色中，所有相邻的顶点都不会具有相同的颜色，这种着色就是有效着色。根据这种思想编写中国地图着色算法，算法主要使用回溯法。根据算法运行，可以看出，无论有多少点，点与点之间怎样相邻，都只需要4种颜色就可以完成着色。 通过此次对中国地图着色问题的探究，我更好更深入了学习了着色问题中回溯法的运用，在课堂上学习的理论知识只有运用到实践里才能被更好的掌握。 操作系统 (实验报告) 银行家算法姓名：***** 学号：***** 专业班级：***** 学验日期：2011/11/22 指导老师：*** 一、实验名称： 利用银行家算法避免死锁 二、实验内容： 需要利用到银行家算法，来模拟避免死锁：设计M个进程共享N类资源，M个进程可以动态的申请资源，并可以判断系统的安全性，进行打印出，相应的安全序列和分配表，以及最后可用的各资源的数量。 三、实验目的： 银行家算法是一种最有代表性的避免死锁的算法，在避免死锁的方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。 为实现银行家算法，系统必须设置若干数据结构，所以通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁，产生死锁的必要条件，安全状态等重要的概念，并掌握避免死锁的具体实施方法。 四、实验过程 1.基本思想： 我们可以把操作系统看成是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程申请到资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过再测试系统现资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 安全状态就是如果存在一个由系统中所有进程构成的安全序列P1……则系统处于安全状态。安全状态是没有死锁发生。而不安全状态则是不存在这样一个安全序列，从而一定会导致死锁。 2.主要数据结构： (1)可利用资源向量Available.这是一个含有m个元素的数组，其中的每一个 元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类的资源的分配和回收而动态地改变，如果Available[j]=K,则表示系统中现有Rj类资源K个。 (2)最大需求矩阵Max.这是一个n*m的矩阵，定义了系统中n 个进程中的每 一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K. (3)分配矩阵Allocation.这也是一个n*m的矩阵，它定义了系统中每一类资源 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类问题。。 华南农业大学期末考试试卷（A卷） 2004学年第二学期(2005.6)考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟 学号姓名年级专业 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了 A 。 （A）二义性（B）有限性（C）正确性（D）可终止性 2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n（C）2n2（D）3nlog3n 4、渐进算法分析是指 B 。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？C （A）大O表示法（B）大Ω表示法 （C）Θ表示法（D）小o表示法 6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是 B 。 （A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用 C 来实现。 （A）有序的线性表（B）队列（C）栈（D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。C （A）问题规模相同，问题性质相同 （B）问题规模相同，问题性质不同 （C）问题规模不同，问题性质相同 （D）问题规模不同，问题性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面 D 答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面 C 答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解 11、关于回溯搜索法的介绍，下面D是不正确描述。 （A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 改：树结构 回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理》 题目：银行家算法 班级： 学号： 姓名： 一、实验目的 银行家算法是操作系统中避免死锁的典型算法，本实验可以加深对银行家算法的步骤和相关数据结构用法的更好理解。 实验环境 Turbo C 2.0/3.0或VC++6.0 实验学时 4学时，必做实验。 二、实验内容 用C语言编写一个简单的银行家算法模拟程序，用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。进程可动态地申请资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。 三、实验说明 实验中进程的数量、资源的种类以及每种资源的总量Total[j]最好允许动态指定。初始时每个进程运行过程中的最大资源需求量Max[i,j]和系统已分配给该进程的资源量Allocation[i,j]均为已知（这些数值可以在程序运行时动态输入），而算法中其他数据结构的值（包括Need[i,j]、Available[j]）则需要由程序根据已知量的值计算产生。 四、实验步骤 1、理解本实验中关于两种调度算法的说明。 2、根据调度算法的说明，画出相应的程序流程图。 3、按照程序流程图，用C语言编程并实现。 五、分析与思考 1．要找出某一状态下所有可能的安全序列，程序该如何实现？ 答：要找出这个状态下的所有可能的安全序列，前提是要是使这个系统先处于安全状态，而系统的状态可通过以下来描述： 进程剩余申请数=最大申请数-占有数；可分配资源数=总数-占有数之和； 通过这个描述来算出系统是否安全，从而找出所有的安全序列。 2．银行家算法的局限性有哪些？ 算法设计与分析试卷(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 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 ）。 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 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．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 课程设计报告课程设计名称共享资源分配与银行家算法 系（部） 专业班级 姓名 学号 指导教师 年月日 目录 一、课程设计目的和意义 (3) 二、方案设计及开发过程 (3) 1.课题设计背景 (3) 2.算法描述 (3) 3.数据结构 (4) 4.主要函数说明 (4) 5.算法流程图 (5) 三、调试记录与分析 四、运行结果及说明 (6) 1．执行结果 (6) 2．结果分析 (7) 五、课程设计总结 (8) 一、程设计目的和意义 计算机科学与技术专业学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，其目的在于加深催操作系统基础理论和基本知识的理解，加强学生的动手能力.银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法 二、方案设计及开发过程 1.课题设计背景 银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待 2.算法描述 1）如果Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi 需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti[j]<= Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 2）如果Requesti[j]<=Available[j],便转向步骤3，否则，表示尚无足够资源，进程Pi须等待。 3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]:=Available[j]-Requesti[j]; Allocation[i,j]:=Allocation[i,j]+Requesti[j]; Need[i,j]:=Need[i,j]-Requesti[j]; HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 计算机操作系统实验报告 一、实验名称：银行家算法 二、实验目的：银行家算法是避免死锁的一种重要方法，通过编写 一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 三、问题分析与设计： 1、算法思路：先对用户提出的请求进行合法性检查，即检查请 求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。 2、银行家算法步骤：（1）如果Requesti＜or =Need,则转向步 骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣 布的最大值。 （2）如果Request＜or=Available,则转向步骤（3）；否则，表示 系统中尚无足够的资源，进程必须等待。 （3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构 中的数值： Available=Available-Request[i]; Allocation=Allocation+Request; Need=Need-Request; (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安 全状态。 3、安全性算法步骤： （1）设置两个向量 ①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation; ②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。 （2）从进程集合中找到一个能满足下述条件的进程： ①Finish[i]=false ②Need 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行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比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n n n n n -+≥-+≥，所以，可选4c =，08n =。对于0n n ≥， 22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。 （3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥， 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： 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. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系 一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。 成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日 课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分 操作系统课程设计实验报告用C实现银行家算 法 文档编制序号：[KKIDT-LLE0828-LLETD298-POI08] 操作系统 实 验 报 告 (2) 学院：计算机科学与技术学院 班级：计091 学号：姓名： 时间：2011/12/30 目录 1.实验名称 (3) 2.实验目的 (3) 3.实验内容 (3) 4.实验要求 (3) 5.实验原理 (3) 6.实验环境 (4) 7.实验设计 (4) 数据结构设计 (4) 算法设计 (6) 功能模块设计 (7) 8.实验运行结果 (8) 9.实验心得 (9) 附录：源代码（部分） (9) 一、实验名称： 用C++实现银行家算法 二、实验目的： 通过自己编程来实现银行家算法，进一步理解银行家算法的概念及含义，提高对银行家算法的认识，同时提高自己的动手实践能力。 各种死锁防止方法能够阻止发生死锁，但必然会降低系统的并发性并导致低效的资源利用率。死锁避免却与此相反，通过合适的资源分配算法确保不会出现进程循环等 待链，从而避免死锁。本实验旨在了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生。 三、实验内容： 利用C++,实现银行家算法 四、实验要求： 1.完成银行家算法的设计 2.设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。 五、实验原理： 系统中的所有进程放入进程集合，在安全状态下系统收到进程的资源请求后，先把资源试探性的分配给它。之后，系统将剩下的可用资源和进程集合中的其他进程还需要的资源数作比较，找出剩余资源能够满足的最大需求量的进程，从而保证进程运行完毕并归还全部资源。这时，把这个进程从进程集合中删除，归还其所占用的所有资源，系统的剩余资源则更多，反复执行上述步骤。最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正执行本次分配，否则，本次资源分配暂不实施，让申请资源的进程等待。 银行家算法是一种最有代表性的避免的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。 《算法设计与分析》教学大纲 一、课程概述 算法设计是计算机科学的一门分支学科，是软件技术的一个重要方向。算法设计既是软件设计的关键，也是培养学生成为未来软件工程师所不可或缺的一门专业知识。 算法设计与分析课程将高级语言程序设计、数据结构和计算方法等内容紧密地结合在一起，全面培养学生分析问题、解决问题的能力。这门学科的重点是在培养和培训学生学会经典算法方面的知识与应用，因此它对学生的专业发展具有极其重要的意义。 算法设计与分析的先修课程是高级语言程序设计、数据结构、高等数据、组合数学。 二、课程目标 1.知道《算法设计与分析》这门学科的性质、地位和独立价值。知道这门学科的研究 范围、分析框架、研究方法、学科进展和未来方向。 2.理解这门学科的主要概念，尤其是算法的时间复杂度和空间复杂度。 3.初步学会运用数学的方法推导和证明算法的时间复杂度和空间复杂度。 4.掌握常用的经典算法，培养学生在软件设计时对算法设计的重视，并能够把所学的 知识应用到具体的软件设计实践中去。 三、课程内容和要求 这门学科的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下： 知道———是指对这门学科和教学现象的认知。 理解———是指对这门学科涉及到的概念、原理、策略与技术的说明和解释，能提示所涉及到的教学现象演变过程的特征、形成原因以及教学要素之间的相互关系。 掌握———是指运用已理解的教学概念和原理说明、解释、类推同类教学事件和现象。 学会———是指能模仿或在教师指导下独立地完成某些教学知识和技能的操作任务，或能识别操作中的一般差错。 教学内容和要求表中的“√”号表示教学知识和技能的教学要求层次。 本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。银行家算法实验报告
中科院陈玉福计算机算法设计与分析期末简答题答案
2005.6算法设计与分析课程期末试卷
算法设计与分析课后部分习题答案
银行家算法-实验报告
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
算法设计与分析课程设计报告样本
银行家算法_实验报告
算法设计与分析课程设计(完整版)
计算机操作系统银行家算法实验报告
算法设计与分析期末试题答案解析
算法设计与分析课程设计报告
算法设计与分析C++语言描述(陈慧南版)课后答案
算法设计与分析试卷及答案.doc
算法设计与分析课程设计-实验指导书
计算机算法设计与分析课程设计.
操作系统课程设计实验报告用C实现银行家算法
《算法设计与分析》教学大纲
相关主题
文本预览