算法设计大作业

迷宫问题解决

摘要：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。

1设计总体方案

1.1总体方案

走迷宫问题的走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北、4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。

每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。

1.2主要设计思路

用一个字符类型的二维数组表示迷宫，输入值的范围是0，1，其中0表示路径，1为非路径(即障碍)，输入的矩阵大小和矩阵的内容是靠手动输入。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。

解决迷宫问题，面对的第一个问题是迷宫的表示方法。假定用n*m矩阵来描述迷宫。左上角为入口，右下角为出口。n和m分别表示迷宫的行数和列数。矩阵中，0表示可通行的路径，1代表障碍。

如图1-1表示4*6的迷宫矩阵表示。

如果现在的位置（i,j）,则下一步有：上、下、左、右四种走法，如图1-2表示。

迷宫内部的位置有四种移动的位置：上、下、左、右。而迷宫的边界位置有两种或三种可能的移动。为避免在处理内部和边界位置是存在差异，可在迷宫的周围增加一圈障碍物，如图1-3表示。

增加一圈障碍物之后，原迷宫中的每个位置都可以有四种移动方向。而且可以使程序不必去处理边界条件，从而大大简化代码的设计。这种简化是以稍稍增加数组amze 的空间为代价的。

分别用x和y来指定每个迷宫位置的行坐标和列坐标。可以定义一个类class T 来表示迷宫的位置。

class T //定义描述迷宫中当前位置的结构类型

{

public:

int x; //x代表当前位置的行坐标

int y; //y代表当前位置的列坐标

int dir; //0:无效,1:右,2:下,3:左,4:上

};

当输入一个二维数组时，每次输入的元素都存放在一个栈里面。所以定义一个栈Stack用于存放二维数组元素。这里用到栈，栈是限定尽在表位进行插入和删除的线性表。对于栈来说，允许进行插入和删除的一段，称为栈顶；不允许插入和删除的另一端，则成为栈底。在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。这里是栈的一个重要应用，就是实现递归。

class Stack

{public:

Stack(); //构造函数，置空栈

~Stack(); //析构函数

void Push(T e); //把元素data压入栈中

T Pop(); //使栈顶元素出栈

T GetPop(); //取出栈顶元素

void Clear(); //把栈清空

bool empty(); //判断栈是否为空，如果为空则返回1，否则返回0

private:

LinkNode *top; }; //指向第一个结点的栈顶指针

调试结果如图1-4：

图1-4 迷宫和矩阵的建立

如果位置（i,j）的下一步的四个方向都是可以走的，假设出发的先后顺序是向上.向下.向左.向右。每个结点都是按照先后顺序来决定下一个结点的方向。一旦做出了决定，就需要知道下一个位置的坐标。可通过保留一个如图1-5所示的偏移量表来计算这些坐标。可以把向右.向左.向下.向上移动分别编号为0.1.2.3。在图1-3中，move[i].x和move[i].y分别给出了从当前位置沿方向移动到下一个相连位置时，x和y坐标的增量。

因此假设现在的位置是（2，3），则其右边相连位置坐标的行坐标为2+move[0].x=2,列坐标为3+move[0].y=4.

定义一个主函数int main()，用于调用其他函数实现函数的嵌套调用，实现整个程序。这里运用的二维指针我是参考书上的。

int main()

{

int m=0,n=0; //定义迷宫的长和宽

int **maze; //定义二维指针存取迷宫

maze=GetMaze(m,n); //调用GetMaze(int &m,int &n)函数，得到迷宫

if(Mazepath(maze,m,n))//调用Mazepath(int **maze,int m,int n)函数获取路径

cout<<"迷宫路径探索成功!\n";

else cout<<"路径不存在!\n";

return 0;}

调试结果：

图1-6 搜索迷宫完成界面

时间算法复杂度：

