算法设计与分析作业

最接近点对问题

问题

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

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

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

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

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

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

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

基本思想

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

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

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

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

最接近点对问题

问题

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

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

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

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

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

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

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

基本思想

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

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

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

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

《算法分析与设计》作业

1、考虑0?xi?1,而不是xi∈{0，1}的连续背包问题。一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包内装如此物品的一部分。

(a) 对于n=3，w=[100,10,10]，p=[20,15,15]，以及c=105，上述装入法获得结果是什么？

(b)证明这种贪婪算法总能获得最优解。 (c) 用伪代码描述此算法。

答：（a）利用贪婪算法，按价值密度考察的背包为w2，w3，w1；

背包w2和w3重20，还可以容纳85，由于0?xi?1，背包w1还可以装入x1=0.85，则背包内物品总价值为

15+15+20*0.85＝47.

（b）假设已按价值密度排好序，考察w1,w2,……,wi，……，

对应的价值为p1,p2,……,pi,……

如果装到pi-1再装pi时，恰好要取xi个wi。（0?xi?1,） 因为比它价值密度大的都已装载完，所以此时获得的为最优解。 （c）算法描述如下： template

int ContainerLoading( int x[], T w[], T c, int n ) {

int *t = new int[n+1]; Indi

算法分析与设计大作业

《回溯法计算皇后跳棋》

班级： 学号：

姓名：

指导老师：

得分：

一、 问题陈述：

在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。要求在n×n格的棋盘上放置n个皇后，任何两个皇后不放在同一行或同一列或同一斜线上。

二、 回溯法基本思想：

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：

1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性

回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明确的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。

三、 算法描述：

Q Q Q Q

第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.掌握分治法的设计思想并能熟练应用；

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个数字的和，求一个列表的最大元素，等等。第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法，它们多少具备一些实用价值，而且并不限制实例的规模。第三，

算法设计与分析期末作业

算法设计与分析期末作业

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

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

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

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

1

算法设计与分析期末作业

第一题

答：一、递归算法：

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

算法设计与分析 复习 算法与程序

算法：解决问题的方法或过程，是满足下述性质的指令序列。

输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。

确定性：组成算法的每条指令清晰、无歧义。

有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

程序：

程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。

例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

描述算法与算法设计 算法分析的基本原则 算法分析的基本原则

时间复杂度(time complexity)T(n) 时间复杂度指程序执行时所用的时间。

在使用解析方法时程序p的时间复杂度表示为输入量的函数T。 机器独立的分析方法-解析的方法.

在解析地分析时间复杂度时,使用以下两种时间单位并计算：

操作计数(operation count):算法的基本操作 (程序)步计数(step count):分析全部程序

要点:基本操作或程序步的执行时间必须是常数。 最好，最坏和平均情形时间复杂度

当长度