要求:算法设计与分析考试方式为小论文形式。下面给出了小论文的参考模型和参考题目,供大家选择。 1.小作业题目(仅供参考)
(题目的难易:●简单10道题★中等11道题▲复杂10道题)
问题描述:某旅游区的街道呈网格状,其中东西向的街道都是旅游街,南向的街道都是林荫道。由于游客众多,旅游街被规定为单行道。游客在旅游街上只能从西向东走,在林荫道上既可以由南向北走,也可以从北向南走。 阿隆想到这个旅游区游玩,他的好友阿福给了他一些建议,用分值表示所有旅游街相邻两个路口之间的道路浏览的必要程度,分值从-100到100的整数,所有林荫道不打分,所有分值不可能全是负值。阿隆可以从任一路口开始浏览,在任一路口结束浏览,请写出一个算法,帮助阿隆寻一条最佳的浏览路线,使得这条路线的所有分值总和最大。(算法设计与分析第二版P190—11题)
●问题描述:某工业生产部门根据国家计划的安排,拟将某种高效率的5台机器,分配给所属的,A,B,C个工厂,各工厂在获得这种机器后,可以为国家盈利如图表所示,问:这5台机器如何分配给各工厂,才能使得国家盈利最大?(P190-14题)
●问题描述:编写算法对输入的一个整数,判断他能否被4,7,9整除,并输出一下信息之一,
能同时被4,7,9整除;
能被其中两个数(要指出那两个)整除
能被其中一个数(要指出哪一个)整除
不能被4,7,9任一个整除。(P118-16)
●问题描述:某一印刷厂有6项加工任务,对印刷车间和装订车间所需的时间表如下图:完成每项任务都要先去印刷车间印刷,再到装订车间装订。问咋样安排这6项加工任务的加工工序,使得加工工时最少?(P191-17)
C的算法(P191-19).
●问题描述:编写用动态规划法求组合数m
n
●问题描述:仿照分治算法中两个大数相乘的算法策略,完成求解两个n*n阶矩阵A和矩阵B的乘积的算法。假设n=2k,要求算法的复杂性要小于O(n3).(P190-12)
●问题描述:在一个n*m的方格中,m为奇数,放置有n*m个数,方格中间的下方有一人,此人可按照5个方向前进但不能跃出方格,如图所示,人每走过一个方格必须取此方格中的数。要求到一条路径从低到顶的路径,使其数相加之和为最大,输出最大和的值。(P190-14)
●问题描述:N 块银币中有一块不合格,已知不合格的银币比正常的银币重,先用一天平,请利用它不合格的银币,并且用天平的次数最少。(P-19116)
●问题描述:旅行售货员问题:某售货员要到若干城市去推销商品,已知个城市之间的路线。她要选择一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(或总旅行费)最小(P246-6)
●问题描述:54张扑克牌,两个人轮流拿牌,每人每次最少取一张,最多取四张,谁那最后一张谁输。编写模拟计算机先拿牌取且必胜的算法。(P189-3)
★题目一选课方案设计(P290)
★题目二表达式相等判断(P291)
★题目三决策系统(P291)
★题目四数独游戏(P292)
★题目五输油管道问题(P293)
★题目六人机类(P293)
★题目七购物单(P293)
★题目八数列构造(P293)
★题目九另类杀人游戏(P293)
★题目十最有存储问题(P294)
★题目十一套汇问题(P294)
▲经典算法棋盘算法(课本143页有问题详细描述)
▲经典算法Hanno塔问题(课本58页有问题详细描述)
▲经典算法装载问题(课本235页有问题详细描述)
▲经典算法N皇后问题(课本212页有问题详细描述)
▲经典算法0-1背包问题(课本270页有问题详细描述)
▲经典算法布线问题无人机测量
问题描述:在印刷电路板将布线区域划分为n×n 个方格阵列,精确的电路布线问题要求确定连接方格a中的点到方格b中点的最短距离布线方案,在布线时电路只能沿着直线或直角布线。
▲经典算法圆排练问题
问题描述:给定n个大小不等的圆,现要将这n 个圆排进一个矩形框中,且要求各个圆与矩形框的底边相切,圆排练问题要求从n个圆的所有排练中出最小长度的圆排练。
隐藏的信息▲经典算法:最大团问题
问题描述:给定一个图G,要求G的最大团(团是指G的一个完全子图,该子图不包含在任何其他的完
全子图当中。最大团指其中包含顶点最多的团).
▲经典算法:符号三角形问题
问题描述:如下图是由14个“+”和14个“-”组成的符号三角形, 2个同号下面都是“+”,2个异号下面都是“-”。
- + + - + + +
- + - - + +
- - + - +
+ - - -
- + +
- +
-
在一般情况下,符号三角形的第一行有n个符号, 符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。
▲流水线作业调度问题
问题描述:(课本228页有详细描述)
2.选题说明
●经典算法要求在原来算法的基础上进行改进,使得算法时间或者空间复杂度比经典算法
要优。
●如果有同学已选择了不在建议范围之内的题目也可,成绩不受影响。
最后的总成绩根据小论文质量和题目的难易程度等决定。
3.小论文模版
作者1,作者2,作者33
(宁波工程学院电信学院,浙江宁波 315010)
摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息.
关键词:关键词1; 关键词2;关键词3;……(一般可选3~8个关键词,用中文表示,不用英文
Title
如:XIN Ming-ming , XIN Ming
(1.Dept. of ****, Univers ity, City Provinc e Zip Code, C hina;2.Dept. of ****, Univers ity, City Province Zip C ode, China;3.Dept. of ****, Univers ity, City Provinc e Zip C ode, China)
Abstract: abstrac t(第三人称叙述,尽量使用简单句;介绍作者工作(目的、方法、结果)用过去时,简述作者结论用一般现在时)
Key words: keyword1;keyword2; keyword3;……(与中文关键词对应,字母小写(缩略词除外));正文部分用小5号宋体字,分两栏排,其中图表宽度不超过8cm.。设置为A4页面
0 引言(一级标题四号黑体加粗)
引言的作用就是引出为什么要写这篇文章,主要有以下几个方面:
(1)如果以采用新方法新理论,就要引出为什么要
采用这种方法;
(2)如果是为了阐明某个观点,就要引出目前观点
和目前对所研究领域的现状;
(3)为什么要研究“XXX”算法(为什么要研究它,背景及必要性)
如:汉诺塔问题的描述:汉诺塔(Tower of Hanoi)问题又称“世界末日问题”有这样一个故事[1]。古代有一个
焚塔,塔内有3个基座A,B,C,开始时A基座上有64个盘子,盘子大小不等,大的在下,小的在上。有
一个老和尚想把这64个盘子从A座移到B座,但每次只容许移动一个盘子,且在移动过程中,3个基座上的盘子都始终保持大盘在下,小盘在上。移动过程中可以利用C基座做辅助。如图1所示:
假如每秒钟一次,共需多长时间呢?一年大约有 31536926 秒,计算表明移完这些金片需要5800多亿年,比地球寿命还要长,事实上,世界、梵塔、庙宇和众生都早已经灰飞烟灭。
提示:(1)可以定义问题的规模n,如盘子的数量;(2)塔柱的数量(目前有部分理论可以支撑,不妨用计算机实
现)分析规模的变化与算法的复杂度比较。(3)可以对经典的汉诺塔问题条件放松、加宽,如在经典的汉诺塔问题中大盘只能在小盘下面,放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。
1 算法设计
剩余污泥泵
1.1 汉诺塔递归算法描述(二级标题小五黑体加粗)
用人类的大脑直接去解3,4或5个盘子的汉诺塔问题还可以,但是随着盘子个数的增多,问题的规模变的越来越大。这样的问题就难以完成,更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n 个盘的汉诺塔问题可用如下递归方法实现。
如果n=1,则将圆盘从A直接移动到B。
如果n=2,则:
(1)将A上的n-1(等于1)个圆盘移到C上;
(2)再将A上的一个圆盘移到B上;
(3)最后将C上的n-1(等于1)个圆盘移到B上。
如果n=3,则:
A)将A上的n-1(等于2)个圆盘移到C(借助于B),步骤如下:
(1)将A上的n-2(等于1)个圆盘移到B上。
(2)将A上的一个圆盘移到C。
(3)将B上的n-2(等于1)个圆盘移到C。
B)将A上的一个圆盘移到B。
C)将C上的n-1(等于2)个圆盘移到B(借助A),步骤如下:(1)将C上的n-2(等于1)个圆盘移到A。
(2)将C上的一个盘子移到B。
(3)将A上的n-2(等于1)个圆盘移到B。到此,完成了三个圆盘的移动过程。
从上面分析可以看出,当n大于等于2时,移动的过程可分解为三个步骤:
第一步把A上的n-1个圆盘移到C上;
第二步把A上的一个圆盘移到B上;
第三步把C上的n-1个圆盘移到B上;
其中第一步和第三步是类同的。
算法如下:(伪码描述、自然语言描述、流程图)Main
1: { int n ;
2: Input(n);
3: Hanoi(n,”A”,”B”,”C”); }
4: Hanoi(n,char a,char b,char c)
5: { if (n>0)
6: { hanoi ( n - 1, a, c, b) ;
7: printf“(%d%a- > %c \n”,n,a,c);8: hanoi ( n - 1,b, a, c) ;}
}
递归算法结构清晰,可读性强,而且很容易用数学归纳法证明算法的正确性,然而它的运行效率较低,它的时间复杂度主要在程序嵌套调用所用的时间。T(N)=2T(N-1)+1,容易计算出T(N)=2N-1.若在程序中消除递归调用,使其转化为非递归调用算法。通常,消除递归采用一个用户定义的栈来模拟系统的递归调用工作栈,从而达到递归改为非递归算法的目的。
1.2 汉诺塔非递归算法描述
1.2.1非递归1:遍历二叉树搜索解空间(三级标题小五楷体)
通过定义MAXSTACK栈,可将递归算法转化为非递归调用算法。具体程序如下:
#defineMAXSTAC K 100 /* 栈的最大深度*/
int N = 3; /* N阶问题/*
int c = 1; /* 一个全局变量,表示目前移动的步数*/ structhanoi { /* 存储汉诺塔的结构,包括盘的数目和三个盘的名称*/
int n; char a, b, c;};
structhanoi p[MAXSTAC K];
void move(char a, int n, char c) /* 移动函数,表示把某个盘从某根针移动到另一根针*/
{ printf("%d. Move disk %d from %c to %c\n", c++, n, a, c);} void push(structhanoi *p, int top, char a, char b, char c,int n) {p[top+1].n = n - 1;
p[top+1].a = a;
p[top+1].b = b;
p[top+1].c = c; }
void unrever se_han oi(structhanoi *p) /*汉诺塔的非递归算法*/
{ int top = 0;
while (top >= 0) {
while (p[top].n > 1) { /* 向左走到尽头*/
push(p, top, p[top].a, p[top].c, p[top].b, p[top].n);
便民充值top++; }
if (p[top].n == 1) { /* 叶子结点*/
move(p[top].a, 1, p[top].b);
top--; }
if (top >= 0) { /* 向右走一步*/
move(p[top].a, p[top].n, p[top].c);
top--;
push(p, top, p[top+1].b, p[top+1].a, p[top+1].c,
p[top+1].n);
top++; } }} int main(void)
{ printf ("unreve r se progra m :n"); c = 1; p[0].n = N;
p[0].a = 'a', p[0].b = 'b', p[0].c = 'c'; unreve r se_ha n oi(p); return 0;}
1.2.2 非递归2:优化遍历二叉树搜索解空间
如:从汉诺塔的递归算法中可知,当盘子的个数大于2 时,汉诺塔的移动过程分为3步,第一步将n-1个盘从A 移到C ;第二步将第n 盘从A 移到B ;第三步将n-1个盘从C 移到B 。如果把移动过程看作是二叉树的中序遍历,则可用二叉树与汉诺塔移动过程建立一个映射[2,3]。如图2所示,三阶盘数,所对应的
图 2 移动过程的映射
1. from A →B
2. from A →C
3. from B →C
4. from A →B
5. from C →A
6. from C →B
7. from A →B
01
20
5
4
A →B
A →
C
C
→B
C
→
A
A
→
B
(a)
(b)
固废焚烧B →
C
A
→
B
图3 3阶汉诺塔与所对应的解空间树
下面给出它的中序遍历算法。将二叉树严格按照左子树在左,右子树在右画,中序遍历的结果应该是结点从左到右的一个排列。由于它是满二叉树,整个输出过程是,先输出最下层的一个结点,然后,输出上层中第一个左子树能包含该结点的结点,然后,再输出下层的下一个结点,再输出上层中第一
个左子树能包含该结点的结点,直到下层的结点全部输出完为止。用一维数le v el_po s ition [] 存储某一层已输出的结点序号。由于该二叉树是满二叉树,上层第i 个结点的左孩子一定是下层的第2i-1个结点,右孩子一定是下层的第2i 个结点。这样,判断下层结点是否是上层结点的右孩子,只要判断上下层结点在其本层的编
号是否构成2倍关系即可,整个算法程序实现如下: void output (int presen t _leve l , int positi o n, int n) //参数分别为:当前层号,在本层的序号,总层数 { int val;
val= (positi o n-1) %3;
if (presen t _leve l %2= =1) val=val+3; //如果是奇数层,其值为3, 4, 5 switch (val)
{case 0: printf ("%d from A--->B\n" ,n -presen t _leve l +1) ; break;
case 1: printf (" %d from B--->C\n" ,n-presen t _leve l +1) ; break;
case 2: printf (" % d from C--->A\n" ,n -presen t _leve l +1);break;
case 3:printf ("% d from A --->C\n" ,n -presen t _leve l +1) ; break;
case 4: printf (" %d from C--->B\n" ,n-presen t _leve l +1) ; break;
case 5:printf ("% d from B--->A\n" ,n-presen t _leve l +1); break;}} main ()
{ int level_p ositi o n [100] ; //某层的已输出的结点序号 int n,i,sample _nub,total_s ample ;//最后一层已输个数、总个数 printf (" input n=") ; //盘的数量 scanf (" %d" ,&n) ; printf (" \n") ;
sample _nub=0;total_s ample =1;
for (i=1;i<n;i++) total_s ample *=2; //最底层总样点数 for (i=0;i<=n;i++) level_p ositi o n [i] =0; i=n;
level_p ositi o n [i] ++;
output (i,level_p ositi o n [n] ,n) ;//输出第i 层某一序号的结点 sample _nub++;
while (sample _nub<total_s ample )
{ while (level_p ositi o n [i] ==2*level_p ositi o n [i-1] ) i--; //寻把该结点作为左子树的祖先结点 level_p ositi o n [i-1] ++;
output (i-1,level_p ositi o n [i-1] ,n) ; i=n;
level_p ositi o n [i] ++;
点火装置output (i,level_p ositi o n [n] ,n) ; sample _nub++;} }
2 实验分析比较