O(n2）（不确定,我不太会算这个。）

对相关问题的思考：

这个迷宫问题的算法中，要在开始设置迷宫的大小。在探索迷宫路线的过程中，是通过不断的尝试来得到最终的结果，由于不能对已经设定为可走路径进行返回，所以在这个算法中有时候可能不能得到走出迷宫的路径。

总结

本次设计进展比较顺利，如期完成，并且达到了预先的设计要求，完全贯彻和执行了设计的总体方案。对于迷宫求解的模拟实现比较成功。然而，限于时间和水平，这个设计还有很多的不足之处。

迷宫问题是一个古老的问题，要在迷宫中找到出口，需要经过一连串的的错误尝试才能找到正确的路径，有时甚至找不到路径。而且这里有很多方法可以完成迷宫问题，例如顺序表，深度优先遍历，广度优先遍历等，但是我写不出程序。于是参考了《数据结构》书和我以前的一些设计，所以我们这里用的是栈。在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。

通过这次的作业，我又学会了一种解决迷宫问题的方法，我很高兴。当让在完成设计过程中，我也遇到了很多难题，比如用什么办法解决问题，怎样创建调用栈等等，但在再次复习了当时所学的《C++》,《数据结构》等课程后，发现这些问题还是可以解决的，而且解决的方法不止一种。在这里我参考的最多的是《数据结构》中“栈的应用”那一节的知识，它给我了很大帮助。

本程序虽然简短，但是却有很多难点出现。首先是对基类的调试。为了减少调试的难度，我先调试了一下类的程序。刚开始是在主函数里面直接对程序赋值，发现这将大大限制程序的可重用性，而且无法灵活运用。在指导老师的帮助下，我将程序改成用键盘直接输出，这样的话方便实现。

当然，在我遇到苦难时候，老师和同学的帮助也是很大的。他们使我进步。也让我体会到了成功的来之不易，只有真正付出过才有满意的收获。在此，我诚心的对所有帮助过我的老师、学长、同学们说一句：谢谢！

附录：

#include

using namespace std;

class T //定义描述迷宫中当前位置的结构类型

{

public:

int x; //x代表当前位置的行坐标

int y; //y代表当前位置的列坐标

int dir; //0:无效,1:右,2:下,3:左,4:上

};

class LinkNode //链表结点

{

friend class Stack;

public:

T data;

LinkNode *next;

};

class Stack

{

public:

Stack(); //构造函数，置空栈

~Stack(); //析构函数

void Push(T e); //把元素data压入栈中

T Pop(); //使栈顶元素出栈

T GetPop(); //取出栈顶元素

bool empty(); //判断栈是否为空，如果为空则返回1，否则返回0 private:

LinkNode *top; //指向第一个结点的栈顶指针

};

Stack::Stack() //构造函数，置空栈

{

top=NULL;

}

Stack::~Stack() //析构函数

{

}

void Stack::Push(T e) //把元素x压入栈中

{

LinkNode *P;

P=new LinkNode;

P->data=e;

P->next=top;

top=P;

}

T Stack::Pop() //使栈顶元素出栈

{

T Temp;

LinkNode *P;

P=top;

top=top->next;

Temp=P->data;

delete P;

return Temp;

}

T Stack::GetPop() //取出栈顶元素

{

return top->data;

}

bool Stack::empty() //判断栈是否为空，如果为空则返回1，否则返回0 {

if(top==NULL) return 1;

else return 0;

}

int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向bool Mazepath(int **maze,int m,int n);

//寻找迷宫maze中从（0，0）到（m,n）的路径

//到则返回true,否则返回false

void PrintPath(Stack p); //输出迷宫的路径

int** GetMaze(int &m,int &n); //获取迷宫

//返回存取迷宫的二维指针

int main()

{

int m=0,n=0; //定义迷宫的长和宽

int **maze;

maze=GetMaze(m,n); //调用GetMaze(int &m,int &n)函数，得到迷宫

if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int m,int n)函数获取路径cout<<"迷宫路径探索成功!\n";

else cout<<"路径不存在!\n";

return 0;

}

int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针

