05计本算法设计与分析

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 A 卷

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 2007 年 1 月 13 日 下 午 18 点 30 分

题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 福建师范大学试卷纸 共 9 页，第 1 页

一．填空题（每空2分，共30分） 1．算法的时间复杂性指算法中 的执行次数。 2．在忽略常数因子的情况下，O、?和?三个符号中， 提供了算法运行时间的一个上界。 3．设Dn表示大小为n的输入集

实验报告2

课程 数据结构与算法 实验名称 递归与分治策略(二) 第 页 班级 10计本 学号 105032010111 姓名 陈兴灶

实验日期：2012年3月6日 报告退发 (订正 、 重做)

一、实验目的

掌握递归及分治策略的原理和应用。

二、实验环境

1、微型计算机一台

2、WINDOWS操作系统，Java SDK，Eclipse开发环境

三、实验内容

必做题：

1、编程实现二分搜索算法。

2、编程实现棋盘覆盖问题，现有四种类型的骨牌编号分别为1、2、3、4，请用这四种骨牌覆盖特殊棋盘，并输出结果。

3、编程实现合并排序的递归算法。

4、编程实现合并排序的非递归算法。

5、编程实现快速排序。

四、实验步骤和结果

第一题：

import java.util.Arrays;

import java.util.Scanner;

