算法课程设计
<<算法与程序设计>>课程作业
班级：计本08-1班
学号：3081817106
姓名：詹萍
简单算法
符号三角形问题：这个问题用的是回溯法解决的，符号三角形要求在符号三角形的第1行有n个由“+”和“-”组成的符号，以后每行符号比上行少1个，2个同号下面是“+”，2个异号下面是“-”。计算有多少个不同的符号三角形，使其所含“+”和“-”的个数相同。
解题思路：
1、针对所给问题定义解空间，该问题的解空间为n元组x1,x2,x3...xn，其中xi ∈S，S={0，1}，其中0代表“+”， 1代表“-”；
2、确定易于搜索的解空间结构，例如子集树，排列树，该问题是子集树；
3、以深度优先原则搜索解空间树，并利用剪枝函数避免无效搜索，这里的约束函数应该为：在符号三角形的第一行的前i个符号x1...xi确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x(i+1)的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x1...x(i+1)所相应的符号三角形。最终由x1...xn所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束；用0和1代替+和-，执行异或操作推出下一行对应符号，当所有符号总数为奇数时无解，当某种符号超过总数一半时无解。
4.由于回溯法是对解空间的深度优先搜索，不断改变第一行每个符号，搜索符合条件的解，因此可以使用递归回溯。
#include
using namespace std;
class Triangle
{friend int Computer(int);//定义友元函数
private:
void Backtrack(int t); //t，第一行第t个符号
int n, //第1行符号的个数
half, //每个三角形总符号数的一半
count, // 统计减号的个数
**p; //指向三角形的二维指针
long sum; }; //统计符合条件的的三角形的个数
void Triangle::Backtrack(int t)//回溯法
{int i,j,k,s,f;
if((count>half)||(t * (t-1)/2 - count > half))
return; //如果加号或减号的个数大于符号三角形中总符号数的一半则退出函数if(t<=n) //回溯条件直到n
for(i=0; i<2; i++)
{ p[1][t] = i; //第一行第t个符号
count += i; //“-”号统计
for(j=2; j<=t; j++) //当第一行符号>=2时，可以运算出下面行的某些符号
{ p[j][t-j+1] = p[j-1][t-j+1]^p[j-1][t-j+2]; //通过异或运算下行符号
count += p[j][t-j+1];}
if(t>=n)
{ //输出符合条件的三角形
f=0;
for(j=1; j<=t;j++)
for(k=1; k<=t-j+1; k++)
f+=p[j][k];
if(f==half)
{ //如果减号是总符号数的一半则输出并将sum加1
cout<<"第"<<++sum<<"个三角形"<<'\n';
for(j=1; j<=t; j++)
{for(s=1; s for(k=1; k<=t-j+1; k++) { if(p[j][k] == 1) cout<<"- ";//3个空格 else cout<<"+ ";//3个空格} cout<<'\n';} cout<<'\n';}} Backtrack(t+1); //回溯 for(j=2; j<=t; j++) count -= p[j][t-j+1]; count -=i;} } int Computer(int n) //友元函数调用Triangle类的成员函数{ int i,j; Triangle X; X.n = n; X.count = 0; X.sum = 0; X.half = n * (n+1) / 2; if(X.half % 2 == 1) return 0; //如果是一个三角形符号的总数是奇数则不符合条件，返回0 X.half = X.half / 2; int **p = new int * [n+1]; //分配新行 for(i=0; i<=n; i++) p[i] = new int [n+1];//分配新列 for(i=0; i<=n; i++) for(j=0; j<=n; j++) p[i][j] = 0;//给p所指向的二维数组赋值为0 X.p = p; X.Backtrack(1); return X.sum; } void main() { int i, n; cout<<"请输入第一行的符号个数："; cin>>i; n = Computer(i); cout<<"***************************"<<'\n'; cout<<"共有"< 程序的输入是第一行的符号个数，输出是符合符号三角形的每一种三角形情况，符合符号三角形的总个数。 复杂算法 作业调度问题：这个问题用的是贪心算法，作业调度问题要求设计出一个方案使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。具体要求在设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。 问题分析： 这个问题是一个NP完全问题，到目前为止还没有一个有效的解法。对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 当n <= m 时，只要将机器i 的[0,ti]时间区间分配给作业i即可。当n > m 时，首先将n 个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。 将作业处理所需时间按照从小到大排序，分给每台机器后把剩下的作业分给空闲的机器，即把耗时最多的作业分配给先空闲的机器，这样就充分利用了每台机器的处理能力，显然有利于均衡。总而言之，让最空闲的机器做最繁重的任务。 #include #include"iostream.h" #include "conio.h" #define maxWork 100 //最大工作数为100 #define maxMachine 100 //最大机器数为100 class machineWork { public: machineWork(void); ~machineWork(void); void SetMachine( int machine ); void SetWorks( double times[] , int works ); bool Arrange(); void Sort(int timeId[]); void Print(); private: double timesUnsorted[maxWork]; int graph[maxMachine][maxWork]; double machinesTime[maxMachine]; int machines; int works;}; machineWork::machineWork(void){} machineWork::~machineWork(void){} void machineWork::Sort( int timeId[] ) {for( int i = 0 ; i < works ; i++ ) timeId[i] = i; for( i = 0 ; i < works - 1 ; i++ ) {double min = timesUnsorted[ timeId[i] ]; int p = i; for( int j = i + 1 ; j < works ; j++ ) {if( this->timesUnsorted[ timeId[j] ] > min ) {min = this->timesUnsorted[ timeId[j] ]; p = j;} } int t = timeId[i]; timeId[i] = timeId[p]; timeId[p] = t; }} void machineWork::SetMachine( int machines ) {this->machines = machines;} void machineWork::SetWorks( double times[] , int works ) {this->works = works; for( int i = 0 ; i < works ; i++ ) timesUnsorted[i] = times[i];} bool machineWork::Arrange() { int timeId[maxWork]; Sort( timeId ); //某一工作安排后，对机器的工作时间进行排序，index[i]保存机器编号 int index[maxMachine]; //graph[i][0]表示机器i中已经安排了几项任务 for( int i = 0 ; i < machines ; i++ ) graph[i][0] = 0; //机器已经安排的工作时间 for( i = 0 ; i < works ; i++ ) machinesTime[ i ] = 0.0; //index[0]所指向的graph[ index[0] ][0] 的值是最小的 for( i = 0 ; i < machines ; i++ ) index[i] = i; for( i = 0 ; i < works ; i++ ) //给i 号作业分配机器 { graph[ index[0] ][0]++; //把作业分配给index[0] 所指向的机器graph[ index[0] ][ graph[index[0]][0] ] = timeId[i]; machinesTime[ index[0] ] += timesUnsorted[ timeId[i] ]; int j = 0; //对机器的已经安排的工作时间进行排序 while(j< machines-1 && machinesTime[ index[j] ] > machinesTime[ index[j+1] ]) {int t = index[j]; index[j] = index[j+1]; index[j+1] = t; j++;} } return true;} void machineWork::Print() {for( int i = 0 ; i < works ; i++ ) printf( "工作%d 所需要的时间%5.f\n" , i , timesUnsorted[i] ); printf( "\n" ); for( i = 0 ; i < machines && i < works ; i++ ) {printf( "机器%d 工作总时间%.f = " , i , machinesTime[i] ); printf( "%.f " , timesUnsorted[ graph[i][1] ] ); for( int j = 2 ; j <= graph[i][0] ; j++ ) printf( "+ %.f " , timesUnsorted[ graph[i][j] ] ); printf( "\n" );} printf( "\n" ); for( i = 0 ; i < machines ; i++ ) {printf( "机器%d 上的工作安排" , i ); for( int j = 1 ; j <= graph[i][0] ; j++ ) printf( "%d " , graph[i][j] ); printf( "\n" );}} int main(int argc, char* argv[]) {int a,b; cout<<"请输入工作数："; cin>>a;cout< double t[maxWork]; for(int i=0;i machineWork w; cout<<"请输入机器数："; cin>>b;cout< w.SetMachine(b); w.SetWorks( t , a ); w.Arrange(); w.Print(); getch(); return 0;} 程序的输入是工作数、每个工作需要的时间和机器数，输出是每个工作需要的时间和每个机器的工作总时间和每个机器上的工作安排。 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 情况。 课程设计报告 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 - 吉林财经大学课程设计报告 课程名称：算法课程设计 设计题目：插棒游戏 所在院系：管理科学与信息工程学院计算机科学与技术 指导教师： 职称：副教授 提交时间： 2017年4月 目录 一、题目描述与设计要求 (1) 1 题目描述与设计要求 (1) 二、问题分析 (1) 1 解空间 (1) 2 解空间结构 (2) 3 剪枝 (2) 4 回溯法的基本思想 (2) 5 回溯法的适用条件 (3) 6 回溯法的空间树 (4) 7 回溯法的基本步骤 (4) 三、算法设计 (5) 1 伪代码 (5) 四、复杂性分析 (6) 1 时间复杂度 (6) 2 空间复杂度该 (6) 五、样本测试、分析与总结 (6) 1 样本测试 (6) 2 分析 (7) 2.1、数据类型 (7) 2.2 主要函数思路 (7) 2.3 回溯 (8) 3 总结 (8) 参考文献 (9) 附录 (10) 一、题目描述与设计要求 1 题目描述与设计要求 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本： a.已知空孔的位置，求出消去 13 个插棒的最短步骤，对剩下的插棒的最终位置不限。 b.已知空孔的位置，求出消去 13 个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。 图1 二、问题分析 1 解空间 由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。 例如初始状态时，空孔只有一个，共有15种基本状态。如图2 所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o 互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。 数据结构课程设计设计说明书 内部堆排序算法的实现 学生姓名金少伟 学号1121024029 班级信管1101 成绩 指导教师曹阳 数学与计算机科学学院 2013年3月15日 课程设计任务书 2012—2013学年第二学期 课程设计名称：数据结构课程设计 课程设计题目：内部堆排序算法的实现 完成期限：自2013年3 月4日至2013年3 月15 日共 2 周 设计内容： 堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。 本课程设计中主要完成以下内容： 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下： 1.程序设计界面友好； 2.设计思想阐述清晰； 3.算法流程图正确； 4.软件测试方案合理、有效。指导教师：曹阳教研室负责人：申静 课程设计评阅 摘要 堆排序是直接选择排序法的改进。本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。 关键词：堆排序；C语言；时间复杂度 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第2 学期 课程数据结构与算法 课程设计名称Dijkstra算法的实现 学生姓名张睿辰 学号0804012044 专业班级08计科(2)班 指导教师王昆仑张贯虹 2010 年6月 Dijkstra算法的实现 一、问题分析与任务定义 1、课程设计题目： 1.1题目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径 的Dijkstra算法 1.2 要求：设计合理的数据结构存储图，简单有效的实现Dijkstra算法。 1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短 路径，并显示出来！ 2、原始数据的输入格式： 2.1建图模块：2.1.1数字 2.2.2数字+空格+数字+空格+数字+回车 2.3显示模块：回车 3、实现功能： 3.1 建立有向图 3.2 显示存储的有向图 3.3 显示从顶点到其他各顶点的最短路径 4、测试用例： 4.1正确数据：a）顶点：3；边值信息：0 1 6；0 2 4；1 2 5；2 0 6；0 0 0； b）顶点：0；边值信息：0 0 0； 输出结果：a) v0到v1的最短路径是6，v0到v2的最短路径是4 b) 没有最短路径 4.2错误数据：a) 顶点：a b）顶点：2；边值信息：0 3 6；0 4 4；13 5；0 0 0； c）顶点：3；边值信息：0 1 a； 输出结果：边值错误，请从新输入 5、问题分析： 实现本程序要解决以下几个问题： 5.1如何存储一个有向图。 5.2如何在界面中输出该有向图。 5.3如何定义起始源点。 5.4如何选择出最短路径。 5.5找到的最短路径如何输出。 二、数据结构的选择和概要设计 1、数据结构的选择： 在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的 上海电力学院 计算机操作系统原理 课程设计报告 题目名称：编写程序模拟虚拟存储器管理 姓名：杜志豪.学号： 班级： 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 <<算法与程序设计>>课程作业 班级：计本08-1班 学号：3081817106 姓名：詹萍 简单算法 符号三角形问题：这个问题用的是回溯法解决的，符号三角形要求在符号三角形的第1行有n个由“+”和“-”组成的符号，以后每行符号比上行少1个，2个同号下面是“+”，2个异号下面是“-”。计算有多少个不同的符号三角形，使其所含“+”和“-”的个数相同。 解题思路： 1、针对所给问题定义解空间，该问题的解空间为n元组x1,x2,x3...xn，其中xi ∈S，S={0，1}，其中0代表“+”， 1代表“-”； 2、确定易于搜索的解空间结构，例如子集树，排列树，该问题是子集树； 3、以深度优先原则搜索解空间树，并利用剪枝函数避免无效搜索，这里的约束函数应该为：在符号三角形的第一行的前i个符号x1...xi确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x(i+1)的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x1...x(i+1)所相应的符号三角形。最终由x1...xn所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束；用0和1代替+和-，执行异或操作推出下一行对应符号，当所有符号总数为奇数时无解，当某种符号超过总数一半时无解。 4.由于回溯法是对解空间的深度优先搜索，不断改变第一行每个符号，搜索符合条件的解，因此可以使用递归回溯。 #include 成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日 课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分 算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系 一、运动员比赛日程表 设有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、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。 南通大学计算机科学与技术学院操作系统课程设计报告 专业： 学生姓名： 学号： 时间： 操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。 设计流程图 主流程图 开始的图形界面 处理机管理存储器管理缺页调度 先来先服务时 间 片 轮 转 首 次 适 应 法 最 佳 适 应 法 先 进 先 出 L R U 算 法 A.处理机调度 1)先来先服务FCFS N Y 先来先服务算法流程 开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中的下一位移到首位 计算并打印进程的完成时刻、周转时间、带权周转时间 其中：周转时间 = 完成时间 - 到达时间 带权周转时间=周转时间/服务时间 更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空 结束 2)时间片轮转法 开始 输入进程总数 指针所指的进程是 否结束 输入各进程信息 输出为就绪状态的进程的信息 更改正在运行的进程的已运行时间 跳过已结束的程序 结束 N 指向下一个进程 Y 如果存在下一个进程的话 Y N 输出此时为就绪状态的进程的信息 时间片轮转算法流程图 B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图 申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于延链查找下 一个空闲区 到链尾 了？ 作业等待 返回是 否 登记已分配表 返回分配给进程的内存首地址 开始 课程设计说明书 设计题目：二分法查找 专业：软件工程班级：11-2 设计人：王佳贺 山东科技大学 2013年11 月27日 课程设计任务书 学院：信息科学与工程学院专业：软件工程班级：2011-1 姓名：王佳贺 一、课程设计题目：二分法查找 二、课程设计主要参考资料 （1）《算法分析与设计》（第三版）王晓东电子工业出版社2007 （2） 三、课程设计应解决的主要问题 （1）查询数据 （2） （3） 四、课程设计相关附件（如：图纸、软件等）： （1） （2） 五、任务发出日期：2013-11-21 课程设计完成日期：2013-11-27 指导教师签字：系主任签字： 指导教师对课程设计的评语 成绩： 指导教师签字： 年月日 1二分法详细设计 1.1二分搜索算法 下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？ 如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： X X X X 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (8) 题目2 切割木材 (10) 2.1题目描述 (10) 2.2算法文字描述 (10) 2.3算法程序流程 (11) 2.4算法的程序实现代码 (15) 题目3 设计题 (17) 3.1题目描述 (17) 3.2 输入要求 (17) 3.3输出要求 (17) 3.4样例输入 (17) 3.5样例输出 (17) 3.6测试样例输入 (17) 3.7测试样例输出 (18) 3.8算法实现的文字描述 (18) 3.9算法程序流程 (19) 3.10算法的程序实现代码 (20) 算法分析与设计课程总结 (23) 参考文献 (24) 题目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 计算机操作系统课程设计 班级：计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; //目录地址 }; 操作系统课程设计LRU页面调度算法 学号： 姓名： 学院： 专业： 班级： 指导老师： 日期： 目录 一、实验题目 (1) 二、课程设计的目的 (1) 三、设计容 (1) 四、设计要求 (1) 五、设计思想 (1) 六、主要数据结构及其说明 (2) 七、硬件支持 (3) 八、源程序文件 (3) 九、程序运行结果 (7) 十、实验体会 (8) 一实验题目 LRU页面调度算法 二课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 1.进一步巩固和复习操作系统的基础知识。 2. 培养学生结构化程序、模块化程序设计的方法和能力。 3.提高学生调试程序的技巧和软件设计的能力。 4.提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三设计容 程序应模拟实现LRU算法思想，对n个页面实现模拟调度。 四设计要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 五设计思想 最近最久未使用（LRU）页调度算法是选择最近最久未使用的页面予以淘汰。 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当所要访问的页面在存块中时，就不淘汰页面，否则，淘汰页面中时间最长的，即淘汰最近最久未使用的页面。 操作系统课程设计 一、课程设计题目 实现一个模拟操作系统。 二、课程设计的目的 通过模拟操作系统原理的实现，加深对操作系统工作原理理解，进一步了解操作系统的实现方法，并可练习合作完成系统的团队精神和提高程序设计能力。 三、小组人数 建议3~4人一组共同完成模拟系统的实现。 四、编程语言 建议使用VC、VB、C#、Java等Windows环境下的程序设计语言，以借助这些语言环境来模拟硬件的一些并行工作。 五、课程设计内容 模拟采用多道程序设计方法的单用户操作系统，该操作系统包括进程管理、存储管理、设备管理、文件管理和用户接口四部分。 六、课程设计具体要求和内容 1．文件管理和用户接口 文件管理和用户接口部分实现的主要是单用户的磁盘文件管理部分，包括文件的逻辑结构、物理结构、目录、磁盘分配回收、文件的保护和用户接口的实现。 ⑴文件的逻辑结构 文件的逻辑结构采用流式结构； 文件的内容均采用文本文件； 系统中有两种文件，一种是存放任意字符的文件，一种是可执行文件。可执行文件的内容就是模拟系统内进程的程序体。 文件中要有一种特定命令的“可执行”文件，该文件中的命令有： x=?; 给x赋值一位数 x++; x加1 x--; x减1 !??；第一个？为A,B,C中某个设备，第二个？为一位数，表示使用设备的时间（由于没有实际设备，所以无法知道设备何时工作完成，所以假定一个数，这个数随着系统时间增加而递减，减到0时，认为是设备工作完成）； end. 表示文件结束，同时将结果写入文件out，其中包括文件路径名和x的值。 ⑵磁盘模拟 用一个文件disk1模拟磁盘c，用一个文件disk2模拟磁盘d。两个磁盘一样大小，磁盘的每个盘块64字节，模拟磁盘共有128块。第0、1块存放文件分配表，第2块存放根目录，其余存放子目录和文件。 ⑶目录结构 目录结构采用树型目录结构。 ①目录项内容（8个字节）： 目录名、文件名：3个字节； 扩展名：2个字节（可执行文件扩展名为ex，目录没有扩展名）； 目录、文件属性：1字节（1位标识是文件还是目录，1位标识只读还是非只读，1位是隐藏属性，标识显示还是不显示）； 起始盘块号：1个字节； 文件长度：1字节（目录没有长度）。 . 课程设计说明书 题目：数据结构与算法课程设计 ：学院（系） 专业班级：号：学 学生姓名： 指导教师：教师职称： 起止时间： '. . 课程设计（论文）任务及评语 '. . 目录 第章课程设计目的与要求 _______________________________________________ 11 1.1 课程设计目的 ________________________________________________________ 1 1.2 课程设计的实验环境 __________________________________________________ 1 1.3 课程设计的预备知识 __________________________________________________ 1 1.4 课程设计要求 ________________________________________________________ 1第章课程设计内容 _______________________________________________________ 22 2.1题目的选择 _________________________________________________________ _ 2 2.2 题目的具体实现 ______________________________________________________ 2 2.3 思考题解析 _________________________________________________________ 12 总结： _________________________________________________________ ________ 14 参考文献 _________________________________________________ 错误!未定义书签。 '. . 课程设计目的与要求1第章 课程设计目的1.1 本课程设计是计算机科学与技术专业、软件工程专业的专业技术实践课。 本实践课的主要目的是：使学生学会利用在课堂中学过的理论知识，解决相应的实际问题，深入理解和灵活掌握所学的内容，培养学生理论和实践相结合的能力，培养学生分析问题解决问题的能力。同时，在实验步骤规范化、程序设计 山东理工大学：操作系统课程题目要求 说明：（1）未做特别说明的均参照任务书的要求,每位同学独立完成课程设计。（2）设计中所涉及到的存储结构采用链式，除非题目中有特殊要求；（3）自己所编写的代码不能少于总代码的1/3（输入输出语句不算在内），否则为不合格 1.银行家算法的设计与实现（2人） 要求：（1）设计一个小型的死锁避免系统，在系统中体现银行家算法及安全性算法；（2）用户请求及系统当前的资源分配状态从键盘输入； （3）输出能够判断当前的系统状态是否是安全的？若安全，给出至少一个安全序列；若不安全，给出原因（4）某进程提出一个请求，该请求能够满足，但会使系统进入不安全状态（5）某进程提出一个请求，该请求不能满足 可参考教材上的例题实现 2.基于FCFS和SPF的进程管理系统的设计（2人） 要求：（1）设计一个完整的进程调度系统， 系统中至少包括5个进程；（2）定义PCB；（3）采用链表管理就绪队列；（4）结果要能够显示出进程的调度序列及进入系统的时间、运行时间等必要信息；（5）设计的输入数据要能体现算法的思想 3.基于静态优先权和响应比的进程管理系统的设计（2人） 要求：（1）设计一个完整的进程调度系统，系统中至少包括5个进程；（2）定义PCB，在PCB中定义进程的初始优先权（用整数表示）；（3）采用链表管理就绪队列；（4）结果要能够显示出进程的调度序列及初始优先权、响应比等必要信息（5）设计的输入数据要能体现算法的思想 4.基于多级反馈队列的进程管理系统的设计（2人） 要求：（1）设计三级队列，每一队列至少三个进程；（2）定义PCB（3）为每一队列设置不同的时间片，后一队列通常是前一队列的2倍，依次类推（4）采用链表管理就绪队列；（5）结果要能够显示出进程的调度过程 摘要 分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2 时，只要做一次比较即可排好序；当n = 3时只要做两次比较即可……而当n较大时，问题就不容易那么处理了。要想直接解决一个较大的问题，有时是相当困难的。分治算法的基本思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1 < k < n+1，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治算法就是可行的。由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此自然引出递归算法。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 本次课程设计正是采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。 关键词：分治算法 目录 摘要 ..................................................................................................................... I 1 问题描述 (1) 2 问题分析 (2) 3 算法设计 (3) 4 算法实现 (7) 5 测试分析 (11) 结论 (12) 参考文献 (13) 1 问题描述 设有n位选手参加网球循环赛，n=2k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按以下要求为比赛安排日程， 1)每位选手必须与其他n-1格选手格赛一场； 2)每个选手每天只能赛一场； 3)循环赛一共进行n-1天； 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n,1≤j≤n-1。 内江师范学院 数据结构与算法设计课程设计实验报告册 编制算法设计课题组审定曾意 数学与信息科学学院 2014年9月 1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告； 2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D； 3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告； 4. 实验成绩评定分为A+、A、A-、B+、B、C、D 各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合 实验名称：算法设计基础实验(实验一) 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC++计算机 实验日期：年_月_日实验地点：第五教学楼北802 实验目的： 掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。 实验准备： 1. 在开始本实验之前，请复习相关实验内容； 2. 需要一台准备安装Windows XP Professional操作系统和装有VC++6.0的计算机。 实验内容： 求n至少为多大时，n个1组成的整数能被2013整除。 实验过程： 1.1算法思想 2013=61*33,6个1能够整除33,寻找满足n个1能够整除61的n即可。 1.2算法步骤 1?定义变量y储存余数，i储存1的个数，m为被除数，初始化为111111； 2?如果被除数能够除尽61,输出i; 如果被除数不能够除尽61，while继续循环，m=y*1000000+111111,i++; 3?重复2，直到找到满足条件的m为止，输出i; 1.3算法实现(C++程序代码) #in clude 课程设计说明书 （操作系统) 题目:进程调度 院系:计算机科学与工程学院 专业班级：信息安全１3—2 学号： 20１３302９xｘ 学生姓名: xｘ 指导教师：ｘｘ 2０１5年１2月 15日 ?安徽理工大学课程设计（论文)任务书 计算机科学与工程学院 安徽理工大学课程设计（论文)成绩评定表 摘要 现代计算机系统中,进程就是资源分配与独立运行得基本单位,就是操作系统得核心概念.因而,进程就成为理解操作系统如何实现系统管理得最基本，也就是最重要得概念。进程调度就是进程管理过程得主要组成部分,就是必然要发生得事件。 在现代操作系统中，进程得并发机制在绝大多数时候，会产生不断变化得进程就绪队列与阻塞队列。处于执行态得进程无论就是正常或非正常终止、或转换为阻塞状态，都会引发从就绪队列中,由进程调度选择一个进程进占C ＰU。 进程调度得核心就是进程调度得算法。在本课程设计中,用良好清晰得界面向用户展示了进程调度中得时间片轮转调度算法.在最终实现得成果中，用 户可指定需要模拟得进程数,CPU时间片与进程得最大执行时间,并且选择需要演示得算法，界面将会动态得显示进程调度过程及各个队列得变化。通过此进程调度模拟系统,用户可以对时间片轮转调度算法有进一步以及直观得了解。 关键词：进程，调度，PCB，时间片轮转?目录 1、设计目得................................................................................................................. 错误!未定义书签。 2、设计思路................................................................................................................. 错误!未定义书签。 3、设计过程................................................................................................................. 错误!未定义书签。 3、１流程图............................................................................................................. 错误!未定义书签。 3、2算法?错误!未定义书签。 3、3数据结构.......................................................................................................... 错误!未定义书签。 3、4源代码?错误!未定义书签。 4、实验结果及分析..................................................................................................... 错误!未定义书签。 4、1使用说明?错误!未定义书签。 4、2程序演示?错误!未定义书签。 5、实验总结................................................................................................................. 错误!未定义书签。 6、参考文献................................................................................................................. 错误!未定义书签。算法设计与分析课程设计(完整版)
操作系统课程设计
算法课程设计资料
内部堆排序算法的实现课程设计说明书
Dijkstra算法的实现-数据结构与算法课程设计报告
操作系统课程设计报告
算法课程设计
计算机算法设计与分析课程设计.
算法设计与分析课程设计-实验指导书
操作系统(一个小型操作系统的设计与实现)课程设计
算法课程设计说明书
算法分析资料报告与设计-课程设计资料报告材料
计算机操作系统课程设计
操作系统课程设计(LRU算法)完整版内含代码
操作系统课程设计题目
数据结构与算法课程设计学生成绩管理系统
山东理工大学—操作系统课程设计选题
分支算法循环赛日程表课程设计
数据结构与算法设计课程设计
操作系统课程设计