搜档网
当前位置:搜档网 › 算法设计与分析教学课件3

算法设计与分析教学课件3

Analysis and Design of Algorithms Analysis and Design of Algorithms Transform Coding

Chapter 3: Recursive Algorithm

School of Software Engineering ?Yanling Xu

Recursive Algorithm Recursive Algorithm

Recursion :

a procedure or subroutine, whose implementation references itself

E l 1R i l ti f !

Example 1: Recursive evaluation of n ! ?n initial condition 0

0)!1(1

!>=??

?=n n n n recurrence relation

C(n)=C(n 1)+1

Times of Basic operation for n ! C()C(n-1)+1 =[C(n-2)+1]+1 = C(n-2)+2=[C(n-3)+1]+2 = C(n-3)+3

Iterative Definition

C(n)=

n ……

=[C(n-n)+1]+n-1 = n

2

n

n n ×××××=)-(1...321!

Recursive Algorithm

Recursive Algorithm

Example 4: The Tower of Hanoi Puzzle

void hanoi(int n, int a, int b, int c)

{

if (n > 0)

if(0)

{

hanoi(n-1, a, c, b);

move(a,b);

(b)

hanoi(n-1, c, b, a);

}

}

C(n) ∈Θ (2n)

C(n) = 2C(n –1) + 1 =2n-1 for every n > 0

5

Recursive Algorithm

Recursive Algorithm

Example 5: permutation problem 排列问题

设计一个递归算法生成n个元素{r

,r2,…,r n}的全排列。

?设R={r1,r2,…,r n}是要进行排列的n个元素,R i=R-{r i}。

?集合X中元素的全排列记为perm(X)。

?(r i)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。

?R的全排列可归纳定义如下:

的排列可归纳定义如下

当n=1时,perm(R)=(r),其中r是集合R中唯一的元素;

)perm(R1),(r2)perm(R2),…,(r n)perm(R n)构成。

当n>1时,perm(R)由(r

1

6

Recursive Algorithm Recursive Algorithm

Example 5: permutation problem (‘cont)

template

void Perm(Type list[],int k,int m)

{// create all permutation of list [k: m ]with prefix list[0,k-1]onl one element to be done if (k ==m){//only one element to be done for (int i =0;i <=m;i++) putchar(list[i]); putchar(‘\n’); p ();}

else //several permutations for list[k: m ] are created by recursive for (i=k;i <=m;i++){ S (li t[k]li t[i])Swap (list[k],list[i]); Perm (list,k+1,m);

// Swap (list [k],list [i]);

} }

inline void Swap(Type &a,Type &b) {T t b t }

7

Type temp =a; a =b; b =temp; }

Recursive Algorithm

Recursive Algorithm

Example 6: partition problem 整数划分

将正整数n表示成一系列正整数之和:n=n1+n2+…+n k.

?其中n1≥n2≥…≥n k≥1,k≥1。

正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数q(n)。

? e.g. 正整数6有如下11种不同的划分, q(6)=11

6;

5+1;

4+2,4+1+1;

3+3,3+2+1,3+1+1+1;

2+2+2,2+2+1+1,2+1+1+1+1;

1+1+1+1+1+1

8

Recursive Algorithm

Recursive Algorithm

Example 6: partition problem (‘cont)

将最大加数n

1

不大于m的划分个数记作q(n,m)

()

可以建立q(n,m)的如下递归关系:

?q(n,n)=1+q(n,n-1);

正整数n的划分由n

1

=n的划分和n1≤n-1的划分组成。

?q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;

q()q()q()

正整数n的最大加数n

1不大于m的划分由n

1

=m的划分和n1≤m-1 的划

分组成。

9

Recursive Algorithm Recursive Algorithm

Example 6: partition problem (‘cont)

Recursive definition

?

?

??

=<==?+=1

,1)1,(1),(1),(m n m n m n n n q n n q m n q ???>>?+?1

)