public class BinSearch {

/** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub

实验报告2

课程 数据结构与算法 实验名称 递归与分治策略(二) 第 页 班级 10计本 学号 105032010111 姓名 陈兴灶

实验日期：2012年3月6日 报告退发 (订正 、 重做)

一、实验目的

掌握递归及分治策略的原理和应用。

二、实验环境

1、微型计算机一台

2、WINDOWS操作系统，Java SDK，Eclipse开发环境

三、实验内容

必做题：

1、编程实现二分搜索算法。

2、编程实现棋盘覆盖问题，现有四种类型的骨牌编号分别为1、2、3、4，请用这四种骨牌覆盖特殊棋盘，并输出结果。

3、编程实现合并排序的递归算法。

4、编程实现合并排序的非递归算法。

5、编程实现快速排序。

四、实验步骤和结果

第一题：

import java.util.Arrays;

import java.util.Scanner;

public class BinSearch {

/** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub

第1章 绪 论

算法理论研究的是算法的设计技术和算法的分析技术，前者是指面对一个问题，如何设计一个有效的算法，后者则是对已设计的算法，如何评价或判断其优劣。二者是相互依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。

1.1 算法的基本概念

算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。例如，操作系统是现代计算机系统中不可缺少的系统软件，操作系统的各个任务都是一个单独的问题，每个问题由操作系统中的一个子程序根据特定的算法来实现。用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时，都是必须予以解决的重要问题。

1.1.1 为什么要学习算法

用计算机求解任何问题都离不开程序设计，而程序设计的核心是算法设计。一般来说，对程序设计的研究可以分为四个层次：算法、方法学、语言和工具，其中算法研究位于最高层次。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。例如，用于数据存储和检索的Hash算法产生于20世纪50年代，用于排序的快速排序算法发明于20世纪60年代，但他们至今仍被人

一 填空题

1. 一个计算机算法的指令序列需要满足性质的是输入、输出、确定性、有限性。

输入、输出、确定性、有限性

2.9n?10n的渐近表达式是 O(n)

22

3 . 下面程序段的时间复杂度是 O(n)

for (i=0; i

for (j=0; j

4．求两个n阶矩形的乘法C=A*B,其算法如下：

#define MAX 100

voidmaxtrixmult( int n, float a[MAX][MAX], float c[MAX][MAX]) { int i, j, k; float x; for( i=1; i<=n; i++)8 { for( j=1; j<=n; j++)

{ x=0;

for( k=1; k<=n; k++) x+=a[i][k]*b[k][j];

c[i][j]=x;

}

}

} 该算法的时间复杂度为 O(n)

5．通常用来表示时间算法的有以下六种多项式：

3

2

6．快速排序算法是基于分治策略的一个算法。其基本思想是，对于输入的子数组a[p:r],按以下3个步骤进行排序： 分解、递归求解、合并。

7. 合并排序算法的基本思想是 将待排序的元素分成大小大致相等的2个子集合，分别对两个子集合排序，最终将排好序的子集合合并成为所要求的集合。

最接近点对问题

问题

此问题分为一维，二维，三维的情况

1. 一维: 给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。

2. 二维：给定平面上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这是我们这一问题的重点

3. 三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。

基本思想

由于该问题的基本解法是去考察每个点和其他所有点的距离。因此它的时间复杂度是

O(n2),这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。

1. 因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算： 把直线分成两部分, s1s2,分别求出其最接近点的距离d1 d2。但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。 2. 鉴于此，二维的也可以用此方法进行计算：

把待计算的点s分成两部分s1 s2，分别求出其最接近点

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

学号： 姓名：

实验一 分治法求解**问题

一、实验目的

1.掌握分治法的设计思想并能熟练应用；

2.理解分治与递归的关系。

二、实验题目

在有序序列中(r1,r2,…,rn)中,存在序号i（1≤i≤n）,使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).

三、实验程序

//以(0,2,3,3,5,7,8,10,12,13)为例

#include<iostream>

using namespace std;

void PrintData(int data[],int length)

{

}

int Bisearch(int data[],int begin ,int last)

{

if ( mid < data[mid] ) int mid=(begin + last) /2; if (mid+1 == data[mid]) { } return mid; cout<<"有序序列是："; for (int i=0;i

算法分析与设计基础 （清华版）

Taken from \节选自《算法设计与分析基础》潘彦 译 蛮力法

就像宝剑不是撬棍一样，科学也很少使用蛮力。

——Edward Lytton (1830 - 1873)，leila，第二卷，第一章 认真做事常常是浪费时间。

——Robert Byrne，撞球大师，台球选手和作家

人们是这样描述它的：蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。这里的“力”是指计算机的能“力”，而不是人的智“力”。我们也可以用“直接做吧！”来描述蛮力法的策略。而且一般来说，蛮力策略也常常是最容易应用的方法。虽然巧妙和高效的算法很少来自于蛮力法，但我们不应该忽略它作为一种重要的算法设计策略的地位。第一，和其他某些策略不同，我们可以应用蛮力法来解决广阔领域的各种问题（实际上，它可能是惟一一种几乎什么问题都能解决的一般性方法）。具体来说，蛮力法常常用于一些非常基本、但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素，等等。第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法，它们多少具备一些实用价值，而且并不限制实例的规模。第三，

最接近点对问题

问题

此问题分为一维，二维，三维的情况

1. 一维: 给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。

2. 二维：给定平面上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这是我们这一问题的重点

3. 三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。

基本思想

由于该问题的基本解法是去考察每个点和其他所有点的距离。因此它的时间复杂度是

O(n2),这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。

1. 因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算： 把直线分成两部分, s1s2,分别求出其最接近点的距离d1 d2。但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。 2. 鉴于此，二维的也可以用此方法进行计算：

把待计算的点s分成两部分s1 s2，分别求出其最接近点

算法设计与分析期末作业

算法设计与分析期末作业

学校 专业班级 学号 学院 任课教师 学生姓名 第一题：简述递归算法、分治算法、动态规划算法、回溯算法的基本思想和步骤。

第二题：自拟一组数据，从插入排序、选择排序、合并排序、快速排序四种算法中任选两种算法，以图示描述方式描述算法求解过程。

第三题：从以下高级图算法(即宽度优先搜索算法、深度优先搜索算法、Kruskal算法、Prim算法、BellmanFord算法 、Dijkstra算法)中任选一种，结合现实情况构造一具体案例，并使用所选择的图算法以图示描述方式予以求解。

要求：在此作业模板下答题，电子文档及其打印文档均需上交，其中，电子文档发送至duyuanwei@foxmail.com，打印文稿于16周上课时上交。

1

算法设计与分析期末作业

第一题

答：一、递归算法：

（1）基本思想：把一个问题划分为一个或多个规模更小的子问题，然后用同样的方法解规模更小的子问题。(递归=递推+回归) （2）步