{

int **maze; //定义二维指针存取迷宫

int i=0,j=0;

cout<<"请输入迷宫的长和宽:";

int a,b;cin>>a>>b; //输入迷宫的长和宽

cout<<"请输入迷宫内容:\n";

m=a;

n=b; //m,n分别代表迷宫的行数和列数

maze=new int *[m+2]; //申请长度等于行数加2的二级指针

for(i= 0;i

{

maze[i]=new int[n+2];

}

for(i=1;i<=m;i++) //输入迷宫的内容，1代表不通，0代表可通

for(j=1;j<=n;j++)

cin>>maze[i][j];

for(i=0;i

maze[i][0]=maze[i][n+1]=1;

for(i=0;i

maze[0][i]=maze[m+1][i]=1;

return maze; //返回存贮迷宫的二维指针maze

};

bool Mazepath(int **maze,int m,int n)//寻找迷宫maze中从（0，0）到（m,n）的路径//到则返回true,否则返回false

{

Stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径

T Temp1,Temp2;

int x,y,loop;

Temp1.x=1;

Temp1.y=1;

q.Push(Temp1); //将入口位置入栈

p.Push(Temp1);

maze[1][1]=-1; //标志入口位置已到达过

while(!q.empty()) //栈q非空，则反复探索

{

Temp2=q.GetPop(); //获取栈顶元素

if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))

p.Push(Temp2);

//如果有新位置入栈，则把上一个探索的位置存入栈p

for(loop=0;loop<4;loop++) //探索当前位置的4个相邻位置

{

x=Temp2.x+move[loop][0]; //计算出新位置x位置值

y=Temp2.y+move[loop][1]; //计算出新位置y位置值

if(maze[x][y]==0) //判断新位置是否可达

{

Temp1.x=x;

Temp1.y=y;

maze[x][y]=-1; //标志新位置已到达过

q.Push(Temp1); //新位置入栈

}

if((x==(m))&&(y==(n))) //成功到达出口

{

Temp1.x=m;

Temp1.y=n;

Temp1.dir=0;

p.Push(Temp1); //把最后一个位置入栈

PrintPath(p); //输出路径

return true; //表示成功找到路径

}

}

if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)

//如果没有新位置入栈，则返回到上一个位置

{

p.Pop();

q.Pop();

}

}

return false; //表示查找失败，即迷宫无路经

}

void PrintPath(Stack p) //输出路径

{

cout<<"迷宫的路径为\n";

cout<<"括号内的内容分别表示为(行坐标,列坐标,方向)\n"; Stack t; //定义一个栈，按从入口到出口存取路径int a,b;

T data;

LinkNode *temp;

temp=new LinkNode; //申请空间

temp->data=p.Pop(); //取栈p的顶点元素，即第一个位置t.Push(temp->data); //第一个位置入栈t

delete temp; //释放空间

while(!p.empty()) //栈p非空，则反复转移

{

temp=new LinkNode;

temp->data=p.Pop(); //获取下一个位置

//得到行走方向

a=t.GetPop().x-temp->data.x; //行坐标方向

b=t.GetPop().y-temp->data.y; //列坐标方向

if(a==1) temp->data.dir=1; //方向向下，用1表示

else if(b==1) temp->data.dir=2; //方向向右，用2表示

else if(a==-1) temp->data.dir=3; //方向向上，用3表示

else if(b==-1) temp->data.dir=4; //方向向左，用4表示

t.Push(temp->data); //把新位置入栈

delete temp;

}

//输出路径，包括行坐标，列坐标，下一个位置方向

while(!t.empty()) //栈非空，继续输出

{

data=t.Pop();

cout<<'('<

{

case 1:cout<<"下)\n";break;

case 2:cout<<"右)\n";break;

case 3:cout<<"上)\n";break;

case 4:cout<<"左)\n";break;

case 0:cout<<")\n";break;

}}}

算法设计与分析(作业三)

算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月

实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码

现代设计方法习题答案

3.用梯度法求下列无约束优化问题：MinF(X)=x12+4x22，设初始点取为X(0)={2,2}T，以梯度模为终止迭代准则，其收敛精度为5。 1)求初始点梯度▽F(X) ▽F(X)={2x1,8x2}T▽F(X(0))={4,16}T (2)第一次搜索 |▽F(X(0))|=16.5,S(0)=- ▽F(X(0))/16.5=-{0.243,0.97}T α(0)=2.157 X(1)=X(0)+α(0)S(0)={1.476,-0.923}T ▽F(x(1))={2.952,-0.738}T |▽F(x(1))|=3.043<5.0 故满足要求，停止迭代。 最优点X*={1.476,-0.0923}T 最优值F(X*)=2.21 4.