,()1,(m n m m n q m n q int q(int n,int m){

if (n <1||m <1)return 0;if (n ==1||m ==1)return 1;if (n q(n if (n

10

Recursive Algorithm Recursive Algorithm

Important Recurrence Type

Decrease-by-one recurrences

A decrease-by-one algorithm solves a problem by exploiting a relationship between a given instance of size n and a smaller size n –1.

Example: n!

The recurrence equation for investigating the time efficiency of The recurrence equation for investigating the time efficiency of such algorithms typically has the form T(n) = T(n-1) + f(n)

Decrease-by-a-constant-factor recurrences Decrease by a constant factor recurrences

A decrease-by-a-constant algorithm solves a problem by dividing its given instance of size n into several smaller

instances of

size n/b,solving each of them recursively,and f ,g f y,then,if necessary,combining the solutions to the smaller instances into a solution to the given instance. Example: binary search.

11

The recurrence equation for investigating the time efficiency of

such algorithms typically has the form

T(n) = aT(n/b) + f (n)

Recursive Algorithm Recursive Algorithm

Decrease-by-a-constant-factor recurrences

–The Master Theorem

T (n ) = aT (n/b ) + f (n ),where f (n )∈Θ(n k ), k>=0

1. a < b k T (n ) ∈Θ(n k )

2. a = b k T (n ) ∈Θ(n k log n )

3.

a >

b k

T (n ) ∈Θ(n log b a )

Example:

T()T(/2)+1(l ) T(n) = T(n/2) + 1 Θ(logn) T(n) = 2T(n/2) + n Θ(nlogn) T(n)=3T(n/2)+n

log 312

T(n) 3 T(n/2) + n Θ(n 2)

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

算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程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 。 四、实验源代码

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析实验三

实验三分治算法(2) 一、实验目的与要求 1、熟悉合并排序算法(掌握分治算法) 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况,写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include const int N=100;//定义不可变常量N //各个函数的声明 void ScanTarget(int target[], int n, int head[], int tail[]); int CountHead(int head[]); void MergeSort(int a[], int head[], int tail[], int m); void MergePass(int x[], int y[], int s, int a[], int b[], int m); void Merge(int c[], int d[], int l, int m, int r); //主函数的定义 void main() { char a; do {

int target[N],head[N],tail[N]; int i=0,n,m; for(; i>n; cout<<"请输入需要排序的数列:" <>target[i]; ScanTarget(target,n,head,tail); m=CountHead(head);//调用求长度的函数 MergeSort(target,head,tail,m);//调用归并排序函数 cout<<"排序后:"<>a; } while(a!='n' && a!='N'); } void ScanTarget(int target[], int n, int head[], int tail[])//定义扫描待排数组的函数;{ int i,j=0,k=0; head[k]=0;

算法设计与分析实验报告

本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号: 05 学生姓名:俞梦真 指导教师:郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求

1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 归式,就是如何将原问题划分成子问题。 2.递归出口,递归终止的条件,即最小子问题的求解,可以允许多个出口。 3.界函数,问题规模变化的函数,它保证递归的规模向出口条件靠拢(2)递归与非递归之间如何实现程序的转换? (3)分析二分查找和快速排序中使用的分治思想。 答: 1.一般根据是否需要回朔可以把递归分成简单递归和复杂递归,简单递归一般就是根据递归式来找出递推公式(这也就引申出分治思想和动态规划)。 2.复杂递归一般就是模拟系统处理递归的机制,使用栈或队列等数据结构保存回朔点来求解。 (4)分析二次取中法和锦标赛算法中的分治思想。 二次取中法:使用快速排序法中所采用的分划方法,以主元为基准,将一个表划分为左右两个子表,左子表中的元素均小于主元,右子表中的元素均大于主元。主元的选择是将表划分为r

算法分析与设计

专业: 班级: 学号: 姓名: 日期: 2014年 11月 10日

48476Λn n 111+++=。 2、q(n ,m)=q(n ,n),m>=n 。 最大加数n1实际上不能大于n ,因此,q(1,m)=1。 3、q(n ,n)=1+q(n ,n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ,m)= q(n ,m-1)+q(n-m ,m),n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 (2)、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n

算法设计与分析试卷A及答案

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作; 高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高; 高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高; 把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。 2、 ①不能保证最后求得的解是最佳的;即多半是近似解。(少数问题除外) ②策略容易发现(关键:提取清楚问题中的维度), 而且运用简单,被广泛运用。 ③策略多样,结果也多样。 ④算法实现过程中,通常用到辅助算法:排序 3、解:① 因为:;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知: 1-10n n 2 2+是n ;的渐近表达式。 ② 因为:;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知: 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为:FBGDECA 。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】 5x =6x =7x =

算法设计与分析C++语言描述(陈慧南版)课后答案

第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数,程序1-2的while 循环体做了10次,程序1-3的while 循环体做了14141次(14142-2循环) 若考虑其他语句,则没有这么多,可能就601倍。 第二章 32P 2-8.(1)画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 (2)画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 (3 )画线语句的执行次数为 。O 。 (4)当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++, 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.(1)当1n ≥时,225825n n n -+≤,所以,可选5c =,01n =。 对于0n n ≥,22 ()5825f n n n n =-+≤,所以,22 582()n n n -+=O 。 (2)当8n ≥时,2222 582524n n n n n -+≥-+≥,所以,可选4c =,08n =。对于0n n ≥, 22()5824f n n n n =-+≥,所以,22582()n n n -+=Ω。 (3)由(1)、(2)可知,取14c =,25c =,08n =,当0n n ≥时,有22212582c n n n c n ≤-+≤,所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时,3 log log n n n <<,所以()20log 21f n n n n =+<,3 ()log 2g n n n n =+>。可选21 2 c = ,03n =。对于0n n ≥,()()f n cg n ≤,即()(())f n g n =O 。注意:是f (n )和g (n )的关系。 (2)当4n ≥时,2 log log n n n <<,所以2 2 ()/log f n n n n =<,2 2 ()log g n n n n =≥。可选1c =,04n =。对于0n n ≥,2 ()()f n n cg n <≤,即()(())f n g n =O 。 (3)因为log log(log )()(log ) n n f n n n ==,()/log log 2n g n n n n ==。当4n ≥时,log(log )()n f n n n =≥,

算法设计与分析考试重点归纳

算法设计考试重点整理 题型: 一选择题(10*2=20 分) 二简答题(4*5=20 分) 三应用题(3*10=30 分) 四算法题(3*10=30 分) 第一、二章 算法的定义:解某一特定问题的一组有穷规则的集合(对特定问题求解步骤的一种描述,是指令的有限序列) 算法的特征:1)有限性 2)确定性 3)输入 4)输出 5)能行性 算法分析的目的: 基本数据结构: 线性结构(元素之间是一对一的关系) 用顺序存储结构存储的线性表称为顺序表 用链式存储结构存储的线性表称为链表。 树形结构(元素之间是一对多的关系) 图(网)状结构(元素之间是多对多的关系) 栈:是一种只允许在表的一端进行插入或删除操作的线性表。允许进行插入、删除操作的一端称为栈顶,另一端称为栈底。当栈中没有数据元素时,称之为空栈。栈的插入操作称为进压栈,删除操作称为出栈。 队列:只允许在一端进行插入操作,在另一端进行删除操作的线性表。允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。当队列中没有数据元素时,称之为空队列。队列的插入操作称为进队或入队。队列的删除操作称为退队或出队。 树:树型结构是一种非线性结构,它用于描述数据元素之间的层次关系图 图:G=(V,E)是一个二元组

其中:V是图G中数据元素(顶点)的非空有限集集合 E是图G中关系的有限集合 由表达式求渐进表达式:例:(n2+n)/4 n2/4(增长速率最快的那一项) 时间复杂度的计算:(P23) 性能的比较:O(1) < O(log2n) < O(n) < O(nlog2n) =O(nlogn)< O(n2) < O(n3) < O(n k) < O(2n) 第三章 算法思想、稳定性、时间复杂度、应用、排序的移动次数: 希尔排序(数据结构P265):先将待排序列分割为若干个子序列分别进行直接插入排序;待整个序列基本有序时,再对全体记录进行一次直接插入排序。也称缩小增量的直接插入排序。 希尔排序的时间复杂度在O(nlog2n)和 O(n2)之间,大致为O 合并排序(P59):设初始序列含有n个记录,则可看成n个表长为1的有序表将这n个有序表两两合并,则可得n/2个表长为2的有序表再将这n/2个有序表两两合并,则可得n/4个长为4的有序表依次重复,直到对2个表长为n/2的有序表两两合并得1个表长为n的有序表为止。 堆排序、堆调整(P62): 初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。 基数排序(P71):不进行记录关键字的比较,借助多关键字排序的思想对单逻辑关键字进行排序。 算法时间复杂度稳定性 希尔排序 O不稳定 快速排序 O(nlogn)不稳定

算法设计与分析试卷(2010)

内部资料,转载请注明出处,谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 ( 选择1-4个正确的答案, 每题2分,共20分) (1)计算机算法的正确描述是: A .一个算法是求特定问题的运算序列。 B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。 C .算法是一个对任一有效输入能够停机的图灵机。 D .一个算法,它是满足5 个特性的程序,这5个特性是:有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 (2)影响程序执行时间的因素有哪些? A .算法设计的策略 B .问题的规模 C .编译程序产生的机器代码质量 D .计算机执行指令的速度 (3)用数量级形式表示的算法执行时间称为算法的 A .时间复杂度 B .空间复杂度 C .处理器复杂度 D .通信复杂度 (4)时间复杂性为多项式界的算法有: A .快速排序算法 B .n-后问题 C .计算π值 D .prim 算法 (5)对于并行算法与串行算法的关系,正确的理解是: A .高效的串行算法不一定是能导出高效的并行算法 B .高效的串行算法不一定隐含并行性 C .串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 (6)衡量近似算法性能的重要标准有: A .算法复杂度 B .问题复杂度 C .解的最优近似度 D .算法的策略 (7)分治法的适用条件是,所解决的问题一般具有这些特征: A .该问题的规模缩小到一定的程度就可以容易地解决; B .该问题可以分解为若干个规模较小的相同问题; C .利用该问题分解出的子问题的解可以合并为该问题的解 D .该问题所分解出的各个子问题是相互独立的。 (8)具有最优子结构的算法有: A .概率算法 B .回溯法 C .分支限界法 D .动态规划法 (9)下列哪些问题是典型的NP 完全问题: A .排序问题 B .n-后问题 C .m-着色问题 D .旅行商问题 (10)适于递归实现的算法有: A .并行算法 B .近似算法 C .分治法 D .回溯法 二、算法分析题(每小题5分,共10分) (11)用展开法求解递推关系: (12)分析当输入数据已经有序时快速排序算法的不足,提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

《算法设计与分析》实验一

学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日

实验一:递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习,旨在加深学生对该算法原理的理解,提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1.实验前复习课程所学知识以及阅读和理解指定的课外阅读材料; 2.学生独自完成实验指定内容; 3.实验结束后,用统一的实验报告模板编写实验报告。 4.提交说明: (1)电子版提交说明: a 需要提交Winrar压缩包,文件名为“《算法设计与分析》实验一_学号_姓名”, 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹, 其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 (2)打印版提交说明: a 不可随意更改模板样式。 b 字体:中文为宋体,大小为10号字,英文为Time New Roman,大小为10号 字。 c 行间距:单倍行距。 (3)提交截止时间:2018年10月10日16:00。 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: 【必做题】 (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份?

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:120分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分,共计30 分) 1、用O、Ω与θ表示函数f与g之间得关系______________________________。 2、算法得时间复杂性为,则算法得时间复杂性得阶为__________________________。 3、快速排序算法得性能取决于______________________________。 4、算法就是_______________________________________________________。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是_________________________。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是_____情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越___________,结果就越有价值。。 8、____________________________就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指____________________________________________________________________________________________________________________。 10、回溯法在问题得解空间树中,按______________策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计30分) 1、试述回溯法得基本思想及用回溯法解题得步骤。 2、有8个作业{1,2,…,8}要在由2台机器M1与M2组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M1与M2加工作业i所需得时间分别为: M110 2 8 12 6 9414

