计算机算法分析课程设计[1]
![计算机算法分析课程设计[1]](https://img.sodocs.net/img10/0hxvxg55hdlew88eq6e-01.webp)
![计算机算法分析课程设计[1]](https://img.sodocs.net/img10/0hxvxg55hdlew88eq6e-92.webp)
成绩评定表
学生姓名唐智班级学号1209010324
课程设计题目
专业信息与计算
科学
评
语组长签字：
成绩
日期20 年月日
课程设计任务书
学院理学院专业信息与计算科学
学生姓名郭卫班级学号1209010315
课程设计题目分治法——黄金分配回溯法——填字游戏
实践教学要求与任务:
1、巩固和加深对计算机算法分析与设计基本知识的理解。
2、初步掌握简单软件的分析方法和设计方法。
3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。
4、具体任务
（1）分治算法解决黄金分配问题。
（2）回溯法解决填字游戏问题。
工作计划与进度安排:
第一天查阅资相关料；第二、三天程序设计；
第四天程序调试；第五天答辩
指导教师：
201 年月日专业负责人：
201 年月日
学院教学副院长：
201 年月日
摘要
算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出的各种不同的解决方案，并且要针对具体问题做细致的空间与时间复杂度分析。本文通过计算机算法分析设计出解最优二叉搜索树问题的动态规划算法和0-1背包问题的回溯法算法，利用C++语言编写程序实现算法。
动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻画其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。
回溯法算法是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。
关键词：动态规划；二叉搜索树；回溯法；剪枝原则；C++
目录
一、课程设计目的 (1)
二、课程设计内容 (1)
三、概要设计 (1)
3.1 动态规划—最优二叉搜索树 (1)
3.2 回溯法—0-1背包 (1)
四、详细设计与实现 (2)
4.1 动态规划—最优二叉搜索树 (2)
4.1.1最优二叉搜索树问题描述和分析 (2)
4.1.2最优子结构性质 (3)
4.1.3递归计算最优值 (3)
4.1.4算法实现题 (3)
4.2 回溯法—0-1背包 (6)
4.2.1 0-1背包问题的描述及分析 (6)
4.2.2算法实现 (8)
总结 (14)
参考文献 (16)
一、课程设计目的
《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。
二、课程设计内容
1、动态规划：设计出解最优二叉搜索树问题的动态规划算法；
2、回溯法：设计出解图的着色问题全部可行解的回溯法算法。
三、概要设计
3.1 动态规划—最优二叉搜索树
动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：
（1）找出最优解的性质，并刻画其结构特征；
（2）递归地定义最优值（写出动态规划方程）；
（3）以自底向上的方式计算出最优值；
（4）根据计算最优值时得到的信息，构造一个最优解。
3.2 回溯法—0-1背包
回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。
用回溯法解决0-1背包问题的步骤：
（1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数原则避免无效搜索。
四、详细设计与实现
4.1 动态规划—最优二叉搜索树
4.1.1最优二叉搜索树问题描述和分析
设{}n x x x S ,,,21 =是有序集，且n x x x <<< 21，表示有序集S 的二叉搜索树利用二叉树的结点存储有序集中的元素。它具有下述性质：存储于每个结点中的元素x 大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉树的叶结点是形如()1,+i i x x 的开区间，在表示S 的二叉搜索树中搜索元素x ，返回的结果有两种情况：
（1）在二叉搜索树的内结点中找到i x x =。
（2）在二叉搜索树的叶结点中确定()1,+∈i i x x x 。
设在第(1)中情形中找到元素i x x =的概率为i b ；在第(2)种情形中确定
()1,+∈i i x x x 的概率为i a ，其中约定+∞=-∞=+10,n x x ，显然有：
;1,0;0,0n j b n i a j i ≤≤≥≤≤≥11
0=+∑∑==n
j j n
i i b a ，()n n a b a b a ,,,,,110 称为集合S 的存
取概率分布。
在表示S 的二叉搜索树T 中，设存储元素i x 的结点深度为i c ；叶结点()1,+j j x x 的结点深度为j d ，则：
()∑∑==++=n
j j
j i n i i d a c b p 0
1
1
表示在二叉搜索树T 中进行一次搜索所需要的平均比较次数，p 又成为二叉搜索树T 的平均路长。在一般情况下，不同的二叉搜索树的平均路长是不相同的。
最优二叉搜索树问题是对于有序集S 及其存取概率分布()n n a b a b a ,,,,,110 ，在所有表示有序集S 的二叉搜索树中找到一棵具有最小平均路长的二叉搜索树。
4.1.2最优子结构性质
二叉搜索树T 的一棵含有结点j i x x ,, 和叶结点()()11,,,,+-j j i i x x x x 的子树可以看作是有序集{}j i x x ,, 关于全集合{}11,,+-j i x x 的一棵二叉搜索树，其存取概率为以下的条件概率：
()j k i w b b ij k k ≤≤=/ ()j h i w a a ij h h ≤≤-=1/
公式中：n j i a b b a w j j i i ij ≤≤≤++++=-1,1 。
设ij T 是有序集{}j i x x ,, 关于存取概率{}
j j i i a b b a ,,,,1 -的一棵最优二叉搜索树，其平均路长为ij p 。ij T 的根结点存储元素m x 。其左右子树l T 和r T 的平均路长分别为l p 和r p 。由于l T 和r T 中结点深度是它们在ij T 中的结点深度减1，故有：
r j m l m i j i j i j i p w p w w p w ,11,,,,+-++=
由于l T 是关于集合{}1,,-m i x x 的一棵二叉搜索树，故1,-≥m i l p p 。若
1,->m i l p p ，则用1,-m i T 替换l T 可得到平均路长比ij T 更小的二叉搜索树。这与ij T 是最优二叉搜索树矛盾。故l T 是一棵最优二叉搜索树。同理可证r T 也是一棵最优二叉搜索树。因此最优二叉搜索树问题具有最优子结构性质。 4.1.3递归计算最优值
最优二叉搜索树ij T 的平均路长为ij p ，则所求的最优值为n p ,1。由最优二叉搜索树问题的最优子结构性质可建立计算ij p 的递归式如下：
{}j i p w p w w p w j k j k k i k i j
k i j i j i j i ≤++=++--≤≤,,1,11,1,,,,m in
初始时，n i p i i ≤≤=-1,01,。 记j i j i p w ,,为()j i m ,，则()n n n p p w n m ,1,1,1,1==为所求的最优值。
计算()j i m ,的递归式为：
()()(){}j i j k m k i m w j i m j
k i j i ≤++-+=≤≤,,11,,m in ,
()n i i i m ≤≤=-1,01,
据此，可设计出解最优二叉搜索树问题的动态规划算法。 4.1.4算法实现题
给出标识符集{4,5,6}={do,if,stop}存取概率，若b1=0.5 b2=0.6 b3=0.08 a0=0.2 a1=0.05 a2=0.05 a3=0.05构造一棵最优二叉搜索树
源程序如下：
#include
using namespace std;
void OptimalBinarySearchTree(float a[],float b[],int n,float m[][20],int s[][20],float w[][20])
{ //求解最优值的方法
int i,r,k;
float t;
for(i=0;i<=n;i++){
w[i+1][i]=a[i]; //搜索不到的点,最优解为0
m[i+1][i]=0;
}
for(r=0;r for(i=1;i<=n-r;i++){ int j=i+r; //左子树为空 w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i+1][j]; s[i][j]=i; for(k=i+1;k<=j;k++){ t=m[i][k-1]+m[k+1][j]; if(t { //以k为根节点，左子树不为空 m[i][j]=t; s[i][j]=k; } } m[i][j]+=w[i][j]; } for(i=1;i<=n;i++) for(int j=1;j<=n;j++) cout<<"s["< } void print(int i,int j,int s[][20],int S[]) //递归输出结果 { if(j>=i){ int k=s[i][j]; cout<<"("; print(i,k-1,s,S); cout<<")"; cout<<" "< cout<<"("; print(k+1,j,s,S); cout<<")"; } } int main() { //主函数 int n,i; float a[20],b[20],m[20][20],w[20][20]; int s[20][20],S[20]; cout<<"请输入有序集元素的个数n："< cin>>n; cout<<"请输入有序集各元素的值S[i](一共"< for(i=1;i<=n;i++) cin>>S[i]; cout<<"请输入概率数组a的各元素的值a[i](一共"< cin>>a[i]; cout<<"请输入概率数组b的各元素的值b[i](一共"< for(i=1;i<=n;i++) cin>>b[i]; OptimalBinarySearchTree(a,b,n,m,s,w); cout<<"最优值即平均步长为："< return 0; } 运行结果如下： 图1 运行结果 4.2 回溯法—0-1背包 4.2.1 0-1背包问题的描述及分析 背包问题在现实生活中有着广泛的应用背景，如预算控制、项目选择、材料切割、货物装载等问题。如果对每个对象只提供两种选择：全部接受或全部拒 绝，则该背包问题就是0-1背包问题。 给定n 种物品和一个背包。物品i 的重量是i w ，其价值为i v ，背包容量为C 。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 0-1背包问题的可形式化描述为：给定, 0C >,0i w >, 0i v > ,1i n ≤≤要求找出n 元0-1向量{}12(,,...,),0,1,1n i x x x x i n ∈≤≤，使得n 1 i i i w x c =≤∑，而且n 1 i i i v x =∑达到最大。 1max n i i i v x =∑ 0n k w ≤≤ n 1 i i i w x c =≤∑ {}0,1,1i x i n ∈≤≤ 可以用树的形式将解空间表达出来。树中从第i 层到第i+1层的边上的值表示解向量中i x 的取值，并假定第i 层的左子树描述物品i V 被装入背包的情况， 右子树描述物品i V 被拒绝的情况。则该0-1背包问题的状态空间树就表示为一棵高度为n 的完全二叉树。从根结点到叶子结点的任一路径就对应解空间中的一个解向量。 构造出问题的状态空间树以后，就可以从其根结点出发搜索解空间，即决定每个物品的取舍。为了使目标函数的值增加最快，可以优先选择价值最大的物品装入背包，然后是价值量次之的物品······直至背包装不下为止。但是，如果所选择的物品重量很大，使得背包载重量消耗速度太快!以至后续能装入背包的物品迅速减少， 使得继续装入背包的物品在满足了约束方程的要求以后，无法达到目标函数的要求。因此，最好优先选择那些既能使目标函数的值增加最快，又能使背包载重量消耗速度较慢的物品装入背包。为了达到这个目的，首先把所 有物品按价值重量比的非增顺序排列，然后按照这个顺序进行搜索。 在装包过程中!要尽量优先选择价值重量比较高的物品装入背包。表现在搜索过程中!就是要尽量沿着左子树结点前进。当不能继续前进时（假设该结点为T），就得到问题的一个部分解，并把搜索转移到右子树。估计由该部分解所能得到的最大价值，即结点T的上限。可以用贪婪算法处理剩余物品：将按照价值重量比非增顺序排列的剩余物品依次装入背包，至无法完全装入下一个物品时!就将该物品的一部分装满背包。这样就可以得到一个上限。如果该值为当前最优值：继续由右子树向下搜索，扩大部分解，直至找到可行解；保存可行解，并把可行解的值作为当前最优值，向上回溯，寻找其他可行解；若该值小于当前最优值：丢弃当前正在搜索的部分解，向上回溯。反复使用此方法，直至搜索完整个解空间。 4.2.2算法实现 源程序如下： #include using namespace std; #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 #define ERROR -1 typedef float value; typedef float weight; typedef int KeyType; // 定义关键字类型为整数类型 typedef struct //元素定义 { weight w;//重量 value v;//价值 value q;//单位重量价值 int index;//序号 bool job;//表示是否被用 }Bag; typedef struct //定义背包集 { Bag r[MAXSIZE+1];//r[0]闲置或用作“哨兵单元” int length; //背包个数 }Bags; int n;//包个数 int i;//辅助整型变量 weight c;//背包的容量 weight cw;//当前重量 value bestp=0;//当前最优价值 value cp;//当前价值 Bags L;//定义背包集 int Partition(Bags &L,int low,int high) //快速排序 // 交换顺序表L中子表r[low.....high]的记录,枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大于它. { int shuzhou; //定义枢轴 L.r[0]=L.r[low]; //用第一个记录作为枢轴记录 shuzhou=L.r[low].q; while(low { while(low --high; L.r[low]=L.r[high]; while(low ++low; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; }//Partition void QuickSort(Bags &L,int low,int high) //快速排序//对顺序表L[low ....high]作快速排序 { int shuzhou; if(low { shuzhou=Partition(L,low,high); // 获得枢轴 QuickSort(L,low,(shuzhou-1)); //对枢轴前半部分排序 QuickSort(L,(shuzhou+1),high); //对枢轴后半部分排序} }//QuickSort value bound(int i) {//计算上界 weight left=c-cw;//剩余容量 value bound=cp; //以物品单位重量价值递减顺序装入物品 while(i<=n&&L.r[i].w<=left) { left-=L.r[i].w; bound+=L.r[i].v; i++; } //装满背包 if(i<=n) bound+=L.r[i].v*left/L.r[i].w; return bound; }//bound void backtrack(int i) { if(i>n) {//到达叶子结点 bestp=cp; return ; } //搜索子树 if(cw+L.r[i].w<=c) {//进入左子树 cw+=L.r[i].w; cp+=L.r[i].v; //L.r[i].job=true;//选中 backtrack(i+1); cw-=L.r[i].w; cp-=L.r[i].v; //L.r[i].job=false;//未选中 } if(bound(i+1)>bestp)//进入右子树 backtrack(i+1); }//backtrack void knapsack(weight c)//0-1背包问题主算法{ QuickSort(L,1,L.length); backtrack(1);//回溯搜索 }//knapsack int main() { //输入要选择的背包信息 cout<<"请输入背包的容量:"; cin>>c; cout<<"请输入物品个数（注意：不能超过 100个!）:"; cin>>n; if(n>100) { cout<<"你输入的物品个数太多!!!"< return FALSE; } L.length=n; for(i=1;i<=n;i++) { cout<<"请输入第个"< cin>>L.r[i].w; cout<<"请输入第个"< cin>>L.r[i].v; L.r[i].q=L.r[i].v/L.r[i].w;//单位重量价值 L.r[i].index=i;//索引号 cout< } //执行0-1背包问题主算法 knapsack(c); //输出结果 for(i=1;i<=n;i++) if(L.r[i].job) cout<<"第个"< } } 运行结果如下： 总结 通过本次课程设计，使我对快速排序、最优二叉搜索树以及回溯法求0-1背包问题的基本过程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用c++语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终能运用到实际案例中去。 对我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。而这次的课程设计，正好给了我们一个机会让我们找出自身状况与实际需要的差距，让我的编程思路变得更开阔了，拥有了更严格的设计与分析算法的思维方式，改变了我随意拼凑算法的习惯，并在以后的学习期间及时补充相关知识，为求职与正式工作做好充分的知识、能力准备，从而缩短从校园走向社会的心理转型期。 总结 通过本次课程设计，使我对快速排序、最优二叉搜索树以及图的m着色设计的基本过程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用c++语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终能运用到实际案例中去。 对我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。而这次的课程设计，正好给了我们一个机会让我们找出自身状况与实际需要的差距，让我的编程思路变得更开阔了，拥有了更严格的设计与分析算法的思维方式，改变了我随意拼凑算法的习惯，并在以后的学习期间及时补充相关知识，为求职与正式工作做好充分的知识、能力准备，从而缩短从校园走向社会的心理转型期。 参考文献 [1]王晓东. 计算机算法设计与分析（第4版）. 北京.电子工业出版社. 2012.2 [2]王晓云、陈业纲. 计算机算法设计、分析与实现. 北京.科学出版社. 2012 [3]谭浩强. C语言程序设计（第3版）. 北京.清华大学出版社. 2012 [4]陈玉福. 算法设计与分析 . 北京.清华大学出版社. 2009 [5]严蔚敏. 数据结构 . 北京.清华大学出版社. 2009 微机课程设计报告 目录 一、需求分析 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、二分搜索算法是利用（ 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.创建（插入、调整、改组） 2.输出 开发工具:windows XP操作系统,Microsoft visual c++ 6.0 编译系统; 关键词：C++ ; 二、设计主要目的及意义 目的: 1.熟悉掌握二叉树的基本操作 2.熟悉二叉树的创建(插入、调整、改组),输出以及把二叉排序树转换为二 叉平衡排序树 3.更进一步掌握有关二叉排序树的操作 意义: 软件课程设计是计算机科学与技术专业软件方向的一个重要环节，是语言类课程学习的总结。通过课程设计使我们加深对程序设计的理解，掌握程序开发的基本方法，深化学生面向对象的编程设计思想和新一代程序设计的逻辑思维方式，把课堂上所学到的多个单元串到一起，提高我们在软件设计过程中分析问题和解决问题的实际动手能力，使我们的理论知识和实践技能得到共同发展，最终提高我们解决问题和分析问题的能力。为我们踏上工作岗位之前提供了一次专业研究和项目开发的宝贵实践机会，为今后的工作积累经验。 三、课程设计的过程 主要算法说明: 1.主要数据结构定义 typedef struct node node ; Struct node { Node*parent; Node*left; Node*right; Int balance;//左右子树高度之差 Int key; } 2.主要函数说明 Int scarchNode(int key, node* root, node*parent):按key查找结点 Node* minNode(node* root):树root的最小结点 Node* maxNode(node* root):树root的最大结点 Node* preNode(node* target):求前驱结点 Node* nextNode(node* targer):求后继结点 node* adjustAVL(node* root, node* parent, node* child);调整,保证二叉树的平衡性 Node* insertNode(int key, node* root):插入 Node* deletevode(int key, node* root):删除 Node*createAVL(int* data, int size):创建新的二叉树 Void interordertraverse (node*root):中序遍历 Void preordertraverse(node* root):先序遍历 3.二叉排序树的插入和删除 a.二叉排序树的插入 在二叉排序树插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义 插入过程:若二叉排序树正存在,则返回根结点; 《大学计算机基础》计算机实践任务书 一、计算机实践的任务 计算机实践的主要任务学习使用Frontpage 2003 制作网页，设计网站，并在网站上发布一个综合内容的网页。 二、计算机实践目的 1) 掌握演示文稿的建立、保存和打开操作方法； 2) 掌握幻灯片的外观设置方法； 3) 掌握在幻灯片中插入对象的方法； 4) 掌握幻灯片动画效果的设置方法； 5) 掌握在幻灯片中插入超级链接的方法； 6) 掌握用Word进行文本编辑的基本操作； 7) 掌握用Word进行格式排版的基本操作； 8）掌握利用Frontpage2003制作网页，并融入word和powerpoint 技术。 通过《计算机实践》更进一步深入了解和掌握各种应用软件的使用操作及综合应用，重点在培养学生自学计算机应用软件、开发应用、动手和创新能力。 三、计算机实践的内容及要求 1．学习掌握网页制作软件FrontPage 2003，制作网页； 2．学习掌握中文演示软件PowerPoint 2003的操作及使用，并将作品结合在网页上； 3．对于网页和幻灯片的页面修饰要求用自己制作的动画、图形、图像； 4．对于网页页面要求至少3个页面（使用超链接），网页中的内容与学生所选主题相关； 5．对于PowerPoint 2003制作的幻灯片要求至少有5张，幻灯片中的内容与学生所选主题相关； 6．学习网站的设置和网页的发布，分门别类地放置在相应的文件夹中，规范网页文件名和素材文件名，网站的首页应取名为index。 作品存放在一个文件夹中，以学号（学生卡上的学号）为文件夹名。 7．用Word字处理软件撰写出相应的计算机实践报告论文（字数要求：2000字左右）。 欢迎参观内蒙古 一、任务内容 此次我选择的内容是介绍我的家乡——内蒙古，根据自己平时对内蒙古的了 1 微程序控制器的设计与实现 目录 1设计目的 (3) 2设计内容 (3) 3具体要求 (3) 4设计方案 (3) 5 调试过程 (11) 6 心得体会 (12) 微程序控制器的设计与实现 一、设计目的 1)巩固和深刻理解“计算机组成原理”课程所讲解的原 理，加深对计算机各模块协同工作的认识 2)掌握微程序设计的思想和具体流程、操作方法。 3)培养学生独立工作和创新思维的能力，取得设计与调 试的实践经验。 4)尝试利用编程实现微程序指令的识别和解释的工作 流程 二、设计内容 按照要求设计一指令系统，该指令系统能够实现数据传送，进行加、减运算和无条件转移，具有累加器寻址、寄存器寻址、寄存器间接寻址、存储器直接寻址、立即数寻址等五种寻址方式。 三、设计要求 1)仔细复习所学过的理论知识，掌握微程序设计的思 想，并根据掌握的理论写出要设计的指令系统的微程 序流程。指令系统至少要包括六条指令，具有上述功 能和寻址方式。 2)根据微操作流程及给定的微指令格式写出相应的微 程序 3)将所设计的微程序在虚拟环境中运行调试程序，并给 出测试思路和具体程序段 4)尝试用C或者Java语言实现所设计的指令系统的加 载、识别和解释功能。 5)撰写课程设计报告。 四、设计方案 1)设计思路 按照要求设计指令系统，该指令系统能够实现数据传送，进行加、减运算和无条件转移，具有累加器寻址、寄存器寻 址、寄存器间接寻址、存储器直接寻址、立即数寻址等五种寻址方式。从而可以想到如下指令：24位控制位分别介绍如下： XRD ：外部设备读信号，当给出了外设的地址后，输出此信号，从指定外设读数据。 EMWR：程序存储器EM写信号。 EMRD：程序存储器EM读信号。 PCOE：将程序计数器PC的值送到地址总线ABUS上。 EMEN：将程序存储器EM与数据总线DBUS接通，由EMWR 和EMRD决定是将DBUS数据写到EM中，还是 从EM读出数据送到DBUS。 IREN：将程序存储器EM读出的数据打入指令寄存器IR 和微指令计数器uPC。 EINT：中断返回时清除中断响应和中断请求标志，便于下次中断。 ELP： PC打入允许，与指令寄存器的IR3、IR2位结合，控制程序跳转。 MAREN：将数据总线DBUS上数据打入地址寄存器MAR。 MAROE：将地址寄存器MAR的值送到地址总线ABUS上。 OUTEN：将数据总线DBUS上数据送到输出端口寄存器OUT 里。 STEN：将数据总线DBUS上数据存入堆栈寄存器ST中。 RRD：读寄存器组R0-R3，寄存器R?的选择由指令的最低两位决定。 RWR：写寄存器组R0-R3，寄存器R?的选择由指令的最低两位决定。 CN：决定运算器是否带进位移位，CN=1带进位，CN=0不带进位。 FEN：将标志位存入ALU内部的标志寄存器。 X2：X1：X0: X2、X1、X0三位组合来译码选择将数据送到DBUS上的寄存器。具体如下： X2 X1 X0 输出寄存器 0 0 0 IN_OE 外部输入门 0 0 1 IA_OE 中断向量 0 1 0 ST_OE 堆栈寄存器 0 1 1 PC_OE PC寄存器 、 北京理工大学珠海学院 课程设计任务书 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：完成程序仿真调试和图形仿真调试；完成课程设计说明书；课程设计答 辩总结。 [ 四、基本要求 算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出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.参考文献：列出在撰写过程中所需要用到的参考文献。 《计算机控制技术》课程设计单闭环直流电机调速系统 1 设计目的 计算机控制技术课程是集微机原理、计算机技术、控制理论、电子电路、自动控制系统、工业控制过程等课程基础知识一体的应用性课程，具有很强的实践性，通过这次课程设计进一步加深对计算机控制技术课程的理解，掌握计算机控制系统硬件和软件的设计思路，以及对相关课程理论知识的理解和融会贯通，提高运用已有的专业理论知识分析实际应用问题的能力和解决实际问题的技能，培养独立自主、综合分析与创新性应用的能力。 2 设计任务 2.1 设计题目 单闭环直流电机调速系统 实现一个单闭环直流电机调压调速控制，用键盘实现对直流电机的起/停、正/反转控制，速度调节要求既可用键盘数字量设定也可用电位器连续调节，需要有速度显示电路。扩展要求能够利用串口通信方式在PC上设置和显示速度曲线并且进行数据保存和查看。 2.2 设计要求 2.2.1 基本设计要求 （1）根据系统控制要求设计控制整体方案；包括微处理芯片选用，系统构成框图，确定参数测围等； （2）选用参数检测元件及变送器；系统硬件电路设计，包括输入接口电路、逻辑电路、操作键盘、输出电路、显示电路； （3）建立数学模型，确定控制算法； （4）设计功率驱动电路； （5）制作电路板，搭建系统，调试。 2.2.2 扩展设计要求 （1）在已能正常运行的微计算机控制系统的基础上，通过串口与PC连接； （2）编写人机界面控制和显示程序；编写微机通信程序；实现人机实时交互。 3方案比较 方案一：采用继电器对电动机的开或关进行控制。这个方案的优点是电路较为简单，缺点是继电器的响应时间慢、机械结构易损坏、寿命较短、可靠性不高。 方案二：采用电阻网络或数字电位器调整电动机的分压，从而达到调速的目的。但是电阻网络只能实现有级调速，而数字电阻的元器件价格比较昂贵。更主要的问题在于一般电动机的电阻很小，但电流很大；分压不仅会降低效率，而且实现很困难。 方案三：采用由电力电子器件组成的H 型PWM 电路。用单片机控制电力电子器件使之工作在占空比可调的开关状态，精确调整电动机转速。这种电路由于工作在电力电子器件的饱和截止模式下，效率非常高；H 型电路保证了可以简单地实现转速和方向的控制；电子开关的速度很快，稳定性也极佳，是一种广泛采用的PWM 调速技术。 兼于方案三调速特性优良、调整平滑、调整围广、过载能力大，因此本设计采用方案三。 4单闭环直流电机调速系统设计 4.1单闭环调速原理 4.1.1 闭环系统框图 4.1.2 调速原理 直流电机转速有： 常数Ke Ka 不变，Ra 比较小。 所以调节Ua 就能调节n 。 n n I K R K U K R I U n d d a e e d ?-=Φ -Φ=-=0φa a a U I U ≈- 计算机基础课程设计Word长文档排版 姓名：苏丽萍 班级： 学号: 2013年12月 目录 一、函数与极限 1.1集合的概念 1.1.1集合的表示方法 1.1.2集合间的基本关系 1.1.3集合的基本运算 1.1.4集合中元素的个数 1.2常量与变量 1.2.1变量的定义 1.2.2变量的表示 1.2.3邻域 1.3函数 1.3.1函数的定义 1.3.2函数相等 1.3.3域函数的表示方法 1.4函数的简单性态 1.4.1函数的有界性 1.4.2函数的单调性 1.4.3函数的奇偶性 1.4.4函数奇偶性 Word 长文档排版 一、函数与极限 1.1集合的概念 一般地我们把研究对象统称为元素，把一些元素组成的总体叫集合（简称集）。集合具有确定性（给定集合的元素必须是确定的）和互异性（给定集合中的元素是互不相同的）。比如“身材较高的人”不能构成集合，因为它的元素不是确定的。 我们通常用大字拉丁字母A 、B 、C 、……表示集合，用小写拉丁字母a 、b 、c ……表示集合中的元素。如果a 是集合A 中的元素，就说a 属于A ，记作：a ∈A ，否则就说a 不属于A ，记作：a A 。 ⑴、全体非负整数组成的集合叫做非负整数集（或自然数集）。记作N ⑵、所有正整数组成的集合叫做正整数集。记作N +或N +。 ⑶、全体整数组成的集合叫做整数集。记作Z 。 ⑷、全体有理数组成的集合叫做有理数集。记作Q 。 ⑸、全体实数组成的集合叫做实数集。记作R 。 1.1.1集合的表示方法 ⑴、列举法：把集合的元素一一列举出来，并用“｛｝”括起来表示集合 ⑵、描述法：用集合所有元素的共同特征来表示集合。 1.1.2集合间的基本关系 ⑴、子集：一般地，对于两个集合A 、B ，如果集合A 中的任意一个元素都是集合B 的元素，我们就说A 、B 有包含关系，称集合A 为集合B 的子集，记作A B （或B A ）。。 ⑵相等：如何集合A 是集合B 的子集，且集合B 是集合A 的子集，此时集合A 中的元素与集合B 中的元素完全一样，因此集合A 与集合B 相等，记作A ＝B 。 ⑶、真子集：如何集合A 是集合B 的子集，但存在一个元素属于B 但不属于A ，我们称集合A 是集合B 的真子集。 ⑷、空集：我们把不含任何元素的集合叫做空集。记作 ，并规定，空集是任何集合的子集。 ⑸、由上述集合之间的基本关系，可以得到下面的结论： ①、任何一个集合是它本身的子集。即A A ②、对于集合A 、B 、C ，如果A 是B 的子集，B 是C 的子集，则A 是C 的子集。 ③、我们可以把相等的集合叫做“等集”，这样的话子集包括“真子集”和“等集”。 1.1.3集合的基本运算 ⑴、并集：一般地，由所有属于集合A 或属于集合B 的元素组成的集合称为A 与B 的并集。记作A ∪B 。（在求并集时，它们的公共元素在并集中只能出现一次。） 即A ∪B ＝｛x|x ∈A ，或x ∈B ｝。 ⑵、交集：一般地，由所有属于集合A 且属于集合B 的元素组成的集合称为A 与B 的交集。记作A ∩B 。 ????? 计算机组成课程设计 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT 计算机组成原理课程设计 目录 1.第一部分复杂模型计算机的设计任务 (3) 设计目的 (3) 设计任务 (3) 设计指标 (3) 实验类型 (3) 实验设备 (3) 2.第二部分模型计算机的总体设计 (4) 主要部件的工作原理 (4) 微程序的设计 (5) 微地址转移逻辑的设计 (7) 3.第三部分模型及的组装的调试 (9) 模型机的组装 (9) 模型机的调试 (10) 实验步骤 (11) 4.第四部分附 录 (11) 八位数据原理总图 (12) 微程序流程图 (12) 微程序控制器原理图 (13) 微程序代码表(十六位) (14) 机器码汇............17 编程序 (18) 5.第五部分小 结 (18) 第一部分复杂模型计算机的设计任务一、设计目的： 建立清晰完整的整机概念； 学习设计与调试计算机的基本方法与步骤； 培养严谨的科研风格与独立的工作能力。 二、设计任务： 综合运用所学计算机原理知识，按给定的指令系统 和数据格式，在所提供设备的范围内，设计一台字 长八位的由微程序控制的模型计算机。设计并实现 较为完整的八位模型计算机。 设计微程序控制器的逻辑原理电路图； 设计微地址转移的逻辑电路图； 设计说明书。 三、设计指标： 字长八位； 时钟源MF=QB=1μs; 内存容量不得小于2^8； 指令系统不得小于十四条。要求算术逻辑指令七 条，访问内存和程序控制指令四条、输入输出指令 两条、其他指令一条。 四、实验类型：设计型实验 五、实验设备： CM++试验仪一台； 双总示波器一台； 集成电路芯片及排线若干。 第二部分模型计算机的总体设计总体设计的主要任务是根据设计要求选出所需要的主要器件，计算机的工作过程实质是不同的数据流在控制信号的作用下，在限定的数据通道中进行传送。数据通路的不同指令所通过的操作过程也不同，机器结构也各不相同。因此对数据通道的设计及其应用也是非常重要的。总体设计的原则是性价比好，尽量使用大规模的集成电路器件，以便大大减少接线的工作量。 一、主要部件的工作原理： 通常把许多寄存器之间传送信息的通道称为“数据通路”。信息从什么地方开始，中间进过哪些寄存器，最后传到哪个寄存器，都要加以控制。这些工作是由称为“操作控制器”的不见来完成的。对数据通路和时序部分，直接使用CM++实验仪器的现成电路。这次设计主要是微程序控制部分。对一台数字计算机基本 计算机网络课程设计报告 姓名：李逍逍 班级：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．家庭网络区：包括从网络中心到楼宇中的骨干交换设备，并为各住户单元提供网络接入端口，是整个小区网络系统的最基本单元。 计算机网络课程设计通过课程设计，使学生在对计算机网络技术与发展整体了解的基础上，掌握网络的主要种类和常用协议的概念及原理，初步掌握以TCP/IP协议族为主的网络协议结构，培养学生在TCP/IP协议和LAN、WAN上的实际工作能力；学会网络构建、网络日常维护以及网络管理的方法，使学生掌握在信息化社会建设过程中所必须具备的计算机网络组网和建设所需的基本知识与操作技能。运用网络工程和软件工程思想，按照需求分析、规划、设计、配置的基本流程，经历一个完整的网络工程过程，培养学生调查研究、查阅技术文献、资料、手册以及编写技术文档的能力，培养学生将理论知识应用于实践的能力。 一、格式要求及须知： （1）使用学院网站的课程设计模版，要求格式美观，字体及编号要求见表1。 表1 字体及编号要求 （2）参考文献：参考课本的参考文献格式（附录C）。但编号换成[1]、[2]……（3）附录：课程设计中的代码或得到的数据包等数据将作为该设计附件或附录，题目需要但没有的相应代码及数据包文件的将记整组不及格，需要重做。 （4）成绩记录：该设计成绩将记录到教务处成绩管理系统中。 （5）打印：经审查（发邮件到指导老师处或当面交流修改）后，方可打印、存档。打印后递送到指导老师的信箱。 （6）如发现两组设计雷同或抄袭互联网，该组重做! 二、任务完成形式： 交付课程设计说明书、设计作品（需要验收）。 设计作品指的是完整的源程序代码（对于第二类题目为仿真文件）。 课程设计说明书（纸质+电子版），内容包括：设计任务、需求分析、总体设计、详细设计（相应地给出关键的代码）、设计总结（评价/遇到的问题/体会/建议等）、使用说明等。 设计工作计划与进度安排： 根据所选题目，合理安排进度计划，总体上需要40个小时。以下仅供参考： 1. 原理知识 4小时 2. 程序设计技术 4小时 3. 开发环境与程序调试环境 4小时 4. 总体设计、关键环节的详细设计 8小时 附件一 湖南工业大学 课程设计 资料袋 计算机与通信学院（系、部）2015 ~ 2016 学年第2 学期课程名称计算机组成原理指导教师杨伟丰职称教授 学生姓名顾宏亮专业班级软件1403 学号14408300328 题目复杂模型机的设计 成绩起止日期2016 年 6 月20日～2016 年6月21 日 目录清单 附件二湖南工业大学 课程设计任务书 2015 —2016 学年第2 学期 计通 学院（系、部）软件专业1403 班级 课程名称：计算机组成原理 设计题目：复杂模型机的设计 完成期限：自2016 年 6 月20 日至2016 年6 月21 日共 1 周 内容及任务1.根据复杂模型机的指令系统，编写实验程序 2.按图连接实验线路，仔细检查线路无误后接通电源。 3.写程序 4.运行程序 进度安排 起止日期工作内容2016.6.20-2016.6.21连接线路进行实验 主 要 参 考 资 料 唐朔飞.计算机组成原理.北京：高等教育出版社 指导教师（签字）：年月日系（教研室）主任（签字）：年月日附件三 设计说明书 计算机组成原理 复杂模型机的设计 起止日期：2016 年6月20 日至2016 年 6 月21 日 学生姓名顾宏亮 班级软件1403 学号14408300328 成绩 指导教师(签字) 计算机与通信学院（部） 2016年7月1日 设计题目：复杂模型机的设计 一、设计目的 综合运用所学计算机原理知识，设计并实现较为完整的模型计算机。 二、设计内容 根据复杂模型机的指令系统，编写实验程序，并运行程序，观察和记录运行结果。 三、预备知识 1、数据格式 8位，其格式如下： 1≤X＜1。 2、指令格式 模型机设计四大类指令共十六条，其中包括算术逻辑指令、I/O指令、访问存储器、转移指令和停机指令。 （1）算术逻辑指令 （2）访存指令及转移指令 模型机设计2条访存指令，即存数（STA）、取数（LD），2条转移指令，即无条件转移（JMP）、结果 ，M （3）I/O指令 OUT指令中，addr=10时，表示选中“OUTPUT UNIT”中的数码块作为输出设备。 （4）停机指令 专业教育 ─我所认识的计算机专业 1.对专业的最初认识 1.1为什么选择计算机专业 计算机使当代社会的经济、政治、军事、科研、教育、服务等方面在概念和技术上发生了革命性的变化，对人类社会的进步已经并还将产生极为深刻的影响。目前，计算机是世界各发达国家激烈竞争的科学技术领域之一。 随着信息时代的到来，计算机逐渐成为技术及科学领域的核心。随着计算机的普及，其应用领域逐渐广泛，深刻影响着我们的学习，工作及生活。因而，计算机的学习与我们的生活息息相关。 1.2最初的认识 虽然对于这个专业刚开始的时候不了解它具体是干什么的，但是从小就对于计算机十分感兴趣，因此在高考完填报志愿时就报了这个专业。进入大学之后，看到培养计划发现这个专业应用还是挺多的，但是因此让自己更加的对以后的职业感到很迷茫，不知道究竟是该干什么了。但是既来之，则安之。相信在以后的学习过程中会慢慢地找到方向，并为之努力的。因此说对于计算机专业还是抱有很大的热情的。 2.学习的方法 2.1培养对专业的兴趣 俗话说兴趣是最好的老师，因此要想真正做好一件事情，学好自己的专业首先就要培养自己对本专业的兴趣。那么应该如何培养呢？可能阅读专业书籍对于刚刚步入大学的自己来说有点困难，也很枯燥，那么不妨先从科普书籍看起。科普书籍是了解理论、获得应用知识最好的途径。相信不少理工科的同学被量子物理和相对论搞得头昏脑胀过。究其原因，是我们的现实生活与抽象的数学模型之间存在思想意识上的鸿沟。然而要是读读斯蒂芬·霍金的《时间简史》，你就会被书中有趣的故事和例证所吸引，从而对抽象的理论有了感性的认识——即使仍然没有读懂，你也至少了解了这个学科研究的领域和目标是什么，也必然有所收获。 2.2认真学习专业课程，学好数学 大学计算机专业对数学的要求较高，其重要性不必多言。数学令不少同学头痛，除了其“繁”与“难”外，很大程度上是因为他们没有理解这些抽象理论的实际应用方向。与本科数学专业的课程设置相比，计算机专业的数 设计报告范文 一、任务内容 通过对《大学计算机基础》和《大学计算机基础学习与实验指导》这两本教材的学习后，我们应综合应用计算机进行一系列操作与使用，全面掌握并用所学的知识进行综合实践。本论文的任务主要为学习运用网页制作软件FrontPage2003制作自己的网页，了解制作过程，再者学习网站的发布和网页的发布和学习运用演示软件PowerPoint2003制作幻灯片并设计和编辑文稿进行综合演示浏览，按要求结合相应的图文素材。这里将会报告指出制作的步骤与方法，以及根据自己的主题进行网页和幻灯片的页面修饰的方法，如插入图片，用Flash制作的动画（这里将会报告制作的方法）等等。 二、设计步骤 a)利用网页制作软件FrontPage2003制作一个关于“成都著名小吃”的网页， 并用文本的编辑与格式化以及对象、表格、框架的插入与设置等操作进行网页的编辑。设置该网站的内容主题和格式，并发布该网站。 首先设计主页，内容为“成都著名小吃”，主要介绍成都著名小吃的历史和独特的风味，并用表格的方式输入各个将要介绍的小吃名“麻辣烫”、“麻婆豆腐”、“棒棒鸡”、“担担面”、“夫妻肺片”、“毛血旺”、“传统锅魁”，像菜单形式呈现出来。 接下来设计各个分页面，都用主标题“美味吧”大字体标记，下面再用各个美食的名字作为副标题，接下来就用文字阐释其特征或做法或风味或历史或吃法、、、再加上五彩的图片将该小吃描述的淋漓尽致，形象而鲜活。 最后在最后一行输入“返回主页”的字样，以便于每当看完一项小吃的网页后，可以及时返回主页看另一项小吃的网页，既方便又美观，用超链接的方式把各分页面联系在一起，自动进入对应的网页并完成网页之间的转换。 制作好网页之后，需创建一个网站，主题已确定“成都著名小吃”，则要设计结构，设置各分网页与主页之间为树形链接，主要链接都在主页上，再分别展开，以高效完成操作。可以使用网站模板修饰网站。 接下来就是将网站上传到到网上，以便让更多人能浏览到该页面，可以 XXXX大学课程设计专用纸 成绩评定表 课程设计任务书 目录 1 设计目的 (3) 2 设计内容 (3) 3 实验计算机的设计 (3) 3.1 整机逻辑框图设计 (3) 3.2 指令系统的设计 (5) 3.3 微操作控制部件设计 (5) 3.3.1微指令编码格式设计 (5) 3.3.2 微操作控制信号设计 (6) 3.4 微程序设计 (8) 3.4.1 指令对应的微程序流程图 (8) 3.4.2 微程序中各微指令二进制编码与16进制编码 (8) 3.5 微程序顺序控制方式设计 (10) 3.5.1 微程序入口地址形成方法 (10) 3.5.2 控存下地址确定方法 (10) 3.5.3 每段微程序在控存中的存放位置 (11) 3.6 编写调试程序 (12) 3.6.1 机器指令程序设计内容如下 (12) 3.6.2 每条指令所对应的机器码 (12) 3.6.3 程序在内存中的存放位置 (12) 4 实验计算机的组装 (13) 5 实验计算机的调试 (13) 5.1 调试前准备 (13) 5.2 程序调试过程 (14) 5.3 调试结果 (15) 5.4 出错和故障分析 (17) 5.4.1 出错分析 (17) 5.4.2 故障分析查找 (17) 5.4.3 确认是否属故障 (17) 5.4.4 正确判断故障原因 (18) 6 心得体会 (18) 7 参考文献 (19) 1 设计目的 1、组成一个复杂的计算机整机系统—模型机，输入程序并运行； 2、了解微程序控制器是如何控制模型机运行的，掌握整机动态工作过程; 3、定义几条机器指令，编写相应微程序并具体上机调试. 4、完成多寄存器算术减法\右移位\输入输出\转移指令实验计算机设计。 2 设计内容 利用EL-JY-II型计算机组成原理实验仪提供的硬件资源，通过设计（包括整机结构设计、指令设计、微程序设计、微指令设计、调试程序设计等）、组装、调试三个步骤完成台微程序控制的简单实验计算机的研制。 完成多寄存器算术减法\右移位\输入输出\转移指令实验计算机设计。 3 实验计算机的设计 3.1 整机逻辑框图设计 （1）模型机是由运算器，控制器，存储器，输入设备，输出设备五大部分组成。 ①运算器又是有299，74LS181完成控制信号功能的算逻部件，暂存器LDR1，LDR2，及三个通用寄存器，R0,R1，R2等组成。 ②控制器由程序计数器PC、指令寄存器、地址寄存器、时序电路、控制存储器及相应的译码电路组成。 ③存储器RAM是通过CE和W/R两个微命令来完成数据和程序的的存放功能的。 ④输出设备有两位LED数码管和W/R控制完成的。 （2）计算机由基板和CPU板两部分组成： ①基板：本部分是8位机和16位机的公共部分，包括以下几个部分：数据输入输出、显示及监控，脉冲源及时序电路，数据和地址总线，外设控制电路，单片机控制电路和键盘操作部分，与PC机通讯的接口，主存器和电源，CPLD实验板，自由实验区。 ②CPU板：本板分为8位机和16位机两种，除数据字长分为8位和16位外，都包括 学号 理工大学华夏学院 课程设计 课程名称办公自动化实训 题目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日 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 ）。中南大学微机课程设计报告交通灯课案
《计算机算法设计与分析》习题及答案
计算机科学与技术课程设计
大学计算机基础课程设计【最新】
计算机组成原理课程设计(微程序)报告
计算机仿真课程设计报告
计算机算法设计与分析
计算机控制技术课程设计报告
计算机基础课程设计-word长文档排版
计算机组成课程设计
计算机网络课程设计报告
计算机网络课程设计题目和要求
计算机组成原理课程设计
计算机科学与技术专业课程设计
计算机基础课程设计报告范文
计算机组成原理课程设计_报告全套
计算机课程设计报告书
计算机算法设计与分析期末考试复习题