5.

6. 用外点法求解约束优化问题： ()()12211221min ..0()0 f X x x s t g X x x g X x =+=-≤=-≤ ， 收敛准则：(1) ()0.10.01k k X X εδ+-≤=，约束容限＝ 解：（1）利用外点法惩罚法构造无约束优化问题 () ( ) 12()22()212121(min ,()() k k k x x X r x x r x x r x +??Φ=?++-+-??可行域内）（可行域外） （2）此例只是为了说明外点法的思路，用微分法求解上述无约束优化问题。 用极值条件求解： 在可行域内：偏导数不可能等于0，即可行域内无极值 在可行域外，令： ()2()11211 ()2122 14()2012()0k k k r x x x r x x r x x x ?Φ =+-+=??Φ =--=?

《ACM算法与数据结构设计》大作业

《ACM算法与数据结构设计》课程大作业报告 题目：五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24

注意事项 （1）课程大作业从《ACM算法与数据结构设计》课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 （3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 （4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚19:00~20:00，地点：计算中心A机房。

一、课题名称： 五位以内的对称素数 二、课题内容和要求： 题目：判断一个数是否为对称且不大于五位数的素数。 要求：判断输入的一组数据（正整数）是否是五位以内的对称素数，逐个判断并输出“yes”或“no” 三、课题分析： 定义两个函数分别判断数据是否为素数（bool isprime(int n)），是否是对称数（bool issym(int n)）；在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件，才能判断一个数据是五位以内的对称素数，输出“yes”；否则输出“no”。 输入输出方案： 输入: 输入数据含有不多于50个的正整数(0

算法分析与设计作业及参考答案样本

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )

A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:

现代设计方法 作业

现代设计方法作业习题1 姓名王金昆工程0802班200879250222 2-1.制作一个体积为5m^3的货箱，由于运输装卸要求其长度不小于4m，要求钢板用料最省，试写出该问题的优化数学模型. 解：设该货箱长为x1m、宽为x2m、高为x3m，表面积为S,体积为V.由题意可以建立优化数学模型： S=2*(x1*x3+x2*x3)+x1*x2; V=x1*x2*x3=5; x1>=4; x2>=0; x3>=0; 选择最优化算法求解Smin. 我选择Lingo软件来求解，编程如下： min=fx; fx=2*(x1*x3+x2*x3)+x1*x2; x1*x2*x3=5; x1>=4; x2>=0; x3>=0; 点击Solve出现结果： Local optimal solution found. Objective value: 15.14911 Extended solver steps: 5 Total solver iterations: 112 Variable Value Reduced Cost FX 15.14911 0.000000 X1 4.000000 0.000000 X3 0.7905694 0.1107763E-07 X2 1.581139 0.000000 所以表面积Smin=15.14911 m^2,此时长为4m，宽为1.581139 m,高为0.7905694 m. 2-2.把一根长为L的铜丝截成两段，一段弯成圆形，一段完折成正方形。求截断的两段为何比例才能使圆形和正方形的面积之和最大，试写出该问题的优化数学模型。 解：设弯成正方形的边长为x，所围成的圆形和正方形面积之和为S。建立优化数学模型： 取pai-3.1415926

最新算法分析与设计作业(一)及参考答案讲课讲稿

《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、递归算法：（C ） A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是：（C ） A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的：（A ） A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是：（ A ） A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是：（B） A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是：（A） A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质：（D ） A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是：（A ） A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题：（ C ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是：（A ） A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ） A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到：（C ） A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是：（A ） A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是：（ A ） A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分： 二、写出下列程序的答案（每题2.5分，共2题） 1、请写出批处理作业调度的回溯算法。 #include #include using namespace std; class Flowing { friend int Flow(int ** ,int ,int []); private: //int Bound(int i); void Backtrack(int t); int **M;// int *x;//当前解

《程序设计与算法综合实践》期末大作业题目及评分标准

2017级《程序设计与算法综合实践》 期末大作业题目及评分标准 有如下情况之一者，为不及格。 （1）未能完成所选题目评分标准的最低要求。 （2）抄袭他人成果。 （3）大作业检查时不带电脑，或电脑没有C语言开发环境。 （4）出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。 备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 -

算法设计大作业—求解Tsps问题

基于贪心算法求解TSP问题 一、TSP问题 TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述： V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目； E={(r, s): r,s∈V}是所有城市之间连接的集合； C = {crs: r,s∈V}是所有城市之间连接的成本度量（一般为城市之间的距离）； 如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。 一个TSP问题可以表达为： 求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。 二、贪心算法 贪心算法，又名贪婪算法，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。 1、贪心算法的基本思路 从问题的某一个初始解触发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。大致步骤如下： 1）建立数学模型来描述问题； 2）把求解的问题分成若干个子问题 3）对每一个子问题求解，得到子问题的局部最优解 4）把子问题的局部最优解合成原问题的一个解 2、贪心算法的实现框架 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。 从问题的某一初始解出发； while （能朝给定总目标前进一步） { 利用可行的决策，求出可行解的一个解元素； } 由所有解元素组合成问题的一个可行解； 3、贪心算法存在的问题 1）不能保证求得的最后解是最佳的；

现代设计方法大作业

机电工程学院 现代设计方法大作业基于汽车噪声的TRIZ分析 学号：S314070064 专业：机械工程 学生姓名：*** 任课教师：*** 教授 2015年1月

基于汽车噪声的TRIZ分析 一对技术系统进行初步分析 1.选择系统。 我所选择的系统是汽车。 2.系统的三维图，如图1所示。 图1 汽车的三维图 汽车工作原理：汽车的行驶主要靠发动机来带动，以四冲程汽油机为例，四冲程汽油机是将空气与汽油或柴油以一定的比例混合成良好的混合气，在吸气冲程被吸入汽缸，混合气经压缩点火燃烧而产生热能，高温高压的气体作用于活塞顶部，推动活塞作往复直线运动，通过连杆、曲轴飞轮机构对外输出机械能。四冲程汽油机在进气冲程、压缩冲程、做功冲程和排气冲程内完成一个工作循环。汽油机简图及其具体运动过程如图2所示。 图2 四冲程汽油机工作循环图 （1）进气行程 化油器式汽油机将空气与燃料先在气缸外部的化油器中进行混合，然后再吸入气缸。进气行程中，进气门打开，排气门关闭。随着活塞从上止点向下止点移

动，活塞上方的气缸容积增大，从而气缸内的压力降低到大气压力以下，即在气缸内造成真空吸力。这样，可燃混合气便经进气管道和进气门被吸入气缸。 （2）压缩行程 为使吸入气缸内可燃混合气能迅速燃烧，以产生较大的压力，从而使发动机发出较大功率，必须在燃烧前将可燃混合气压缩，使其容积缩小、密度加大、温度升高，即需要有压缩过程。在这个过程中，进、排气门全部关闭，曲轴推动活塞由下止点向上止点移动一个行程称为压缩行程。 （3）作功行程 在这个行程中，进、排气门仍旧关闭。当活塞接近上止点时，装在气缸盖上的火花塞即发出电火花，点燃被压缩的可燃混合气。可燃混合气被燃烧后，放出大量的热能，因此，燃气的压力和温度迅速增加，所能达到的最高压力约为3-5Mpa，相应的温度则为2200-2800K。高温高压的燃气推动活塞从上止点向下止点运动，通过连杆使曲轴旋转并输出机械能，除了用于维持发动机本身继续运转而外，其余即用于对外作功。 （4）排气行程 可燃混合气燃烧后生成的废气，必须从气缸中排除，以便进行下一个进气行程。当膨胀接近终了时，排气门开启，靠废气的压力进行自由排气，活塞到达下止点后再向上止点移动时，继续将废气强制排到大气中。活塞到上止点附近时，排气行程结束。 汽车的执行机构：轮胎。 作用对象：路面。 3.汽车系统的黑箱图。 汽车的黑箱图如图3所示。 图3 汽车系统黑箱图 4.确定系统主要有益功能和其它功能。 汽车主要有益功能：载运客、货物和牵引客、货挂车。

软件系统分析与设计大作业

《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1

目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················

一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。

二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。

《算法分析与设计》作业参考答案

《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j]

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.