《算法设计与分析》递归算法典型例题

算法递归典型例题 实验一:递归策略运用练习 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份? 源程序: (3)出售金鱼问题:第一次卖出全部金鱼的一半加二分之一条金鱼;第二次卖出乘余金鱼的三分之一加三分之一条金鱼;第三次卖出剩余金鱼的四分之一加四分之一条金鱼;第四次卖出剩余金鱼的五分之一加五分之一条金鱼;现在还剩下11条金鱼,在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼? (4)某路公共汽车,总共有八站,从一号站发轩时车上已有n位乘客,到了第二站先下一半乘客,再上来了六位乘客;到了第三站也先下一半乘客,再上来了五位乘客,以后每到一站都先下车上已有的一半乘客,再上来了乘客比前一站少一个……,到了终点站车上还有乘客六人,问发车时车上的乘客有多少? (5)猴子吃桃。有一群猴子摘来了一批桃子,猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只,以此类推),第九天正好吃完,问猴子们摘来了多少桃子? (6)小华读书。第一天读了全书的一半加二页,第二天读了剩下的一半加二页,以后天天如此……,第六天读完了最后的三页,问全书有多少页? (7)日本著名数学游戏专家中村义作教授提出这样一个问题:父亲将2520个桔子分给六个儿子。分完后父亲说:“老大将分给你的桔子的1/8给老二;老二拿到后连同原先的桔子分1/7给老三;老三拿到后连同原先的桔子分1/6给老四;老四拿到后连同原先的桔子分1/5给老五;老五拿到后连同原先的桔子分1/4给老六;老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子? 四、实验过程 (一)题目一:…… 1.题目分析 由已知可得,运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数,且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天, If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;

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

