成绩评定表
课程设计任务书
算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。
分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上，恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。
回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。
关键词：分治法，回溯法，棋盘覆盖，数字拆分
1分治法解决期盼覆问题 (1)
1.1问题描述 (1)
1.2问题分析 (1)
1.3算法设计 (1)
1.4算法实现 (2)
1.5结果分析 (4)
1.6算法分析 (5)
2回溯法解决数字拆分问题 (7)
2.1问题描述 (7)
2.2问题分析 (7)
2.3算法设计 (8)
2.4算法实现 (8)
2.5结果分析 (10)
参考文献 (10)
1分治法解决期盼覆问题
1.1问题描述
在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k中情形，因而有4k中不同的棋盘，图（a）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b）所示的4中不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L型骨牌不得重复覆盖
1.2问题分析
用分治策略，可以设计解决棋盘问题的一个简介算法。
当k>0时，可以将2^k *2^k棋盘分割为4个2^k-1 * 2^k-1子棋盘。由棋盘覆盖问题得知，特殊方格必位于4个较小的子棋盘中，其余3个子棋盘中无特殊方格。为了将3个无特殊方格的子棋盘转化为特殊棋盘可以将一个L型骨牌覆盖这3个较小棋盘的会合处，所以，这3个子棋盘上被L型覆盖的方格就成为给棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1*1棋盘为止。
。
1.3算法设计
将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
。
1.4算法实现
#include
int tile=1;
int board[100][100];
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
if(size==1)
return;
int t=tile++;
int s=size/2;
if(dr chessBoard(tr, tc, dr, dc, s); else { board[tr+s-1][tc+s-1]=t; chessBoard(tr, tc, tr+s-1, tc+s-1, s); } if(dr chessBoard(tr, tc+s, dr, dc, s); else { board[tr+s-1][tc+s]=t; chessBoard(tr, tc+s, tr+s-1, tc+s, s); } if(dr>=tr+s && dc chessBoard(tr+s, tc, dr, dc, s); else { board[tr+s][tc+s-1]=t; chessBoard(tr+s, tc, tr+s, tc+s-1, s); } if(dr>=tr+s && dc>=tc+s) chessBoard(tr+s, tc+s, dr, dc, s); else { board[tr+s][tc+s]=t; chessBoard(tr+s, tc+s, tr+s, tc+s, s); } } int main() { int size; cout<<"输入棋盘的size(大小必须是2的n次幂): "; cin>>size; int index_x,index_y; cout<<"输入特殊方格位置的坐标: "; cin>>index_x>>index_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;i { for(int j=0;j cout< cout< } } 1.5结果分析 1.6算法分析 设T（n）是算法ChessBoard覆盖一个2^k * 2^k棋盘所需要的时间，则从算 法 { O(1) k=0 的分治策略可知，T(k)满足如下递归方程T(k) = 4T(k-1)+O（1） k>0 解得此递归方程可得T(k) = O（4^k）。由于覆盖一个2^k *2^k棋盘所需的L 型 牌个数为（4^k — 1）/3,故算法ChessBoard是一个在渐进意义下最优的算法. 2回溯法解决数字拆分问题 2.1问题描述 整数的分划问题。 如，对于正整数n=6，可以分划为： 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1+1 用户从键盘输入 n （范围1~10）。 2.2问题分析 很明显这是一道关于数的组合的问题，但形成组合的数是有一定的限制的。仔细分析一下题目，我们可以得到以下的结论： (1)每一组数之和必须等于n； (2)每一组数的个数是不固定的； (3)等式中后一个数的大小必定大于或等于前一个数，因为这样做的目的有两个：一是能够避免等式的重复，例如 n=2 2=1+1 n=3 3=1+2 3=1+1+1 3=2+1 ( 可以看出为与 1+2 是同一种拆分，因此该式子不能算 ) 另一个目的是可以减少不必要的搜索，提高程序效率。 我们可以将待拆分的数对应路径图中的路口，将可拆分的数对应分叉的编号，这样对于 每个路口而言，它所拥有的分叉号是变化的，规律是：分叉的起始值取决于前一次所取数， 分叉的终止值取决于该路口数的中值。 2.3算法设计 在进行算法设计时我们必须要注意两点： 一是本问题需要解决如何记录某一路径中可取数的问题，为了解决这一问题，本程序加入了一个新的数组b，用来记录每一步所取的数。 二是当某一条路走完以后，我们必须回到某一个路口，而路口的值始终保持原来的数，因此在递归调用中我们所使用的实际参数应是独立的。本例中使用的是形式参数m，实际参数是a [ k ]，这样无论在某一级中a[k]的值怎样变化，m 的值是始终不变的。 2.4算法实现 #include #include void splitN(int n,int m);//n是需要拆分的数，m是拆分的进度。 int x[1024]={0},total=0 ;//total用于计数拆分的方法数，x[]用于存储解 int main() { int n ; printf("please input the natural number n:"); scanf("%d",&n); splitN(n,1); printf("There are %d ways to split natural number %d.\n",total,n); system("PAUSE"); return 0 ; } void splitN(int n,int m) {//n是需要拆分的数，m是拆分的进度。 int rest,i,j; for(i=1;i<=n;i++) {//从1开始尝试拆分。 if(i>=x[m-1]) {//拆分的数大于或等于前一个从而保证不重复 x[m]=i ;//将这个数计入结果中。 rest=n-i ;//剩下的数是n-i，如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。 if(rest==0&&m>1) { total++; printf("%d\t",total); for(j=1;j { printf("%d+",x[j]); } printf("%d\n",x[m]); } else { splitN(rest,m+1);//否则将剩下的数进行进度为m+1拆分。 } x[m]=0;//取消本次结果，进行下一次拆分。环境恢复，即回溯} } } 2.5结果分析 参考文献 [1] 张子阳．.NET之美．第一版．机械工业出版社．2014 [2] Mark Michaelis．C#本质论．第四版．人民邮电出版社．2014 [3] MoreWindows．白话经典算法之七大排序．第二版 [4] 王晓东．计算机算法设计与分析．第四版．电子工业出版社．2013 课程设计报告 2015～2016学年第一学期 操作系统综合实践课程设计 实习类别课程设计 学生姓名李旋 专业软件工程 学号130521105 指导教师崔广才、祝勇 学院计算机科学技术学院 二〇一六年一月 - 1 - - 2 - 一、概述 一个目录文件是由目录项组成的。每个目录项包含16B，一个辅存磁盘块(512B)包含32个目录项。在目录项中，第1、2字节为相应文件的外存i节点号，是该文件的内部标识；后14B为文件名，是该文件的外部标识。所以，文件目录项记录了文件内、外部标识的对照关系。根据文件名可以找到辅存i节点号，由此便得到该文件的所有者、存取权、文件数据的地址健在等信息。UNIX 的存储介质以512B为单位划分为块，从0开始直到最大容量并顺序加以编号就成了一个文件卷，也叫文件系统。UNIX中的文件系统磁盘存储区分配图如下： 本次课程设计是要实现一个简单的模拟Linux文件系统。我们在内存中开辟一个虚拟磁盘空间(20MB)作为文件存储器，并将该虚拟文件系统保存到磁盘上(以一个文件的形式)，以便下次可以再将它恢复到内存的虚拟磁盘空间中。文件存储空间的管理可采用位示图方法。 二、设计的基本概念和原理 2.1 设计任务 多用户、多级目录结构文件系统的设计与实现。可以实现下列几条命令login 用户登录 logout 退出当前用户 dir 列文件目录 creat 创建文件 delete 删除文件 open 打开文件 close 关闭文件 - 3 - read 读文件 write 写文件 mkdir 创建目录 ch 改变文件目录 rd 删除目录树 format 格式化文件系统 Exit 退出文件系统 2.2设计要求 1) 多用户：usr1,usr2,usr3,……,usr8 (1-8个用户) 2) 多级目录：可有多级子目录； 3) 具有login (用户登录)4) 系统初始化（建文件卷、提供登录模块） 5) 文件的创建：create (用命令行来实现)6) 文件的打开：open 7) 文件的读：read8) 文件的写：write 9) 文件关闭：close10) 删除文件：delete 11) 创建目录（建立子目录）：mkdir12) 改变当前目录：cd 13) 列出文件目录：dir14) 退出：logout 新增加的功能： 15) 删除目录树：rd 16) 格式化文件系统：format 2.3算法的总体思想 - 4 - 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 微机课程设计报告 目录 一、需求分析 1、系统设计的意义 (3) 2、设计内容 (3) 3、设计目的 (3) 4、设计要求 (3) 5、系统功能 (4) 二、总体设计 1、交通灯工作过程 (4) 三、设计仿真图、设计流程图 1、系统仿真图 (5) 2、流程图 (6) 3、8253、8255A结构及功能 (8) 四、系统程序分析 (10) 五、总结与体会 (13) 六、参考文献 (13) 一、需求分析 1系统设计的意义： 随着社会经济的发展，城市问题越来越引起人们的关注。人、车、路三者关系的协调，已成为交通管理部门需要解决的重要问题之一。城市交通控制系统是用于城市交通数据检测、交通信号灯控制与交通疏通的计算机综合管理系统，它是现代城市交通监控指挥系统中最重要的组成部分。 随着城市机动车量的不断增加，组多大城市如北京、上海、南京等出现了交通超负荷运行的情况，因此，自80年代后期，这些城市纷纷修建城市高速通道，在高速道路建设完成的初期，它们也曾有效地改善了交通状况。然而，随着交通量的快速增长和缺乏对高速道路的系统研究和控制，高速道路没有充分发挥出预期的作用。而城市高速道路在构造上的特点，也决定了城市高速道路的交通状况必然受高速道路与普通道路耦合处交通状况的制约。所以，如何采用合适的控制方法，最大限度利用好耗费巨资修建的城市高速通道，缓解主干道与匝道、城市同周边地区的交通拥堵状况，越来越成为交通运输管理和城市规划部门亟待解决的主要问题。 十字路口车辆穿梭，行人熙攘，车行车道，人行人道，有条不紊。那么靠什么来实现这井然秩序呢？靠的就是交通信号灯的自动指挥系统。交通灯的控制方式很多，本系统采用可编程并行I/O接口芯片8255A为中心器件来设计交通灯控制器，实现本系统的各种功能。同时，本系统实用性强，操作简单。 2、设计内容 采用8255A设计交通灯控制的接口方案，根据设计的方案搭建电路，画出程序流程图，并编写程序进行调试 3、设计目的 综合运用《微机原理与应用》课程知识，利用集成电路设计实现一些中小规模电子电路或者完成一定功能的程序，以复习巩固课堂所学的理论知识，提高程序设计能力及实现系统、绘制系统电路图的能力，为实际应用奠定一定的基础。针对此次课程设计主要是运用本课程的理论知识进行交通灯控制分析及设计，掌握8255A方式0的使用与编程方法，通从而复习巩固了课堂所学的理论知识，提高了对所学知识的综合应用能力。 4、设计要求： （1）、分别用C语言和汇编语言编程完成硬件接口功能设计； （2）、硬件电路基于80x86微机接口； 题目1 连续动态内存管理模拟实现 1.1 题目的主要研究内容及预期达到的目标 （1）针对操作系统中内存管理相关理论进行设计，编写程序并进行测试，该程序管理一块虚拟内存。重点分析三种连续动态内存分配算法，即首次适应算法、循环首次适应算法和最佳适应算法。 （2）实现内存分配和回收功能。 1.2 题目研究的工作基础或实验条件 （1）硬件环境：PC机 （2）软件环境：Windows XP，Visual C++ 6.0 1.3 设计思想 首次适应算法的实现：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。为适应这种算法，空闲分区表中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高址空间保留大的空闲区。 循环首次适应算法的实现：在分配内存空间时，不再每次从表头开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。 最佳适应算法的实现：从全部空闲区中找到能满足作业要求的、且最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表中的空闲分区要按从小到大进行排序，从表头开始查找第一个满足要求的自由分配。 1.4 流程图 内存分配流程图，如图1-1所示。 图1-1 内存分配流程图内存回收流程图，如1-2所示。 图1-2 内存回收流程图 1.5 主要程序代码 （1）分配内存 void allocate(char z,float l) { int i,k; float ad; k=-1; for(i=0;i 、 北京理工大学珠海学院 课程设计任务书 2010 ～2011 学年第 2学期 学生姓名：林泽佳专业班级：08自动化1班指导教师：钟秋海工作部门：信息学院一、课程设计题目 ： 《控制系统建模、分析、设计和仿真》 本课程设计共列出10个同等难度的设计题目，编号为：[0号题]、[1号题]、[2号题]、[3号题]、[4号题]、[5号题]、[6号题]、[7号题]、[8号题]、[9号题]。 学生必须选择与学号尾数相同的题目完成课程设计。例如，学号为8xxxxxxxxx2的学生必须选做[2号题]。 二、课程设计内容 （一）《控制系统建模、分析、设计和仿真》课题设计内容| ！ " [2 有波纹控制器Dy(z)和一单位速度信号输入时的最少拍无波纹控制器Dw(z)。具体要求见（二）。 （二）《控制系统建模、分析、设计和仿真》课题设计要求及评分标准【共100分】 , 1、求被控对象传递函数G(s)的MATLAB描述。（2分） 2、求被控对象脉冲传递函数G(z)。（4分） 3、转换G(z)为零极点增益模型并按z-1形式排列。（2分） 4、确定误差脉冲传递函数Ge(z)形式,满足单位加速度信号输入时闭环稳态误差为零和实际 闭环系统稳定的要求。（6分） 5、确定闭环脉冲传递函数Gc(z)形式，满足控制器Dy(z)可实现、最少拍和实际闭环系统稳 定的要求。（8分） 6、根据4、5、列写方程组，求解Gc(z)和Ge(z)中的待定系数并最终求解Gc(z)和Ge(z) 。 （12分） 7、求针对单位加速度信号输入的最少拍有波纹控制器Dy(z)并说明Dy(z)的可实现性。 （3分） ！ 8、用程序仿真方法分析加速度信号输入时闭环系统动态性能和稳态性能。（7分） 9、用图形仿真方法(Simulink)分析单位加速度信号输入时闭环系统动态性能和稳态性能。 （8分） 10、确定误差脉冲传递函数Ge(z)形式,满足单位速度信号输入时闭环稳态误差为零和实际 闭环系统稳定的要求。（6分） 11、确定闭环脉冲传递函数Gc(z)形式，满足控制器Dw(z)可实现、无波纹、最少拍和实际 闭环系统稳定的要求。（8分） 12、根据10、11、列写方程组，求解Gc(z)和Ge(z)中的待定系数并最终求解Gc(z)和Ge(z) 。 （12分） 13、求针对单位速度信号输入的最少拍无波纹控制器Dw(z)并说明Dw(z)的可实现性。（3分） 14、用程序仿真方法分析单位速度信号输入时闭环系统动态性能和稳态性能。（7分） 15、用图形仿真方法(Simulink)分析单位速度信号输入时闭环系统动态性能和稳态性能。 & （8分） 16、根据8、9、14、15、的分析，说明有波纹和无波纹的差别和物理意义。（4分） 三、进度安排 6月13至6月14：下达课程设计任务书；复习控制理论和计算机仿真知识，收集资料、熟悉仿真工具；确定设计方案和步骤。 6月14至6月16：编程练习，程序设计；仿真调试，图形仿真参数整定；总结整理设计、 仿真结果，撰写课程设计说明书。 6月16至6月17：完成程序仿真调试和图形仿真调试；完成课程设计说明书；课程设计答 辩总结。 [ 四、基本要求 操作系统课程设计报告 东莞理工学院 操作系统课程设计报告 学院：计算机学院 专业班级： 13软件工程1班 提交时间： 2015/9/14 指导教师评阅意见： . 项目名称：进程与线程管理功能 一、设计目的 用语言来模拟进程和线程管理系统，加深对进程和线程的理解，掌握对进程和线程各种状态和管理的算法原理。 二、环境条件 系统： WindowsXP、VMWare、Ubuntu Linux 语言：C/C++ 开发工具：gcc/g++、Visual C++ 6.0 三、设计内容 1. 项目背景 计算机的硬件资源有限，为了提高内存的利用率和系统的吞吐量，就要根据某种算法来管理进程和线程的状态从而达到目的。 进程与线程管理功能完成基于优先级的抢占式线程调度功能，完成进程虚拟内存管理功能。 进程与线程管理功能 基本要求：完成基于优先级的抢占式线程调度功能，完成进程虚拟内存管理功能。 提高要求：（增加1项就予以加分） (1) 实现多种线程调度算法； (2)通过“公共信箱”进行通信的机制，规定每一封信的大小为128字节，实现两个用户进程之间通过这个“公共信箱”进行通信。 (3) 实现多用户进程并发的虚拟内存管理功能。 (4) 实现用户进程间通信功能，并用生产者/消费者问题测试进程间通信功能的正确性。 (5) 实现改进型Clock页面置换算法。 (6) 实现Cache功能，采用FIFO替换算法。 2. 扩展内容 实现多种线程调度算法:时间片轮转调度算法 四、人员分工 优先级调度算法：钟德新，莫友芝 时间片轮转调度算法：张德华，袁马龙 设计报告由小组队员共同完成。小组成员设计的代码分工如下：钟德新编写的代码：void Prinft(){ PCB *p; system("cls");//清屏 p=run; //运行队列 if(p!=NULL) { p->next=NULL; } cout<<"当前正在运行的进程："< 上海电力学院 计算机操作系统原理 课程设计报告 题目名称：编写程序模拟虚拟存储器管理 姓名：杜志豪.学号： 班级： 2012053班 . 同组姓名：孙嘉轶 课程设计时间：—— 评语： 成绩： 目录 一、设计内容及要求 (4) 1. 1 设计题目 (4) 1．2 使用算法分析： (4) 1． FIFO算法（先进先出淘汰算法） (4) 1． LRU算法（最久未使用淘汰算法） (5) 1. OPT算法（最佳淘汰算法） (5) 分工情况 (5) 二、详细设计 (6) 原理概述 (6) 主要数据结构(主要代码) (6) 算法流程图 (9) 主流程图 (9) Optimal算法流程图 (10) FIFO算法流程图 (10) LRU算法流程图 (11) ．1源程序文件名 (11) . 2执行文件名 (11) 三、实验结果与分析 (11) Optimal页面置换算法结果与分析 (11) FIFO页面置换算法结果与分析 (16) LRU页面置换算法结果与分析 (20) 四、设计创新点 (24) 五、设计与总结 (27) 六、代码附录 (27) 课程设计题目 一、设计内容及要求 编写程序模拟虚拟存储器管理。假设以M页的进程分配了N 块内存（N 算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.) 目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18) P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。 计算机网络课程设计报告 姓名：李逍逍 班级：08计11 学号：08261012 一．课程设计的题目、目的及要求 (2) 二．课程设计的内容（分析和设计） (3) 三．绘制拓扑结构图 (3) 四．详细设计步骤 (5) 五．路由器或交换机配置的代码 (6) 六．显示最终的结果 (8) 七．课程设计总结 (9) 一．课程设计的题目、目的及要求 课程设计题目：组建小区局域网 课程设计目的： 更深了解路由器，交换机，PC机之间的配置与应用，熟练掌握一些简单的的网络应用和连接，熟练掌握路由器和交换机的基本配置；掌握DHCP、ACL、VLAN、和NET协议和相应的技术；提高对实际网络问题的分析和解决能力。该设计需要划分为四个子网层面的小区性的网络通讯。采用软件cisco，可以更好的实现各种不同网络设备互相配合与联系，以达到最佳的局域网通讯效果。 课程设计要求： 要求能根据实际问题绘制拓扑结构图，拓扑结构图可以是树形、星形、网状形、环状形及混合形结构的之一，清晰的描述接口，进行路由器或交换机的代码配置实现，并且每个方案的需有以下几部分的内容： 1、需求特点描述； 2、设计原则； 3、解决方案设计，其中必须包含： （1）设备选型； （2）综合布线设计； （3）拓扑图； （4）IP地址规划； （5）子网划分； （6）路由协议的选择； （7）路由器配置。 组建小区局域网的总体要求： 运用自己对局域网组网技术的理解，设计小区组网方案，使得一个具有200个住户节点的智能化小区能够进行网络通讯，且将整个小区可划分为四个区域：1．网络中心区：以物业管理中心及监控中心为主的核心交换设备和服务器群；2．远程网络接入区：包括外部网络接入口的路由器设备和网络安全设备；3．园区网络区：包括从网络中心到社区服务设施的骨干交换设备； 4．家庭网络区：包括从网络中心到楼宇中的骨干交换设备，并为各住户单元提供网络接入端口，是整个小区网络系统的最基本单元。 成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日 课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分 东莞理工学院 操作系统课程设计报告学院：计算机学院 专业班级：13软件工程1班 提交时间：2015/9/14 指导教师评阅意见： . 项目名称：进程与线程管理功能 一、设计目的 用语言来模拟进程和线程管理系统，加深对进程和线程的理解，掌握对进程和线程各种状态和管理的算法原理。 二、环境条件 系统：WindowsXP、VMWare、Ubuntu Linux 语言：C/C++ 开发工具：gcc/g++、Visual C++ 6.0 三、设计内容 1. 项目背景 计算机的硬件资源有限，为了提高内存的利用率和系统的吞吐量，就要根据某种算法来管理进程和线程的状态从而达到目的。 进程与线程管理功能完成基于优先级的抢占式线程调度功能，完成进程虚拟内存管理功能。 进程与线程管理功能 基本要求：完成基于优先级的抢占式线程调度功能，完成进程虚拟内存管理功能。 提高要求：（增加1项就予以加分） (1) 实现多种线程调度算法； (2)通过“公共信箱”进行通信的机制，规定每一封信的大小为128字节，实现两个用户进程之间通过这个“公共信箱”进行通信。 (3) 实现多用户进程并发的虚拟内存管理功能。 (4) 实现用户进程间通信功能，并用生产者/消费者问题测试进程间通信功能的正确性。 (5) 实现改进型Clock页面置换算法。 (6) 实现Cache功能，采用FIFO替换算法。 2. 扩展内容 实现多种线程调度算法:时间片轮转调度算法 四、人员分工 优先级调度算法：钟德新，莫友芝 时间片轮转调度算法：张德华，袁马龙 设计报告由小组队员共同完成。小组成员设计的代码分工如下： 钟德新编写的代码：void Prinft(){ PCB *p; system("cls");//清屏 p=run; //运行队列 if(p!=NULL) { p->next=NULL; } cout<<"当前正在运行的进程："< 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.流程图的绘制 2. 演讲稿的制作 专业软件工程 班级软件1111 姓名王鑫 成绩 _________________ 指导教师 __ ______ 2012年元月2日至2012年元月6日 课程设计任务书 学生：王鑫专业班级：软件1111 指导教师：黄启荃工作单位：理工大学华夏学院 设计题目：程序流程图的绘制 初始条件： 已掌握Office 2003办公自动化软件的应用 要求完成的主要任务： （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 主要任务： 任务描述：已知某班50个学生考试了4门课程，要求绘制一个程序流程图，实现下列功能：1.求每个人的平均成绩； 2．将平均成绩进行降序排序，并将学号与平均成绩按降序输出完成： 1 完成整个规定任务的设计及调试，得出正确结果，并经教师检查及答辩； 2. 写出规的课程设计说明书； 3. 课程设计结束后交设计说明书等文档和设计容。 4. 从元月3日起，学生每天至少要到设计教室半天以上； 设计报告撰写格式要求： 设计报告的主要容是详细写出在设计过程中所用到的主要技术或方法； 课程设计报告按国际通用格式书写， 具体格式要求请见资料：“课程设计说明书的书写容与格式” 时间安排： 第一天：学生先在实验室集中，由指导教师介绍实训目的、布置任务后选题； 第二天-第四天：学生在实验室完成设计，经教师检查并回答提问，确认设计完成； 第五天：教师在计算机上先检查设计报告、学生修改后打印提交 指导教师签字： 2011年12月26日 系主任签字： 2011年12月29日 东莞理工学院 操作系统课程设计报告 学院：计算机学院 专业班级：13软件工程1班 提交时间：2015/9/14 指导教师评阅意见： . 项目名称：进程与线程管理功能 一、设计目的 用语言来模拟进程和线程管理系统，加深对进程和线程的理解，掌握对进程和线程各种状态和管理的算法原理。 二、环境条件 系统：WindowsXP、VMWare、Ubuntu Linux 语言：C/C++ 开发工具：gcc/g++、Visual C++ 6.0 三、设计内容 1. 项目背景 计算机的硬件资源有限，为了提高内存的利用率和系统的吞吐量，就要根据某种算法来管理进程和线程的状态从而达到目的。 进程与线程管理功能完成基于优先级的抢占式线程调度功能，完成进程虚拟内存管理功能。 进程与线程管理功能 基本要求：完成基于优先级的抢占式线程调度功能，完成进程虚拟内存管理功能。 提高要求：（增加1项就予以加分） (1) 实现多种线程调度算法； (2)通过“公共信箱”进行通信的机制，规定每一封信的大小为128字节，实现两个用户进程之间通过这个“公共信箱”进行通信。 (3) 实现多用户进程并发的虚拟内存管理功能。 (4) 实现用户进程间通信功能，并用生产者/消费者问题测试进程间通信功能的正确性。 (5) 实现改进型Clock页面置换算法。 (6) 实现Cache功能，采用FIFO替换算法。 2. 扩展内容 实现多种线程调度算法:时间片轮转调度算法 四、人员分工 优先级调度算法：钟德新，莫友芝 时间片轮转调度算法：张德华，袁马龙 设计报告由小组队员共同完成。小组成员设计的代码分工如下：钟德新编写的代码：void Prinft(){ PCB *p; system("cls");//清屏 p=run; //运行队列 if(p!=NULL) { p->next=NULL; } cout<<"当前正在运行的进程："< 南通大学计算机科学与技术学院操作系统课程设计报告 专业： 学生姓名： 学号： 时间： 操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。 设计流程图 主流程图 开始的图形界面 处理机管理存储器管理缺页调度 先来先服务时 间 片 轮 转 首 次 适 应 法 最 佳 适 应 法 先 进 先 出 L R U 算 法 A.处理机调度 1)先来先服务FCFS N Y 先来先服务算法流程 开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中的下一位移到首位 计算并打印进程的完成时刻、周转时间、带权周转时间 其中：周转时间 = 完成时间 - 到达时间 带权周转时间=周转时间/服务时间 更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空 结束 2)时间片轮转法 开始 输入进程总数 指针所指的进程是 否结束 输入各进程信息 输出为就绪状态的进程的信息 更改正在运行的进程的已运行时间 跳过已结束的程序 结束 N 指向下一个进程 Y 如果存在下一个进程的话 Y N 输出此时为就绪状态的进程的信息 时间片轮转算法流程图 B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图 申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于延链查找下 一个空闲区 到链尾 了？ 作业等待 返回是 否 登记已分配表 返回分配给进程的内存首地址 开始 操作系统课程设计实验报告 实验名称：进程控制 姓名/学号： 一、实验目的 学习、理解和掌握Linux与windows的进行控制系统调用的功能，熟悉主要的几个系统调用命令的格式和如何利用系统调用命令进行编程。通过学习，理解如何创建一个进程、改变进程执行的程序、进程和线程终止以及父子进程的同步等，从而提高对进程和线程控制系统调用的编程能力。 二、实验内容 设计并实现Unix的“time”命令。“mytime”命令通过命令行参数接受要运行的程序，创建一个独立的进程来运行该程序，并记录程序运行的时间。 三、实验环境 CPU: Inter ×2 2.10GHz RAM: 3.00GB Windows 7 旗舰版 Linux Ubuntu 10.04 编译: VS2010 四、程序设计与实现 4.1进程控制系统的调用 4.1.1 windows进程控制调用程序中使用的数据结构及主要符号说明 SYSTEMTIME starttime,endtime; //进程开始时间和结束时间 PROCESS_INFORMATION pi //该结构返回有关新进程及 //其主线程的信息 STARTUPINFO si //该结构用于指定新进程的主窗口特性4.1.2 linux进程控制调用程序中使用的数据结构及主要符号说明 struct timeval starttime,endtime //进程开始时间和结束时间 pid_t pid //进程标志符 4.2 程序流程图 图1 windows进程控制调用图2 linux进程控制调用程序运行流程图程序运行流程图 五、实验结果和分析 5.1 windows实验结果和分析 《计算机组成原理课程设计》任务书 一、实验目的： (1)通过微程序的编制、装入、执行，验证微程序控制器控制的工作方法。观察微程 序的运行过程，为进行简单模型计算机实验做准备。 (2)通过实验分析简单模型机结构，了解计算机工作原理。掌握计算机微程序控制器 的控制方法，掌握计算机指令执行过程。 (3)深入了解计算机各种指令的执行过程，以及控制器的组成，指令系统微程序设计 的具体知识，通过在简单模型计算机基础上设计新的5条机器指令，以提高学生 对计算机机器指令理解，锻炼学生自己动手设计模型计算机机器指令的能力。二、实验说明： 要进行这项大型实验，必须清楚地懂得： （1）模型机的功能部件及其连接关系； （2）模型机每个功能部件的功能与具体组成； （3）模型机支持的指令格式； （4）模型机的微指令格式； （5）已实现的典型指令的执行实例，即相应的微指令与其执行次序的安排与衔接；三、实验内容： （1）完成总线数据传输控制实验。 （2）完成简单模型计算机实验。 （3）完成机器指令设计实验。可选择其中一项任务 任务之一： 在模型机上实现以下功能： a)每次输入2个数，将这2 个数相加，其和依次存入存储器地址为20H开始的 3个单元，并送LED显示输出，以上操作循环执行3次后停机。 b)其中：设R0为循环计数器、R1为累加器、R2为变址寄存器，Ri就是R2 c)INPUT DEVICE和OUTPUT DEVICE的端口地址皆为00H。 任务之二： 在模型机上实现以下功能： 对输入开关上的数据和存储器某一单元中的数据进行加法操作，结果累计在存储器某一单元中，当累计值大于256时转而进行减法操作，即把此存储器单元中的值减去输入开关上的数据，结果送同一存储器单元，当操作结果小于0时再转而进行加法操作，使用显示灯上出现数据连续加，然后连续减，减到0时再连续加。这样连续加民、减直到拔动CLR结束程序运行为止。 任务之三： 1、分析手动装入程序代码时，为什么必须要在微地址显示灯显示“”时，才从开 关上置入指令代码？同时，在手动校验时，为什么只有当微地址显示灯显示“”时，发光管上显示的内容才是内存的数据？ 2、若将OUT指令的操作码改为0101，则微程序必须做什么样的修改？ 3、在微程序流程图上，最多还可以添加几条机器指令？ 四、实验要求： （1）根据实验内容完成各指导书中的实验数据的结果、分析和总结。 （2）要求自行设计相关指令微程序；（务必利用非上机时间设计好微程序） （3）设计测试程序、实验数据并上机调试。 计算机操作系统课程设计 班级：计091-1 姓名： 学号： 使用语言：C++ 指导老师： 学院： 一、系统要求 1、实验目的 通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能及内部实现。 2、实验内容 为linux系统设计一个简单的二级文件系统。要求做到以下几点： （1）可以实现下列几条命令（至少4条）； login 用户登陆 dir 列文件目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件 （2）列目录时要列出文件名、物理地址、保护码和文件长度； （3）源文件可以进行读写保护。 二、系统分析 1、设计思想 本文件为二级文件系统，即要实现对文件的增删改查，同时又具备登陆系统、注册用户的功能，各个用户之间的文件系统互不干扰。 本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。 系统采用结构体来存储用户、文件目录、文件数据内容： 0 48*5 48*5+44*50 48*5+44*50+264*200 每个分区都是由结构体组成，每个个去的结构体的个数由格式化系统是决定。 整个系统的编码构成主要分为： Allstruct.h 定义了每个分区的结构体； Mysys.h 声明了对系统操作的各种方法；Myuserfile.h 声明了对文件操作的各种方法； Mymain.cpp 整个系统的主函数，操作入口； Mysys.cpp 包含了mysys.h，实现了操作系统的各种方法；Myuserfile.cpp 包含了myuserfile.h，实现了操作文件的各种方法； 2、主要数据结构 Allstruct.h文件的内容： struct s_user //用户区结构体 { long isuse; //是否使用 char name[20]; //用户名 char psd[20]; //密码 long address; //目录地址 };操作系统课程设计
《计算机算法设计与分析》习题及答案
中南大学微机课程设计报告交通灯课案
操作系统课程设计报告书
计算机仿真课程设计报告
操作系统课程设计报告
操作系统课程设计报告
计算机算法设计与分析
计算机网络课程设计报告
计算机算法设计与分析课程设计.
操作系统课程设计报告
计算机算法设计与分析期末考试复习题
计算机课程设计报告书
操作系统课程设计报告
操作系统(一个小型操作系统的设计与实现)课程设计
操作系统课程设计报告
计算机课程设计报告
计算机操作系统课程设计
相关主题
文本预览