算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

现代设计方法3000字总结

现代设计方法 现代设计方法是随着当代科学技术的飞速发展和计算机技术的广泛应用而在设计领域发展起来的一门新兴的多元交叉学科。以满足市场产品的质量、性能、时间、成本、价格综合效益最优为目的,以计算机辅助设计技术为主体,以知识为依托,以多种科学方法及技术为手段,研究、改进、创造产品和工艺等活动过程所用到的技术和知识群体的总称。 现代设计方法有:并行设计、虚拟设计、绿色设计、可靠性设计、智能优化设计、计算机辅助设计、动态设计、模块化设计、计算机仿真设计、人机学设计、摩擦学设计、反求设计、疲劳设计。 一、并行设计 并行设计是一种对产品及其相关过程(包括设计制造过程和相关的支持过程)进行并行和集成设计的系统化工作模式。强调产品开发人员一开始就考虑产品从概念设计到消亡的整个生命周期里的所有相关因素的影响，把一切可能产生的错误、矛盾和冲突尽可能及早地发现和解决，以缩短产品开发周期、降低产品成本、提高产品质量。 二、虚拟设计 在达到产品并行的目的以后，为了使产品一次设计成功，减少反复，往往会采用仿真技术，而对机电产品模型的建立和仿真又属于是虚拟设计的范畴。所谓的虚拟制造(也叫拟实制造)指的是利用仿真技术、信息技术、计算机技术和现实制造活动中的人、物、信息及制造过程进行全面的仿真，发现制造过程中可能出现的问题，在真实制造以前，解决这些问题，以缩减产品上市的时间，降低产品开发、制造成本，并提高产品的市场竞争力。 三、绿色设计 绿色设计是指以环境资源保护为核心概念的设计过程，其基本思想就是在设计阶段就将环境因素和预防污染的措施纳人产品设计之中，将环境性能作为产品的设计目标和出发点，力求使产品对环境的影响为最小。 产品设计的基本流程为：市场调研--草图构思--方案设计。 四、可靠性设计 机电产品的可靠性设计可定义为:产品在规定的条件下和规定的时间内，完成规定功能的能力。可靠性设计是以概率论为数学基础，从统计学的角度去观察偶然事件，并从偶然事件中找出其某些必然发生的规律，而这些规律一般反映了在随机变量与随机变量发生的可能性(概率)之间的关系。用来描述这种关系的模型很多，如正态分布模型、指数分布模和威尔分布模型。 五、智能优化设计 随着与机电一体化相关技术不断的发展，以及机电一体化技术的广泛使用，我们面临的将是越来越复杂的机电系统。解决复杂系统的出路在于使用智能优化的设计手段。智能优化设计突破了传统的优化设计的局限，它更强调人工智能在优化设计中的作用。智能优化设计应该以计算机为实现手段，与控制论、信息论、决策论相结合，使现代机电产品具有自学习、自组织、自适应的能力，其创造性在于借助三维图形，智能化软件和多媒体工具等对产品进行开发设计。 六、计算机辅助设计 机械计算机辅助设计（机械CAD）技术，是在一定的计算机辅助设计平台上，对所设计的机械零、部件，输入要达到的技术参数，由计算机进行强度，刚度，稳定性校核，然后输出标准的机械图纸，简化了大量人工计算及绘图，效率比人工提高几十倍甚至更多。 七、动态设计 动态设计法是在计算参数难以准确确定、设计理论和方法带有经验性和类比性时，根据施工