算法设计与分析课程实验项目目录 学生:学号: *实验项目类型:演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。

本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日~6月30日温度24℃ 1.实验目的和要求: 熟悉蛮力法的设计思想。 2.实验原理和主要容: 实验原理:蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容:以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序,实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的: S END +MORE MONEY . 这里有两个前提假设: 第一,字母和十进制数字之间一一对应,也就是每个字母只代表一个数字,而且不同的字母代表不同的数字;第二,数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意,解可能并不是唯一的,不同人的解可能并不相同。3.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。)

该算法程序代码如下: #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数:\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l

算法设计与分析 王红梅 胡明 习题答案

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现 在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 ??m=n ???n=r ??r=m-n 3?输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C ++描述。 编写程序,求n 至少为多大时,n 个“1”组成的整数能被2013整除。 #include using namespace std; int main() { double value=0; 图 七桥问题

for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说:神6天创造天地万有,第7日安歇。为什么是6天呢?任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间? 由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如: 第一趟:甲,乙过桥且甲回来

算法设计与分析实验报告 统计数字问题

算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4.实现具体的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2, (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0,1,2, (9) 三.程序算法 将页码数除以10,得到一个整数商和余数,商就代表页码数减余数外有多少个1—9作为个位数,余数代表有1—余数本身这么多个数作为剩余的个位数,此外,商还代表1—商本身这些数出现了10次,余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int s[10]; //记录0~9出现的次数 int a[10]; //a[i]记录n位数的规律 void sum(int n,int l,int m) { if(m==1) {

int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i

南京邮电大学算法设计实验报告——动态规划法

实验报告 (2009/2010学年第一学期) 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的:加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的最长公共子序列问题。 任务:用动态规划法实现求两序列的最长公共子序列,其比较结果可用于基因比较、文章比较等多个领域。 要求:掌握动态规划法的思想,及动态规划法在实际中的应用;分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件:计算机 软件:Visual C++

三、实验原理及内容(包括操作过程、结果分析等) 1、最长公共子序列(LCS)问题是:给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n},要求找出X和Y的一个最长公共子序列。 例如:X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列,检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法,求解时间为指数级别的,因此不可取。 2、分析LCS问题特征可知,如果Z={z1,z2,……,z k}为它们的最长公共子序列,则它们一定具有以下性质: (1)若x m=y n,则z k=x m=y n,且Z k-1是X m-1和Y n-1的最长公共子序列; (2)若x m≠y n且x m≠z k,则Z是X m-1和Y的最长公共子序列; (3)若x m≠y n且z k≠y n,则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题,分解为求解较小规模的问题: 若x m=y m,则进一步分解为求解两个(前缀)子字符序列X m-1和Y n-1的最长公共子序列问题; 如果x m≠y n,则原问题转化为求解两个子问题,即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列,取两者中较长者作为X和Y的最长公共子序列。 由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度,由上述分析可得如下递推式: 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见,最长公共子序列的求解具有重叠子问题性质,如果采用递归算法实现,会得到一个指数时间算法,因此需要采用动态规划法自底向上求解,并保存子问题的解,这样可以避免重复计算子问题,在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解(即最长公共子序列),还需要一个二维数组s[][],数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到,从而可以得到最优解的当前解分量(即最长公共子序列中的当前字符),最终构造出最长公共子序列自身。

