算法分析与设计[1]

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

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

作业⼀

⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。

2.程序：程序是算法⽤某种程序设计语⾔的具体实现。

⼆、简答题：1.算法需要满⾜哪些性质？简述之。

答：算法是若⼲指令的有穷序列，满⾜性质：

（1）输⼊：有零个或多个外部量作为算法的输⼊。（2）输出：算法产⽣⾄少⼀个量作为输出。 （3）确定性：组成算法的每条指令清晰、⽆歧义。

（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：

（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；

（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质； （3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；

（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。 答：将递归算法转化为⾮递归算法的⽅法主要有：

（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。该⽅法通⽤性强，但本质上还是递归，

只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。（2）⽤递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。

后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。

三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]

交换a[j]、a[j+1]；

分析该算法的时间复杂性。

答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。

（1）设⽐较⼀次花时间1；

（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=i

《算法设计与分析》实验报告

实验一 递归与分治策略应用基础

学号：**************

姓名：*************

班级：*************

日期：2014-2015学年第1学期

第九周

一、实验目的

1、理解递归的概念和分治法的基本思想 2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法

3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务： 以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，

完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。（30分）

2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。（30分）

3、设有n=2k个运动员要进行网球循环赛。设计一个满足要求的比赛日程表。（40分）

提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include "iostream"

using namespace std;

#define N 100 void Perm(int* list, int k, int m)

{

if (k == m)

{

for (int i=0; i

cout << endl;

return;

}

else {

for (int i=m; i

{

swap(list[m], list[i]);

Perm(list, k, m+1); swap(list[m], list[i]);

}

}

}

void swap(int a,int b) {

int temp;

temp=a;

a=b;

b=temp; }

int main()

{

int i,n;

int a[N]; cout<<"请输入排列数据总个数：";

cin>>n;

《算法分析与设计》实验教学大纲

一、课程描述

《算法分析与设计》是计算机科学与技术专业的一门核心课程，旨在让学生了解并掌握基本的算法和算法分析的方法。通过本课程的学习，学生将能够理解算法设计的基本原理和方法，并能够应用这些原理和方法解决实际问题。

二、课程目标

1.了解算法设计和算法分析的基本概念和方法；

2.掌握常用的算法设计和分析技巧；

3.能够独立设计和实现算法，并进行正确性和效率分析；

4.熟悉常用的算法实现和优化技术；

5.能够将算法应用于解决实际问题。

三、教学内容

1.算法基础知识

(1)算法的定义和特性；

(2)算法的表达方式；

(3)算法的复杂度分析。

2.基本排序算法

(1)冒泡排序； (2)插入排序；

(3)选择排序；

(4)快速排序；

(5)归并排序；

(6)堆排序。

3.检索算法

(1)顺序查找；

(2)二分查找；

(3)哈希查找；

(4)平衡二叉树查找。

4.图算法

(1)图的表示方式；

(2)深度优先；

(3)广度优先；

(4)最短路径算法；

(5)最小生成树算法；

(6)拓扑排序。

5.动态规划算法

(1)递归算法； (2)记忆化；

(3)状态转移方程；

(4)应用案例分析。

6.贪心算法

(1)贪心算法的基本思想和特点；

(2)贪心算法的应用案例。

7.分治算法

(1)分治算法的基本思想和特点；

(2)分治算法的应用案例。

8.高级算法设计思想

(1)动态规划的高级技巧；

(2)贪心算法的高级技巧；

(3)分治算法的高级技巧；

(4)随机化算法；

(5)近似算法。

四、实验教学安排

1.实验1：基本排序算法的实现及性能比较

(1)实现冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序； (2)对比各个排序算法的性能（时间复杂度和空间复杂度）。

2.实验2：检索算法的实现及性能比较

(1)实现顺序查找、二分查找、哈希查找、平衡二叉树查找；

(2)对比各个检索算法的性能（时间复杂度和空间复杂度）。

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------

----------------------------------------------------------------------------------------------------------------------------------------------

《算法分析与设计》期末复习题

一、 选择题

1.应用Johnson法则的流水作业调度采用的算法是（D）

A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法

2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）

3. 动态规划算法的基本要素为（C）

A. 最优子结构性质与贪心选择性质

B．重叠子问题性质与贪心选择性质

C．最优子结构性质与重叠子问题性质

D. 预排序与递归调用

4. 算法分析中，记号O表示（B）， 记号表示（A）， 记号表示（D）。

A.渐进下界

B.渐进上界

C.非紧上界

D.紧渐进界

E.非紧下界

5. 以下关于渐进记号的性质是正确的有：（A）

A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))

B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))

C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})

D. f(n)O(g(n))g(n)O(f(n))

6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）

A. 最优子结构性质与贪心选择性质 Hanoi塔 A. void hanoi(int n, int A, int C, int B)