哈工大现代设计方法大作业

2014年春季学期 “机电产品现代设计方法”课程大作业一 作业题目：雷达转台设计 学生姓名： 评阅教师： 作业成绩：

1.设计任务 雷达底座转台设计：一个回转自由度 承载能力：500kg 被测件最大尺寸：Ф500×600mm 台面跳动：，台面平面度： 台面布置T型槽，便于负载安装 方位转角范围：±120° 具有机械限位和锁紧机构 角位置测量精度：±5′ 角位置测量重复性：±3′ 角速度范围：°/s～60°/s 2.设计流程 如上图所示，整个设计过程分为功能设计、总体方案设计、详细设计和设计总结四部分。功能设计部分 要结合所给出的性能要求以及我们设计的转台的目标客户可能存在的功能需求，对转台的功能进行定义。然后将转台的功能细化为小的功能单元，对应于一个个要实现功能的结构单元。然后利用QFD图对要实现的各种功能实现综合评估，评价出功能需求的相对重要性及解决方案的相对重要性。 总体方案设计部分 我们首先利用SysML语言来明确各部分功能的参数以及参数约束之间的关系，然后综合考虑各种参数，设计出整体的设计草图。

详细设计部分 首先要使得零件实现其所对应的功能，使其满足其精度及强度的要求。在此基础上，要综合考虑工件的可加工性，可装配性以及价格等因素，从而选出最符合我们需求的设计。然后根据确定的参数和方案，利用三维建模软件CATIA来进行三维建模，并将3D图进行投影，得出适合工业加工的2D图，完成整个设计。 设计总结部分 对整个过程中进行反思，考虑这个过程中存在的不足以及设计过程种学到的知识，以便应用于以后的设计当中。 设计 QFD(全称Qualification Function Deployment)是进行设计总体规划的工具。可以根据消费者的需求与需求的重要性来对工程设计做出相应的规划。 如图所示，其中第一纵行代表了安全性高，价格便宜，角度定位精度高及重复定位精度高等一系列的客户可能对所设计的转台所提出的要求。第三列(Importance of whats)用数字显示出各功能的重要性。数字越大，所对应的功能越重要，所有数字之和为100，以防止把每一项都标注得很重要，无法得出比较重要的功能。参数的分配，理论上应是根据对客户的进行调查问卷，然后根据客户的答复，给第一列中的功能按重要性赋值得到的相对重要性的饼状图如下。 定位精度、重复定位精度、可靠性、安全性为主要考察功能，重要性参数确定的比较合理。 其中第一行代表了重量、伺服电机等对第一列的为了实现功能的设计。这里将所有能想到的设计列出。 屋顶代表着各功能之间的关系。它表示了各种设计之间的关系，相互促进(+)或者相互限制(-). 以此可以对设计有个宏观的综合的考虑得到一个中性的方案。 而中间的主体矩阵部分起到衡量横行上的设计单元对客户需求的功能的满足程度，将各列里的数字加起来，即为该设计方案所对应的重要程度，重要程度越大，说明越应该重点设计。 如图所示，我们得到个设计方案的相对重要程度如下。从图中我们可以看出，为了实现客户所需求的功能，轴的设计以及电机的选择显得至关重要。这意味着在后续的设计中，应该着重设计这部分。

对并行算法的介绍和展望——学期大作业

《计算机系统结构》大作业 对并行算法的介绍和展望 专业计算机科学与技术 班级 111 学号 111425020133 姓名完颜杨威 日期 2014年4月17日 河南科技大学国际教育学院

对并行算法的介绍和展望 我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。 并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已

算法分析与设计(线下作业二)

《算法分析与设计》 学习中心： 专业： 学号： 姓名：

作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。

3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。

算法设计与分析课程大作业

题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术

目录 《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (4) 1、问题描述 (4) 2、算法分析 (4) 3. 算法的描述 (5) 4、部分算法实现 (6) 5. 运行结果 (8) 6、时空效率分析 (8) 二．贪心算法解多机调度问题 (8) 1、问题描述 (8) 2、算法分析 (9) 3.部分算法实现 (9) 4.计算复杂性分析 (11) 5. 运行结果 (12) 三．回溯法解决批作业调度问题 (12) 1.问题描述 (12) 2.算法思想 (13) 3. 部分算法实现 (14) 4.运行结果 (15) 5.时间复杂性分析 (15) 四．作业调度算法比较 (16) 五．课程学习总结 (16)

摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法；

一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1）