算法设计与分析试题(三合一).(优选)

西安电子科技大学网络教育 2010学年上学期期末考试模拟试题一 一、 填空题(每小题4分,共计40分) 1. 通常只考虑三种情况下的时间复杂度,即 情况、 情况和 情况 下的时间复杂度,分别记为T max (N)、T min (N) 和T avg (N),实践表明可操作性最好且最有实 际价值的是 情况下的时间复杂度。 2. n n 1032 的渐近表达式是 , )log(3n 的渐近表达式是 。 3. 根据符号O 的定义易知O(1)=O(2),用O(1)和O(2)表示同一个方法时,差别仅在于其中 的 。 4. 递归算法是指 的算法, 递归函数是指 的函数。 5. 贪心算法总是做出在当前看来_____________的选择,也就是说,贪心算法并不从整体最优考虑它 所做出的选择只是在某种意义上的________________。 6. 如果某问题具有________________________和___________________________两个重要性质,该问题可以用贪心算法求解。 7. 单源最短路径问题适合用_______________算法来求解、0-1背包问题适合用_____________算法来 求解。 8. 分治法是将一个规模为n 的问题分解为k 个规模________的子问题,这些子问题___________且与 原问题__________。递归地求解这些子问题,然后将各个子问题的解_________得到原问题的解。 9. 动态规划算法的两个基本要素是____________________和____________________。 10.___ 算法可以有效地解凸多边形最优三角剖分问题,而____________算法是求解最优 装载问题的有效方法。 二、简答题(每小题10分,共计40分) 1. 如果只需要求解问题的最优值,动态规划算法步骤是什么?如果需要构造最优解,则还需要加上什么步骤? 2. 请简述什么是贪心选择性质 3. 请简述什么是最小生成树。 4. 请简述贪心算法比动态规划算法效率高的原因。

相关主题