澳门mgm官网算法期末考试练习题,大学算法深入

2019-12-31 05:59 来源:未知

转载:

一、选择题

高校算法深入分析与规划复习总结

分类: 【大学课程之算法解析与两全】2013-06-08 11:49 1900人阅读 评论(0) 收藏 举报

算法编制程序语言

 

目录(?)[-]

  1. 第1章 绪论
  2. 第3章 蛮力法
  3. 第4章  分治法
  4. 第5章 减治法
  5. 第6章 动态规划法
  6. 第7章 贪心法
  7. 第8章 回溯法
  8. 第9章 分治限界法

 

大学算法深入分析与布置复习总计

 

为了拿大学的那喜剧的学分,好好弄懂以下有所知识点吧。把导师的复习的总纲,刻意汇总了有着考试之处,方便童鞋们复习。不喜勿喷!!!

这本书是《算法设计与深入分析》 王红梅 编慕与著述

总共有以下12章,大家学了1、3、4、5、6、7、8、9

分级是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法

 

 

1.算法解析中,记号O表示(B),灯号Ω标价出卖(A),暗号Θ表示(D)

第1章 绪论

考点:

 

1、  算法的5个重视特点。(P3)

答:输入、输出、有穷性、确定性、可行性

2、  描述算法的八种艺术分别是什么,有何优短处。(P4)

答:

1.      自然语言 优点:轻易通晓;劣势:轻便并发二义性,並且算法都很冗长。

2.      流程图       优点:直观易懂;缺点:严密性比不上程序语言,灵活性比不上自然语言。

3.      程序设计语言 优点:用程序语言描述的算法能由Computer直接奉行;弱点:抽象性差,是算法设计者拘泥于描述算法的实际细节,忽视了“好”算法和不利逻辑的关键,别的,还须要算法设计者精晓程序设计语言及其编制程序技术。

伪代码    优点:表明手艺强,抽象性强,轻巧驾驭

 

3、  理解非递归算法的岁月复杂性分析。(P13State of Qatar

 要点:对非递归算法时间复杂性的分析,关键是起家一个表示算法运营时刻的求和表明式,然后用渐进符号表示这么些求和表明式。

非递归算法深入分析的相通步骤是:

(1)      决定用哪个(或如何)参数作为算法难题规模的度量。

(2)      寻觅算法的着力语句。

(3)      检查基本语句的施行次数是或不是只依据难题规模。

(4)      创设基本语句实行次数的求和表达式。

(5)      用渐进符号表示那几个求和表明式。

 

[例1.4]:求数组最小值算法

 int ArrayMin(int a[ ], int n)

 {

      min=a[0];

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

         if (a[i]<min) min=a[i];

      return min;

 }

主题素材规模:n

基本语句: a[i]<min

T(n)= n-1=O(n)

 

4、  明白扩大递归技巧和通用分治递推式的应用。(P15)

扩展递归技巧:

 

 

 

澳门mgm官网 1

澳门mgm官网 2

澳门mgm官网 3

通用分支递归式:

 

 

 澳门mgm官网 4

澳门mgm官网 5

 

5、  习题1-4,习题1-7

统筹算法求数组中相差不远的八个因素(称为最周围数)的差。要求交付伪代码描述,并用生机勃勃组例子进行追踪验证,写出评释进程。

(1)伪代码

1.   令最小间隔min等于数组头三个成分Rubicon[0]和R[1]的差的相对值;

2.   从i=0循环至i<n-1,对于各种奥迪Q3[i]

2.1     分别求其与j=i+1至j<n的数的差的相对值;

2.2     如若此值小于最小间距,则令新的小小间隔为此值;

3.   输出最小距离。

(2)用实例实行追踪验证

R[6]={10,5,11,16,30,14},n=6;

Min=|10-5|=5;

i=0,j=1, |R[i]-R[j]|=|10-5|=5;

   j=2,|R[i]-R[j]|=|10-11|=1<min;min=1;

   j=3, |R[i]-R[j]|=|10-16|=6;

   j=4, |R[i]-R[j]|=|10-30|=20;

   j=5, |R[i]-R[j]|=|10-14|=4;

i=1,j=2, |R[i]-R[j]|=|5-11|=6;

   j=3, |R[i]-R[j]|=|5-16|=11;

   j=4, |R[i]-R[j]|=|5-30|=15;

   j=5, |R[i]-R[j]|=|5-14|=9;

i=2,j=3, |R[i]-R[j]|=|11-16|=5;

   j=4, |R[i]-R[j]|=|11-30|=19;

   j=5, |R[i]-R[j]|=|11-14|=3;

i=3,j=4, |R[i]-R[j]|=|16-30|=14;

   j=5, |R[i]-R[j]|=|16-14|=2;

i=4,j=5, |R[i]-R[j]|=|30-14|=16;

终极输出min=1

7、使用扩张递归本事求解下列递推关系式

(1)

澳门mgm官网 6

 

 

(2)

澳门mgm官网 7

 

 

 

A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界

第3章 蛮力法

 

1、  精晓蛮力法的计划思想:

蛮力法注重的主导才干——扫描本事,即采取自然的政策将待求解难题的保有因素依次拍卖二回,进而寻觅难点的解;

首要——依次拍卖全部因素。

 

2、  蛮力法的象征算法及其时间复杂度:

依次查找,O(n)

串匹配(BF O(nm)* ,KMPO(n+m) , BMO(nm)*

分选排序,O(n2)

冒泡排序,O(n2)

浮动排列对象(排列难点),O(n!)

生成子集(组合问题),O(2n)

0/1手拿包 属于组合难题。

任务分配,拉萨顿回路,TSP难题 归于排列难题。

近些年对难点 O(n2),凸包难题 O(n3)

3、  通晓BF和KMP算法的法则,可以画出比较进程。P71习题3的4。必要交付朝气蓬勃串字符串,能够求出对应的next数组,并能使用KMP算法实行比较合营。

4、  驾驭接纳排序和冒泡排序算法描述和岁月复杂性,要求能够写出伪代码。(P56-58)

分选排序

算法描述:选取排序发轫的时候,扫描整个系列,找到任何系列的矮小记录和类别中的第黄金年代记下沟通,进而将小小记录停放它在有序区的尾声地点上,然后再从第一个记录开始扫描种类,找到n-1个类别中的最小记录,再和第三个记录沟通地点。日常地,第i趟排序从第i个记录发轫扫描类别,在n-i+1个记录中找到关键码最小的笔录,并和第i个记录沟通作为长久以来体系的第i个记录。

时光复杂性:O(n2)

伪代码:

 

 澳门mgm官网 8

冒泡排序

算法描述:冒泡排序起首的时候扫描整个体系,在围观进程中两两相比较相邻记录,如若反序则交流,最后,最大记录就会被“沉到”了连串的末梢一个地点,第二趟扫描将第二大记录“沉到”了尾数第4个职位,重复上述操作,直到n-1趟扫描后,整个系列就排好序了。

冒泡排序,O(n2)

***澳门mgm官网 9


 

5、  算法设计题:习题3-3,3-6,3-8,3-11,3-13

3-3 对于KMP算法中求next数组难题,设计叁个蛮力算法,并深入分析其时间质量。

 

[cpp] view plaincopy

 

  1. voidGetNext(char T[ ], int next[ ])  
  2. {  
  3.    next[1]=0;  
  4.    next[2]=1;  
  5.    j=T[0],k=0;  
  6.    for(;j>2;j--){  
  7.         for(n=j-2;n>=1;n--卡塔尔{//n为要比较的前缀的尾声二个字符的下标  
  8.                m=j-n;//m为要比较的后缀的首先个字符的下标  
  9.                for(i=1;i<=n;i++)  
  10.                {  
  11.                        if(T[i]!=T[m+i-1])break;  
  12.                }  
  13.                if(i==n+1){next[j]=n+1;break;}  
  14.          }  
  15.         if(n==0)next[j]=1;  
  16.          }  
  17. }  

 

3-4 假若在文书“ababcabccabccacbab”中搜索模式“abccac”,求分别选择BF算法和KMP算法进行串相称进度中的字符比较次数。

澳门mgm官网 10

澳门mgm官网 11

测算,用BF算法后生可畏共要拓宽3+1+4+1+1+6+1+1+1+6=21遍相比较方能相配出

 

KMP算法:next[]={,0,1,1,1,1,2};

澳门mgm官网 12

想见,用KMP算法意气风发共要扩充3+4+6+5=十伍遍相比方能相称出

 

参照代码如下:

排列最后存款和储蓄在长短为n的阶乘,成分类型为指针的数组中,数组指向一个排列,具体的排列数据存款和储蓄在数组中。

 

[cpp] view plaincopy

 

  1. int fabs(int n)  
  2. {  
  3.        int r=1;  
  4.        for(inti=n;i>1;i--)  
  5.               r=r*i;  
  6.        return r;  
  7.    
  8. }  
  9.    
  10. //排列存储在数组中  
  11. void getArrangement(int**&s,int n)  
  12. {  
  13.        int * p,*q;  
  14.        int * *s1;  
  15.        int i,j,k,l,m,o;  
  16.        s=new int *[1];  
  17.        s[0]=newint[1];  
  18.        s[0][0]=1;  
  19.        for(i=2;i<=n;i++)  
  20.               {  
  21.                      j=0;  
  22.                      o=0;  
  23.                      m=fabs(i-1);  
  24.                      s1=newint *[fabs(i)];  
  25.                      while(o<m)  
  26.                      {  
  27.                             q=p=s[o];  
  28.                             for(k=i-1;k>=0;k--)  
  29.                             {                                   
  30.                                    s1[j]=newint[i];  
  31.                                    for(l=0;l<i;l++)  
  32.                                    {  
  33.                                           if(l==k){s1[j][l]=i;}  
  34.                                           else{  
  35.                                                  s1[j][l]=*p;  
  36.                                                  p++;}  
  37.                                    }  
  38.                                    j++;  
  39.                                    p=q;  
  40.                             }  
  41.                             o++;  
  42.                             delete[] q;  
  43.                      }  
  44.                      delete[]s;  
  45.                      s=s1;  
  46.               }  
  47. }  

 

 

3-8对此三个平面上n个点的集结S,设计蛮力算法求集结S的凸包的二个终极。

点集合中最左边或然最左边的点一定是凸包的二个极限,则求凸包的极端的标题转变为求点的x坐标最大或比非常的小的点

 

[cpp] view plaincopy

 

  1. int getPole(int x[],int y[],int n)  
  2. {  
  3.        int r=0;  
  4.        for(inti=0;i<n;i++)  
  5.        {  
  6.               if(x[i]>x[r])r=i;  
  7.        }  
  8.        return r;  
  9. }<span style="font-weight: bold; "> </span>  

 

3-11 设总结法生成在n个成分中隐含k个成分的具有结成对象。

二种思路:

1、  生成全部的整合,在组成人中学找成分个数为k个的三结合。

伪代码:

1.起始化二个尺寸为n的比特串s=00…0并将相应的子集输出;

 2.for(i=1; i<2n; i++卡塔尔国   //注意不可能书写成i<=2n

    2.1  s++;

    2.2  推断s中1的个数,若为k,则将s对应的子集输出;

 

2、  使用k层嵌套循环生成成分个数为k个的重新组合。

设k=3;n个成分存款和储蓄在数组a[]中;

伪代码:

for (i=1; i<n-2; i++)

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

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

      输出a[i]a[j]a[k]整合的整合。

 

3-13United States有个体验店叫7-11以此直营店早先是每一日7点开门,早晨11点关门

然方今后是全天24钟头运维。有一天,有个人过来这一个专营店,买了4件物品

售货员拿起计算器敲了弹指间,说:总共是$7.11买主开玩笑说:所以你们公司就叫7-11?营业员未有理他,说:当然不是,小编是把它们的标价相乘之后获得的。

买主说:相乘?你应有把他相加才对。营业员说,作者弄错了。接着又算了三遍,结果让三个人吃惊的是:总计结果也是$7.11请问,那4件商品的价位是多少?

仿照效法代码:

 

[cpp] view plaincopy

 

  1. #include<iostream.h>  
  2. #include <stdio.h>  
  3. int main()  
  4. {  
  5. long i,j,k,m;  
  6.    
  7. for (i=1; i <=711/4 ; i++)  
  8. {  
  9. for (j=i; j <=711/3 ; j++)  
  10. {  
  11. for (k=j; k <=711/2 ; k++)  
  12. {  
  13. m=711-i-j-k;  
  14. if (i*j*k*m==711*1000000)  
  15. {  
  16. cout<<i<<endl<<j<<endl<<k<<endl<<m<<endl;  
  17.             }  
  18. }  
  19. }  
  20. }  
  21. return 0;  
  22. }  

出口结果为:价格分别是1.2   1.25   1.5     3.16

 

 

 

2.以下关于渐进暗号的属性是精确的有:(A)

第4章  分治法

 

询问分治法的布置性观念

陈设观念:将供给解的原难点分开成k个异常的小圈圈的子难点,对这k个子难点分别求解。借使实难点的层面照旧相当不足小,则再将各样子难点分割为k个规模越来越小的子难点,如此讲解下来,直到难点规模丰富小,超级轻易求出其解为止,再将子难题的解合併为一个更加大局面包车型地铁题目标解,自底向上稳步求出原难点的解。

手续:(1)划分(2)求解子难点(3)合并

 

分治法的表示算法及时间复杂度:

合併列排在一条线序,赶快排序,最大子段和,近日对难点,凸包难点,那多种难点的分治算法的日子复杂度为O(nlog2n)

棋盘覆盖,循环赛日程安插为O(4k)

 

支合作并列排在一条线序和急迅排序算法的算法伪代码。(P78-83)

归拢列排在一条线序:

澳门mgm官网 13

 

算法中数组r中寄存原始数据,r1在中间进程中蕴藏排序后的数码,s指需排序数组的苗头下标,t指需排序数组的完工下标。最后排序后的多寡依然存款和储蓄在r数组中。

澳门mgm官网 14

 

急速排序:

澳门mgm官网 15

澳门mgm官网 16

 

 

左右最大子段和难点的算法伪代码。(P83-85)

澳门mgm官网 17

澳门mgm官网 18

 

 

对此待排体系(5, 3, 1, 9, 8, 2, 4, 7),画出急迅排序的递归运转轨道。

按升序排列

起来系列:5,3,1,9,8,2,4,7

第一遍私分:4,3,1,2,5,8,9,7

第一次私分:2,3,1,4,5,8,9,7

其一遍私分:1,2,3,4,5,8,9,7

第八遍私分:1,2,3,4,5,7,8,9

排序实现,玉石白字体为每一回划分的轴值

 

在稳步连串9(r1,r2,```, rn)中,存在序号i ( 1<=i<=n卡塔尔国,使得ri = i, 请设计三个分治算法找到这些元素,须要算法在最坏情形下的时刻质量为O(log2n).

参照代码:

 

[cpp] view plaincopy

 

  1. #include<iostream.h>  
  2. int findr(ints[],int begin,int end)  
  3. {  
  4.        if(begin==end){  
  5.               if(s[begin]==begin) return begin;  
  6.               else return 0;  
  7.        }else  
  8.        {  
  9.               int m=(begin+end)/2;  
  10.               if(s[m]>m) return findr(s,begin,m-1);  
  11.               else if (s[m]==m)return m;  
  12.               else return findr(s,m+1,end);  
  13.        }  
  14.    
  15. }  
  16. void main()  
  17. {  
  18.        int s[]={0,1,1,2,4,6,8};  
  19.        cout<<findr(s,1,6)<<endl;  
  20. }  

 

A  f(n) =Θ(g(n)),g(n) =Θ(h(n)) ⇒f(n) =Θ(h(n))

第5章 减治法

 

问询减治法的设计理念

两全观念:原难题的解只设有于当中三个不大范围的子难题中,所以,只须要解在那之中叁个一点都不大圈圈的子难点就能够赢得原难点的解。

 

精晓运用减治法的意味难点及时间复杂度:

折半招来,二叉树查找,堆排序,选用主题材料,淘汰赛亚军难点,假币难题;

上述难点的小时复杂度,如若减治是每一次减小为原来规模的百分之二十五,则时间复杂度平常为O(log2n)

 

支配折半物色的算法伪代码描述及实际事例的检索进程,会依据折半查找的进程成立判断树。(P98-100)

澳门mgm官网 19

 

会依靠已知多少系列创制二个二叉查找树。(P100)

澳门mgm官网 20

 

操纵堆排序算法中的三种调节堆和新建堆的主意:筛选法和插入法(P101-105)

堆调解问题:将三个无序类别调度为堆

(1)筛选法调节堆

        关键难题:完全二叉树中,根结点的左右子树均是堆,如何调解根结点,使任何完全二叉树成为一个堆?    澳门mgm官网 21

 

(2)插入法调节堆

关键难点是:在堆中插入一个结点,如何调治被插入结点,使全部完全二叉树仍为四个堆?

澳门mgm官网 22

 

驾驭采纳难点的算法的伪代码(P105-106)

 

 澳门mgm官网 23

 

习题5-1,算法设计题

习题5-4,给出任性生龙活虎组数据,能分别用筛选法和插入法写出创设堆的经过,并用三种艺术开展堆排序。

对(47,5,26,28,10)举行筛选堆排序,使用大根堆,产生升序 ,列出每趟筛选后的系列

变异大根堆的经过(先把数组直接表示成完全二叉树):

47,5,26,28,10(叶子结点,不用筛选)

47,5,26,28,10 (叶子结点,不用筛选)

47,5,26,28,10 (叶子结点,不用筛选)

47,5,26,28,10

47,28,26,5,10 (5与多个儿女子中学的大者比较,5小,沟通个方式置)

47,28,26,5,10 (47与五个孩子中的大者相比较,47大,不用沟通地点)

47,28, 26, 5 ,10 (大根堆)

10,28, 26, 5 , 47 (抽出堆顶成分后的队列)

10,28, 26, 5 , 47 (筛选)

28, 10 , 26, 5 , 47

28, 10 , 26, 5 , 47 (大根堆)

5, 10 , 26, 28, 47 (抽取堆顶成分后的类别)

5, 10 , 26, 28, 47 (筛选)

26, 10 , 5, 28, 47

26, 10 , 5, 28, 47 (大根堆)

5, 10 , 26, 28, 47 (抽取堆顶成分后的队列)

5, 10 , 26, 28, 47 (筛选)

10, 5 , 26, 28, 47

10, 5 , 26, 28, 47 (大根堆)

5, 10 , 26, 28, 47 (抽取堆顶成分后只剩一个值,停止算法)

对(47,5,26,28,10)举办插队法生成大根堆

47

47 5

47 5 26

47 28 26 5

47 28 26 5 10

 

B  f(n) =O(g(n)),g(n) =O(h(n)) ⇒h(n) =O(f(n))

第6章 动态规划法

 

问询动态规划法的规划观念

设计理念:将待求解难点分解成若干个互相重叠的子难题,每种子难点对应决策进程的三个等级,将子难点的解求解叁回并填写表中,当须求再一次求解此子难点时,能够通过查表得到该子难题的解而不要再行求解。

步骤:

将原来难点解释为相互重叠的子难题,分明动态规划函数;

求解子难点,填表;

听大人讲表,自底向上总括出原难点的解。

 

左右能够用动态规划法息灭的难点及时间复杂度:

TSP,多段图的最短路径难题,0/1手拿包,最长公共子种类难点,最优二叉查找树,相符串相称难题;

多段图的最短路线难题: O(n+m卡塔尔(قطر‎

0/1单肩包难点: O(n×CState of Qatar

 

支配多段图的最短路线难点的动态规划算法及具体完毕(P121-123),习题6-2

澳门mgm官网 24

 

澳门mgm官网 25

 

动态规划函数为:

cost[i]中寄存顶点i到顶点的最短路线长度

cost[i]=min{C[i][j]+cost[j]} (i≤j≤n且极点j是极点i的邻接点卡塔尔

path[i]=使C[i][j]+cost[j]最小的j

先构造cost数组和path数组

 

 澳门mgm官网 26

通晓0/1手拿包难题的动态规划算法及现实贯彻(P123-126),习题6-3

澳门mgm官网 27

澳门mgm官网 28

 

 

例题:用动态规划法求如下0/1信封包难题的最优解:有5个货物,其重量分别为(3,2,1,4,5),物品的价值分别为(25,20,15,40, 50),背包体量为6。写出求解进度。

0/1马鞍包难点的动态规划函数为:

澳门mgm官网 29

 

V(i,jState of Qatar表示把前i个货色归入体积为j的单肩包中的最大价值和。

填表进程:

澳门mgm官网 30

放入手袋中的物品的求解进程:则65表示把5个物品归入容积为6的手拿包中的最大价值和。

i=5,j=6;  v[5][6]>v[4][6],x[5]=1, j=6-w[5]=1

i=4,j=1; v[4][1]=v[3][1], x[4]=0

i=3,j=1; v[3][1]>v[2][1], x[3]=1, j=1-w[3]=0

i=2,j=0; v[2][1]=v[1][0], x[2]=0

i=1,j=0; v[1][0]=v[0][0], x[1]=0

结果是把首个和第5个归入了公文包

左右最长公共子类别难题的动态规划法算法及现实落到实处(P126-128),习题6-4

澳门mgm官网 31

 

求X=“xzyzzyx”和Y=“zxyyzxz”系列的最长公共子体系的动态规划函数为:

澳门mgm官网 32

L[i][j]表示X中前i个要素和Y中前j个成分结合的行列的最长公共子类别的尺寸。

为了鲜明具体的最长公共子类别,必要同有的时候候计算S[i][j]的值,S[i][j]表示在总计L[i][j]的经过中的找寻状态。

澳门mgm官网 33

 

澳门mgm官网 34  

澳门mgm官网 35
子系列为斜箭头所标示的行或列:X[2],X[3],X[6] ,X[7]或Y[1], Y[3], Y[4] , Y[6]最长公共子序列的长短为4

即为:zyyx

 

 

 

 

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

第7章 贪心法

问询贪心法的布置性看法

 

贪心法在解决难题的政策上只见树木,只依据近期已部分音信就做出局地最优选拔,並且只要做出了选取,不管未来有怎么着结果,那一个选项都不会转移。

贪心法的关键在于决定贪心计谋。

 

操纵能够用贪心法化解的难点:

TSP问题中的三种缓和格局:近期领点战略,最短链接战术

最小生成树难点的二种算法:近来极端计谋(Prim算法),最短边战术(Kruskal算法)

马鞍包难点,活动安顿难题,多机调整难题,哈夫曼编码。

 

左右最小生成树的两种贪心算法:prim算法和kruskal算法(P145-148),给出具体的例子,能够用二种方法画出树的更动进度。

澳门mgm官网 36

 

 澳门mgm官网 37

 

调整托特包难题的贪婪算法(P148-151),给出三个切实可行的事例,可以写出解决难题的长河。习题7-2

主题素材:求如下包包难题的最优解:有7个货物,价值P=(10,5,15,7,6,18,3卡塔尔,重量w=(2,3,5,7,1,4,1卡塔尔国,背包体积W=15.

解决方式:

先对货物的单位重量价值依照降序排列

物品重量

物品价值

物品价值/物品重量

1

6

6

2

10

5

4

18

4.5

5

15

3

1

3

3

3

5

1.67

7

7

1

依次把货物归入体积为15的手拿包,直到手包棉被服装满

1+2+4+5+1=13,前5个物品装入背包,还余下体积为2,第6个货品只可以装入2/3

由此总的价值为:6+10+18+15+3+5*2/3=55.3333

 

交由字符集和相应的功用,能够画出相应的哈夫曼树,并对给定的字符串举行哈夫曼编码。(P155-157)

澳门mgm官网 38

澳门mgm官网 39

 

 

D  f(n) = O(g(n)) ⇔g(n) = O(f(n))

第8章 回溯法

领悟回溯法的布署性理念

两全观念:从解空间树根结点出发,根据深度优先政策遍历解空间树,在寻觅至树中任风流罗曼蒂克结点时,先推断该结点对应的一些解是还是不是满足约束标准,或许是还是不是超出目的函数的界,也便是剖断该结点是或不是包括难题的(最优)解,假诺一定不带有,则跳过对以该结点为根的子树的索求,即所谓剪枝(Pruning);不然,步向以该结点为根的子树,继续根据深度优先政策找寻。直到搜索到叶子结点,则获得难点的八个大概解。

步骤:

分明解向量和重量的取值范围,结构解空间树;

规定剪枝函数;

对解空间树按深度优先寻找,寻觅进度中剪枝;

从有着的恐怕解中鲜明最优解。

 

叩问能够用回溯法解决的难点:

归属组合难题和排列难题中求最优解的标题都足以用回溯法消除,譬如:图着色难题,哈密顿回路难题,八皇后难题(4皇后难点),批管理作业调治难点。

 

调控m颜色图着色决断难题的追思法算法,并能画出解空间树的查找进程(P168-170),习题8-4

对图8.14使用回溯法求解图难题,画出转换的物色空间。

澳门mgm官网 40

 

解:图着色难点求解的是满意图着色必要的异常的小颜色数。对图8.14应该从1、2、3、4……种颜色依次尝试用回溯法决断是不是满足M着色的渴求。

经查找,1种和2种颜色均不可能满足图着色的须要,3种颜色能够满足图着色供给,寻找进度如下,所以图8.14的着色的最少颜色数应该为3

寻找空间为:

澳门mgm官网 41

 

调节n皇后难点的回主张算法,并能画出解空间树的查找进度(P173-174),

和蔼看书

掌握0/1手提包难点的追忆算法,并能画出解空间树的检索进度(P163-164),习题8-5

投机看书

习题8-6,算法设计题。

 给定三个正整数集合X={x1,x2,…, xn}和四个正整数y,设计回溯算法,求集合X的二个子集Y,使得Y桐月素之和等于y。

解:

用回溯法求解难题深入分析:

该难点为求子集难题。

解分量的和小于y为剪枝函数。

当寻觅到结点,何况解分量的和至极y时,找到难题的解。

 

1.X={x1,x2,x3……xn },sum=0,Y={ }为解向量,初叶化为全0;

2.flag=false;

3.k=1;

4.while (k>=1)

      4.1 当(Sk取1、0卡塔尔国循环实施下列操作

            4.1.1yk=Sk中的下三个成分;

            4.1.2将yk加入Y;

            4.1.3sum=+(yk?xk:0);

            4.1.4if (sum==y) flag=true; 转步骤5;

            4.1.4else if (sum<y) k=k+1; 转步骤4;

      4.2 重新载入参数Sk,使得下二个要素排在第三位;

      4.3 k=k-1;    //回溯

5.if flag 输出解Y;

      else 输出“无解”;

参照代码:

 

[cpp] view plaincopy

 

  1. #include <iostream.h>  
  2. const int N=5;  
  3. int f(int x[],int  y[],int n)  
  4. {  
  5.      //初叶化y,y为所求的会面  
  6.      for(inti=0;i<N;i++)  
  7.          y[i]=2;  
  8.      int k=0;  
  9.      int sum=0;  
  10.      while(k>=0)  
  11.      {  
  12.          y[k]=y[k]-1;  
  13.          if((y[k]==1||y[k]==0)&&k<N){  
  14.               sum=sum+(y[k]?x[k]:0);  
  15.               if(sum==n){break;}//找到解  
  16.               else{  
  17.                    if(sum<n卡塔尔{k++;}//寻找下二个  
  18.                    else{  
  19.                        sum=sum-(y[k]?x[k]:0);  
  20.                    }  
  21.               }  
  22.          }  
  23.          else{//回溯  
  24.          //  sum=sum-(y[k]?x[k]:0);  
  25.               y[k]=2;  
  26.               k--;  
  27.               sum=sum-(y[k]?x[k]:0);  
  28.          }  
  29.      }  
  30.      return k;  
  31. }  
  32.    
  33. void main()  
  34. {  
  35.      int x[N]={2,1,3,4,2};  
  36.      int y[N]; //解向量  
  37.      int n=12; //题目必要等于的和  
  38.      int k=f(x,y,n卡塔尔(قطر‎;//k表示寻觅到第多少个要素  
  39.      cout<<k<<endl;  
  40.      for(int i=0;i<N;i++)  
  41.          cout<<(y[i]==1?x[i]:0)<<endl;  
  42.    
  43. }  
  1. 暗号O的概念准确的是(A)。

第9章 分治限界法

摸底分支限界法的规划思想

规划思想:

1)首先鲜明八个合理的境界函数,并依照限界函数鲜明指标函数的界[down, up] ,并规定限界函数;

2)然后依据广度优先政策遍历难题的解空间树,在分层结点上,依次寻觅该结点的拥有子女结点,分别估量那个孩子结点的分界函数的恐怕取值;

3)假使某孩子结点的疆界函数或者赢得的值超过指标函数的界,则将其废弃;不然,将其参预待管理结点表(以下简单称谓表PT)中;

4)依次从表PT中接收使限界函数的值是极值的结点成为当前扩充结点;

5)重复上述进程,直到找到寻找到叶子结点,若是叶子结点的边际函数的值是极值,则正是难点的最优解,不然,找到任何极值结点重复扩张寻觅。

步骤:

规定解空间树

鲜明限界函数

按广度优先搜索解空间树,总计限界函数的值,填入PT表

从PT表中检索极值,继续扩充结点,直到找到限界函数值为极值的叶子结点。

 

打听能够应用分支限界法化解的主题素材:

TSP难点,多段图的最短路线难点,职责分配难点,批管理作业调整难题,0/1手提袋难题。

调控职责分配难点的道岔限界法(P195-197),习题9-5

驾驭0/1包包难点的支行限界法(P184-185),习题9-6

精晓批管理作业难题的分层限界法(P198-200),习题9-7

 

更多0

  • 上一篇Spring学习--面向抽象编制程序(模拟Spring的简约完毕)
  • 下一篇算法深入分析与安排--0/1马鞍包难题(回溯法)

主旨推荐
设计算法冒泡排序快快排序合并列排在一条线序

猜你在找
计算机优良图书E-BOOK合集(符合Computer学子上学以致技术员笔试、面试卡塔尔(قطر‎

写给Computer学子的求学观点

ACM班新队员暑假集中锻练安顿

冒泡、快捷、合并列排在一条线序课程设计

计科《算法设计与解析》第三周作业——冒泡排序和集结排序

数据布局与算法:三种排序算法总括(冒泡排序、选取排序、直接插入排序、Hill排序、堆排序、合併列排在一条线序、火速排序)

归拢列排在一条线序和快速排序比较【算法设计与解析实验报告】

算法导论之插入排序,采纳排序,合并列排在一条线序,冒泡排序,Hill排序,堆排序,快速排序的c语言实现

各样排序算法总计----基数排序、合併列排在一条线序、插入排序、冒泡排序、选拔排序、飞速排序、堆排序、Hill排序

接受排序、火速排序、Hill排序、堆排序不是牢固的排序算法,而冒泡排序、插入排序、归总列排在一条线序和基数排序

 

翻看商量

  暂时未有争论

 

 

你还尚无登入,请[登录]或[注册]

* 以上客户言论只表示其个人观点,不意味CSDN网站的眼光或立场

 

澳门mgm官网 42

A O(g(nState of Qatar卡塔尔国 = { f(nState of Qatar | 存在平常数c和n0使得对具备n≥n0有:0≤ f(n) ≤ cg(n) };

大旨本事类目

整套核心 Java VPN Android iOS ERP IE10 Eclipse CRM JavaScript Ubuntu NFC WAP jQuery 数据库 BIHTML5 Spring Apache Hadoop .NET API HTML SDK IIS Fedora XML LBS Unity Splashtop UML componentsWindows Mobile Rails QEMU KDE Cassandra CloudStack FTC coremail OPhone CouchBase 云计算 iOS6 RackspaceWeb App SpringSide Maemo Compuware 大数据 aptech Perl Tornado Ruby Hibernate ThinkPHP Spark HBase PureSolr Angular Cloud Foundry Redis Scala Django Bootstrap

 

澳门mgm官网 43 
IT_xiao小巫

 

 

澳门mgm官网 44澳门mgm官网 45

  • 访问:485855次
  • 积分:10263分
  • 排名:第366名
  • 原创:496篇
  • 转载:81篇
  • 译文:2篇
  • 评论:758条
Android自定义组件

文章:10篇

阅读:6173
Android通许录模块开发精要

文章:11篇

阅读:15010
新浪微博客户端开发

文章:8篇

阅读:14470
Head First 设计模式学习记录

文章:13篇

阅读:8074
Android--简、美音乐播放器开发过程

文章:13篇

阅读:68880

多年来动态:
1.2016.1.18 实习完结

  1. 今日头条今日头条客商端支付完成
  2. 简、美音乐播放器结束更新
  3. 上学新知识ing
  4. 毕业设计开题

有关评释:
1.多谢网上朋友的钟情,小巫会继续享受技巧和知识

  1. 2016年,小巫将要结业,会延续持始终如一写博客,与君共勉
  2. 小巫建设构造了三个群,有意思味能够投入大家:299402133
  • 【Android博客园今日头条客商端支出】(8)
  • 【 Android应用-小巫新闻客商端】(5)
  • 【Android应用-简、美音乐播放器】(13)
  • 【Android多媒体开垦类别】(2)
  • 【Android UI效果锦集】(4)
  • 【Android开辟学习之路】(117)
  • 【Android开垦记录】(18)
  • 【Android SDK开发】(7)
  • 【Android设计格局连串】(8)
  • 【Android通信录模块开荒】(11)
  • 【Android自定义组件】(11)
  • 【Android Design翻译】(2)
  • 【cocos2d-x】(12)
  • 【二零一二年求职之路-小巫的面试宝典】(13)
  • 【Lua脚本语言】(0)
  • 【技巧进级之设计形式】(13)
  • 【成长记录之记录点滴】(62)
  • 【互联网合同】(3)
  • 【Go语言程序设计】(1)
  • 【IPhone开发】(0)
  • 【PHP服务端】(0)
  • 【Unity 3D】(0)
  • 【建站经历】(1)
  • <----------高校分水线--------->(0)
  • 【Java语言程序设计】(50)
  • 【C++ Primer的学习】(31)
  • 【C++语言程序设计】(27)
  • 【PHP语言程序设计】(8)
  • 【C#言语程序设计】(5)
  • 【操作系统之Linux】(10)
  • 【SQL Server 数据库】(18)
  • 【脚本语言之JavaScript】(1)
  • 【大学课程之计算机网络】(5)
  • 【高校课程之软件工程】(2)
  • 【大学学科之ASP.Net】(7)
  • 【ASP.Net之ADO.Net】(2)
  • 【大学学科之数据布局】(27)
  • 【高校学科杂货】(9)
  • 【大学课程之Java EE】(10)
  • 【高校学科之算法解析与设计】(9)
  • 【高校课程之编译原理】(1)
  • 【大学本科完成学业设计专项论题】(4)

  • 2014年06月(5)

  • 2014年05月(8)
  • 2014年04月(14)
  • 2014年03月(10)
  • 2014年02月(16)

展开

  • Android开源框架ImageLoader的全面例子(17784)
  • Android应用--简、美音乐播放器原型放送(笔者:小巫)(14626)
  • Android自定义单反相机实现(拍照、保存到TF内存卡,利用Bundle在Acitivity调换数据)(10903)
  • Android应用开垦--DVD音乐播放器代码完成(生机勃勃)(10505)
  • 基于Android的小巫音信顾客端支付--主分界面业务逻辑完成(9776)
  • 基于Android的小巫音讯顾客端支付--UI设计(主分界面)(7734)
  • Android应用开采--MP5音乐播放器代码完结(二)(7359)
  • Android应用开采--DVD音乐播放器分界面设计(1)(6988)
  • Android面试题采撷(有详尽答案)(5952)
  • Android应用开辟--MP5音乐播放器Service达成(5449)
  • Android应用--简、美音乐播放器原型放送(小编:小巫)(99)
  • 高档学园结束学业初感悟(60)
  • Android开源框架ImageLoader的周到例子(47)
  • 基于Android的小巫消息顾客端支出--主分界面业务逻辑完毕(27)
  • 基于Android的小巫音讯顾客端支出---呈现新闻详细内容业务逻辑达成(26)
  • Android应用开采--MP5音乐播放器代码完毕(二)(21)
  • Android应用开垦--MP4音乐播放器代码完毕(后生可畏)(20)
  • Android应用开辟--DVD音乐播放器分界面设计(1)(17)
  • Android应用开采--DVD音乐播放器瑟维斯完成(17)
  • Android 友盟社会化组件-分享完成(16)
  • 高端学园结束学业初感悟

    IT_xiao小巫: @u010785685:平素都是为现在是光明的,一同去憧憬吧

  • 高档学园毕业初感悟

    IT_xiao小巫: @gc_gongchao:哈哈,向那个比大家牛B的人读书,超过他们

  • 高校结束学业初感悟

    IT_xiao小巫: @u011212909:好好努力

  • 高端高校完成学业初感悟

    IT_xiao小巫: @fbljq5:不会化为找职业的本钱,但会形成你起步的血本

  • 高级学园完成学业初感悟

    IT_xiao小巫: @szklyy:不太懂。。。

  • 高级高校完成学业初感悟

    IT_xiao小巫: @hanlingyan0219:加油

  • 大学结束学业初感悟

    赵亚盟: 人生就如生龙活虎首不完全的乐曲,意气风发曲待续。加油,现在的人生还有大概会越来越卓越。

  • 高端学园完成学业初感悟

    将军_: 楼主比小编牛逼多了呀,话说,小编那时候增选自愿时,也是坚决接收了Computer类的行业内部,本科读的软件工程,到了高校...

  • 大学毕业初感悟

    将军_: 楼主比本人帅爆了多了哟,话说,小编当年甄选自愿时,也是坚决接收了计算机类的规范,本科读的软件工程,到了高档学园...

  • 高校结业初感悟

    化身为小灰驴的驴小毛: 刚完成学业,博客便是行家级,原创400多篇。。。真心膜拜,就要踏进大四,最上一季度能够努力,实现结束学业目的

从入门到成长到成熟再到精髓,大非常多程序猿走了日前后生可畏段雷同的征程,而略带人却走得更远一些!!!!

 

 

公司简单介绍|选聘纳士|广告服务|银行汇款帐号|联系方式|版权证明|法律军师|难点报告|合作同伴|论坛反映

网站客性格很顽强在艰难险阻或巨大压力面前不屈 侧记客性格很顽强在荆棘载途或巨大压力面前不屈 博客园客服 webmaster@csdn.net 400-600-2320

京 ICP 证 070598 号

京师更新乐知音信才干有限公司 版权全数

广东乐知网络技艺有限公司 提供商务扶持

Copyright © 1999-2014, CSDN.NET, All Rights Reserved 澳门mgm官网 46

澳门mgm官网 47 

B O(g(nState of Qatar卡塔尔 = { f(n卡塔尔 | 存在符合规律数c和n0使得对具有n≥n0有:0≤ cg(n) ≤ f(n) };

C  O(g(n卡塔尔卡塔尔(قطر‎ = { f(n卡塔尔国 | 对于其他正规数c>0,存在正数和n0 >0使得对具备n≥n0有:0 ≤f(n)<cg(n) };

D  O(g(nState of QatarState of Qatar = { f(nState of Qatar | 对于其余正规数c>0,存在正数和n0 >0使得对持有n≥n0有:0 ≤cg(n) < f(n) }; 

  1. 暗记Ω的定义正确的是(B)。

A   O(g(n卡塔尔国卡塔尔国 = { f(nState of Qatar | 存在平常数c和n0使得对具有n≥n0有:0≤ f(n) ≤ cg(n) };

B   O(g(n卡塔尔卡塔尔(قطر‎ = { f(nState of Qatar | 存在正常数c和n0使得对具备n≥n0有:0≤ cg(n) ≤ f(n) };

C   (g(n卡塔尔卡塔尔国 = { f(n卡塔尔国 | 对于别的正规数c>0,存在正数和n0 >0使得对具有n≥n0有:0 ≤f(n)<cg(n) };

D   (g(n卡塔尔国卡塔尔国 = { f(n卡塔尔(قطر‎ | 对于任何正规数c>0,存在正数和n0 >0使得对具有n≥n0有:0 ≤cg(n) < f(n) }; 

  1. T(n)代表当输入规模为n时的算法功效,以下算法效用最优的是( C 卡塔尔

A T(n)= T(n – 1)+1,T(1)=1    

B T(n)=  2n2

C T(n)= T(n/2)+1,T(1)=1      

D T(n)= 3nlog2n

  1. 动态规划算法的基本要素为(C)

A  最优子构造天性与贪心选用性质

B 重叠子难点性质与贪心选拔性质

C 最优子构造特性与重叠子难题性质

D  预排序与递归调用

7.下列不是动态规划算法基本步骤的是(   A    )。

A 寻觅最优解的属性            B 结构最优解  

C 算出最优解                  D 定义最优解

8.能接受贪心算法求最优解的难题,日常装有的尤为重要性质为:(A)

A 最优子构造性情与贪心选取性质

B 重叠子难题性质与贪心选用性质

C 最优子构造本性与重叠子难点性质

D 预排序与递归调用

9.底下是名缰利锁算法的基本要素的是(      C     )。

A 重叠子难点  B 布局最优解  C 贪心选用性质  D 定义最优解

10(   D   )是名缰利锁算法与动态规划算法的合作点。

A 重叠子难题          B 布局最优解

C 贪心选取性质        D 最优子结构个性

11.施用分治法求解无需满意的尺度是(A )。

A 子难点必须要是同生机勃勃的         B 子难题不可见再一次

C 子难题的解能够统大器晚成       D 原主题材料和子难题选择同后生可畏的艺术解

12.完毕循环赛日程表利用的算法是(    A      )。

A 分治政策       B 动态规划法  

C 贪心法         D 回溯法

13.应用分治法求解无需知足的基准是(A )。

A 子难题亟须是均等的         B 子难题不可以预知再度

C 子难点的解能够统风华正茂       D 原难点和子难点采纳同黄金年代的艺术解

14.下列算法中不能够解决0/1手包难点的是(A )

A 贪心法  B 动态规划  C 回溯法  D 分支限界法

15.之下( C 卡塔尔(قطر‎不能够或不可能在线性时间成功排序

A 计数排序     B 基数排序      C 堆排序      D 桶排序

16.下列哪意气风发种算法是随机化算法(    D     )

A 贪心算法     B 回溯法     C 动态规划算法    D Sherwood算法

  1. 下列算法中常见以自底向上的不二等秘书籍求解最优解的(    B     )。 A 分治法     B 动态规划法    C 贪心法    D 回溯法

18. n私有拎着水桶在叁个水阀前边排队打水,水桶有大有小,水桶必得打满水,水流恒定。如下 ( A 卡塔尔国 说法不无误?A

A 让水桶大的人先打水,能够使得各种人排队时间之和纤维

B 让水桶小的人先打水,可以使得各种人排队时间之和纤维

C 让水桶小的人先打水,在有些明确的年华t内,可以让尽恐怕多的人打上水

D 若要在尽量短的日子内,n个人都打完水,遵照什么样顺序其实都平等

19.PRADO曼编码的贪婪算法所需的考虑时间为 (  B    卡塔尔(قطر‎。

A O(n2n)  B O(nlogn)  C O(2n)  D O(n)

20.上面关于NP难题说法科学的是(B 卡塔尔(قطر‎

A NP难题都以不容许消弭的主题素材   

B P类难点暗含在NP类难点中

C NP完全难点是P类问题的子集    

D NP类难点暗含在P类难点中

21.单肩包标题贪心算法所需的估测计算时间为(  B   卡塔尔国   

A O(n2n)  B O(nlogn)  C O(2n)  D O(n)

22.包包主题材料的回想算法所需的总计时间为(  A   )  

A O(n2n)  B O(nlogn)  C O(2n)  D O(n)

23.施用最大效劳优先搜索格局的算法是(  A   )  

A 分支界限发      B 动态规划法     C 贪心法    D 回溯法

24. 在棋盘覆盖难点中,对于2k×2k的奇特棋盘(有三个奇特方块),所需的L型骨牌的个数是 ( A )

A ( 4k – 1)/3  B 2k /3      C 4k      D 2k

  1. 下列随机算法中运维时不经常候成功临时候退步的是(C )

A 数值可能率算法 B 舍Wood算法 C 布兰太尔算法 D 蒙特卡罗算法

  1. 兑现大整数的乘法是利用的算法(      C   )。

A 贪心法    B 动态规划法   C 分治政策  D 回溯法

二、填空题

1.算法的目眩神摇有    时间    复杂性和    空间     复杂性之分。

2.矩阵连乘难点的算法可由  动态规划  设计完结。

3.从分治法的相同设计情势能够观察,用它安插出的次序经常是  递归算法  。

4.算法是由若干条指令组成的商朝体系,且要知足输入、输出、明确性和有限性四条性质。

5.飞跃排序算法的性质决定于  划分的对称性  。

6.选择二分找出算法在n个有序成分表中搜索贰个特定成分,在一级状态下,搜索的年月复杂性为O( 1 ),在最坏情况下,搜索的小时复杂性为O( logn  )。

三、解答题

1. 给定已按升序排好序的n个成分a[0:n-1],现要在这里n个因素中搜索风流罗曼蒂克特定成分x,重返其在数组中的地点,如果未找到再次来到-1。 写出二分查找的算法,并深入分析其时间复杂度

  1. 浅析最有追寻二叉树和0/1马鞍包的光阴复杂度

3. 试用动态规划算法完成最大子矩阵和主题材料:求n×m矩阵A的三个子矩阵,使其各因素之各为最大

4已知输入向量a=(1,3,4,-2),给出用FFT的蝶形操作求输出向量y的结果,并解析出FFT的思虑时间复杂度。

 

1.用到递归算法求递归方程F(n卡塔尔=F(n-1(+F(n-2卡塔尔(قطر‎,算法描述如下(正是递归fibonacci!)

问:算法共要求开展多少次递归调用(算法中没征引F(iState of Qatar三遍称为一遍递归调用)。有未有更加好的算法来总计F(n卡塔尔国?若有请描述算法并分析复杂度。

2.之类算法是或不是发毕生均布满的跟着调换?为啥?

Permute-With-All(A)

  n←length(A)

  for i←1 to n

     swap(A[i],A[RANDOM(1,n)])

注:RANDOM(1,n卡塔尔随机、等大概地再次回到整数k,1≤k≤n

3. 能还是不能够在给定的s[n]中推断是否留存多少个数的和为x,何况时间复杂度是nlgn,借使得以写出程序的伪代码,不然给出理由。

  1. 挪动选拔难点

(1)递归的岁月复杂度解析

(2)动态规划的日子复杂度深入分析

(3)写出三个更优的算法,何况对其举办时间复杂度分析

  1. 多项式乘法难点

汇报三个非常快的算法来缓和复数之间的多项式乘法,多项式的全面为复数,未鲜明的数也为复数。

还要对此张开时间复杂度剖判。

 

郑55                           算法2013考试题

填空:

  1. 给一美妙绝伦的函数,依照渐进性,从大到小排列n^3/2,nlgn,lgn,e^n,n!,n^2
  2. 动归的四个属性
  3. 贪婪无餍的两特性情
  4. 1)NP问题:  2)P问题
  5. 面试标题 雇一人的概率:  ,雇n个人的概率:
  6. 复杂度分为:  和  ;动归是捐躯   复杂度换取   复杂度
  7. 选取二分寻找算法在n个有序成分表中寻觅一个一定成分,在拔尖状态下,寻觅的年华复杂性为O( 1 ),在最坏意况下,找寻的岁月复杂性为O( logn  )。

选择:

1摊还排序是()意况下的()代价

A最优B最坏C平均D最好

2动态规划的设计思想是a

(a卡塔尔自底向上   (b卡塔尔(قطر‎自上而下   (cState of Qatar从左向右   (dState of Qatar从右向左

3贪婪算法的设计观念是b

(aState of Qatar自底向上   (b卡塔尔国自上而下   (c卡塔尔(قطر‎从左向右   (d卡塔尔(قطر‎从右向左

4以下哪一个更或然描述实际多个灵光的算法d

(a)    (b)    (c)    (d)

5蝶形操作的统筹理念是a

(a卡塔尔国分治法   (b卡塔尔(قطر‎贪心算法   (c卡塔尔(قطر‎动态规划   (d卡塔尔回溯

6以下哪三个不是NPC难点

(a卡塔尔单源最短路线   (b卡塔尔国巡回售货员难题   (c卡塔尔(قطر‎布尔可满足性难题   (dState of Qatar大数分解

7以下哪些不是几何探讨中的基本操作

(a)+   (b)—   (c)×   (d)/

8哪个难点不可能用贪心算法消除

(aState of Qatar活动计划   (b卡塔尔哈夫曼编码   (c卡塔尔(قطر‎分数双肩包   (d卡塔尔(قطر‎0-1信封包

9哪个难题无法用动态规划消弭c

(a卡塔尔分数单肩包   (b卡塔尔国0-1手包   (cState of Qatar最长简单路线   (dState of Qatar最短轻易路径

10插入排序的然而时光复杂度是a

(a)n   (b)n^2   (c)nlgn   (d)lgn

11合併列排在一条线序的年月复杂度是c

(a)n   (b)n^2   (c)nlgn   (d)lgn

12算法解析中,灯号O表示(B),灯号Ω标价发售(A),暗记Θ表示(D)

A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界

13.n个体拎着水桶在三个水阀后面排队打水,水桶有大有小,水桶必得打满水,水流恒定。如下 ( A State of Qatar 说法不得法?A

A 让水桶大的人先打水,可以使得各样人排队时间之和微小

B 让水桶小的人先打水,能够使得各样人排队时间之和渺小

C 让水桶小的人先打水,在有些分明的年华t内,能够让尽或然多的人打上水

D 若要在尽恐怕短的日子内,n个人都打完水,依照什么样顺序其实都同豆蔻年华

14.RAV4曼编码的自私自利算法所需的乘除时间为 (  B    State of Qatar。

A O(n2n)  B O(nlogn)  C O(2n)  D O(n)

15.上面关于NP难点说法科学的是(B 卡塔尔(قطر‎

A NP难题都是不恐怕消弭的主题素材   

B P类难题暗含在NP类难题中

C NP完全难点是P类难题的子集    

D NP类难题暗含在P类难点中

大题

  1. 四路合併列排在一条线序:分解时分成四个,合併等任何步骤与二路归总肖似,请写出中央算法,并解析时间复杂度。
  2. 矩阵链乘积的递归算法

T(n)= 1    n=1

  n>=2

请详细深入分析该算法的日子复杂度

  1. 交付最优二叉搜索树的程序代码和p,q可能率

依赖可能率1)求e,w,root,2)画出二叉树的构造3)请说出root[i,j]有如何意思

(见3621大班试卷影印版的第五题)

  1. FFt蝶形操作 见3621大班试卷的影印版第九题
  2. 字符串自动机结构,见书

 

二〇〇六-二〇〇五学年第二学期《Computer算法设计与深入分析》试题

院系:软件高校   专门的学问:软件工程   年级:二〇〇一级

 

一.简答题(共10分)

 

二.计算题(35分)

1.(6分卡塔尔对下列各组函数f(n卡塔尔和g(n卡塔尔(قطر‎,分明f(n卡塔尔国=O(g(nState of QatarState of Qatar或f(n卡塔尔=Ω(g(n卡塔尔(قطر‎卡塔尔(قطر‎或f(n卡塔尔(قطر‎=θ(g(n卡塔尔国卡塔尔。

(1)   f(n)=3n,g(n)=2n

(2)   f(n)=log n + 5,g(n)=log n2

(3)   f(n)=log n,g(n)=

答:

(1)                                 f(n) = Ω(g(n))         (2分)

(2)                                 f(n) = θ(g(n))         (2分)

(3)                                 f(n) = O(g(n))          (2分)

 

2.(8分)采纳动态规划政策,总括a={5,-3,7,-4,-5,9,-2,10,-3,2}的最大子段和,并付出那么些最大子段和的开场下标和停歇下标。[设数组a中的成分下标从1从头。]必要付诸进程。

答:

       b[1]=5;

       b[2]=max{b[1]+a[2],a[2]}=max{2,-3}=2

b[3]=max{b[2]+a[3],a[3]}=max{9,7}=9

b[4]=max{b[3]+a[4],a[4]}=max{5,-4}=5

b[5]=max{b[4]+a[5],a[5]}=max{0,-5}=0

b[6]=max{b[5]+a[6],a[6]}=max{9,9}=9

b[7]=max{b[6]+a[7],a[7]}=max{7,-2}=7

b[8]=max{b[7]+a[8],a[8]}=max{17,10}=17

b[9]=max{b[8]+a[9],a[9]}=max{14,-3}=14

b[10]=max{b[9]+a[10],a[10]}=max{16,2}=16

(上述每两行1分,共5分卡塔尔(قطر‎

最大子段和为17(1分)

(若数组下标从1起来)起首下标:6(1分),终止下标:8(1分)

(若数组下标从0开首)初叶下标:5(0.5分),终止下标:7(0.5分)

 

3.(11分)设有3件专门的职业分配给3个人,将职业i分配给第j个人所花的成本为Cij,现将为每一位都分配1件差异的干活,并使总花费到达最小。设:

      

要求:

(1)画出该难点的解空间树;(6分)

(2)写出该难题的剪枝战略(限界条件卡塔尔国;(1分)

(3)按回溯法寻找解空间树,并选择剪枝计谋对相应剪掉的子树打´;(2分)

(4)最后提交该难点的最优值和最优解。(2分)

答:

     (1)

                                   

1         2        3             

2       3      1      3       1      2

         

              1        1      2        2      3        3

      

                                                 

             3          2     3        1      2        1

                       

           16        16   9      9      9      9

                         ╳               ╳        ╳        ╳

         (每个分枝1分,也许是每层2分,共6分)

       (2)当花费大于等于当前最优值时,剪枝。(1分)

       (3)见上图。(每2个 1分,共2分)

    (4)最优值: 9   (1分)

        最优解:2,1,3

 

 

 

4.(8分)给定三个种类X=<A,B,C,B,A>,Y=<B,D,C,A,B>,请选用动态规划政策求出其最长公共子体系。要求付诸过程。

答:

j   0    1     2     3     4      5   

i         yi      B    D     C     A     B   

0   xi    0    0    0      0     0      0    

1   A    0    0    0      0     1      1    

2   B    0    1    1      1     1      2    

3   C   0    1    1      2     2      2   

4   B    0    1    1      2     2      3   

5   A   0    1    2      2     2      3    

         (上述表内每豆蔻梢头行一分,共6分)

         最长公共子种类为<B,C,B>  (2分)

   

5.(2分)酌量n=3时的0-1手袋难题的实例:W={15,10,10},P={50,30,30},c=20。当x[1]=1,x[2]=0时,请计算Bound(2)。

答:

Bound(3)=50+5/10 * 20 = 65    (2分)

 

三、算法填空题(共10分,每空2分)

加以n种货品和一个背包,物品i的轻重是w[i], 其市场总值是p[i], 手袋的体积为c。设物品已按单位重量价值依次减少的次序排序。每一种货色不得以装入包包多次,但能够装入部分的货品i。求解单肩包难点的荒淫无耻算法如下:

float Knapsack (float x[ ], float w[ ], float p[ ],float c, int n)  

{ float maxsum=           ;   // maxsum表示装进包的物料价值总和               

for ( int i=1;i<=n; i++)  x[i]=0 // x[i]=0表示第i个货物未装进包         

for (                        ** **)                        

         if(                )                                

{ x[i] =1;                                 

             maxsum+=             ;                           

             c- = w[i];                                

       }

         else break;                               

if (c>0) {x[i]=c/w[i];                   ;}      

return maxsum;                             

}

答:(共5个空,每空2分,总计10分)

       0 

       int i=1;i<=n;i++

       w[i]<=C

       p[i]

       maxsum+ = p[i] * c / w[i]

 

四、算法设计及分析题(共45分)

1.(20分)请用分治战略设计递归的二分查找算法,并深入分析其时间复杂性(必要提交各种阶段所花的小时,在那根基上列出递归方程,并求出其解的渐进级)。

答:(此题解法不唯后生可畏)

算法:

int bsearch(A[],K,L,H)                                          (1分)

{ if (H<L)  return(-1);                                           (2分)

 else

{ mid=(L+H) /2;                                            (2分)

          if (A[mid] == K)                                      (1分)

              return(mid);                                    (1分)

     else if (A[mid]>K)                                       (2分)

return(bsearch(A,K,L, mid-1)) ;                     (2分) 

         else  return(bsearch(K, mid+1,H));                       (2分)

     }

}

 

 

算法时间复杂性剖析:

Divide阶段所花时间为O(1State of Qatar                                   (1分)

   Conquer阶段所花时间为T(n/2卡塔尔                              (1分卡塔尔

   merge阶段没有花时间(大概说,merge阶段所花时间为O(1卡塔尔)  (1分)

∴算法时间复杂性递归方程如下:

   T(n)=O(1)             当n≤0

     T(n)= T(n/2)+O(1)    当n>1                              (2分)

  用套用公式法(master method)求解递归方程:

     ∵a=1,b=2,                                  

   f(n)=O(1), ∴与f(n)同阶                             

T(n)= O(log n)                                                     (2分)

 

2.(15分)请用回溯法设计算法,用各个颜色给地图着色(若在调用了其余算法,也需将该算法写出)。请在种种循环语句和标准判定语句后加注释。

答:(此题解法不唯生龙活虎)

算法:

boolColor::Ok(int k)                                                 

{ for (int j=1; j<k; j++卡塔尔国//检查前k-1个点与当前点(第k点)颜色是不是冲突 (2分)

if ((a[k][j]==1)&&(x[j]==x[k]))

//决断第j点与日前点(第k点)颜色是不是冲突  (2分)

return false;                                            (1分)

else  return true;                                                       (1分)

}

 

void Color::Backtrack(int t)                                                   

{ if (t > n卡塔尔  // 判别是不是到叶节点                                            (1分)

{ sum++;                                                              

for (int i=1;i<=n; i++卡塔尔(قطر‎ //输出每一种点的色号                                 

cout << x[i]<< ’  ’ ;                                              

cout << endl;                                                         (2分)

}

else  

for (int i=1; i<=4; i++卡塔尔国 // 依次检查当前点(第t点)是还是不是可着第i(1≤i≤4)种颜色  (2分)

{ x[t]=i;                                                               (1分)

if (Ok(t卡塔尔(قطر‎卡塔尔(قطر‎  Backtrack(t+1卡塔尔; //若当前点(第t点)可着第i种颜色,则递归调用  (3分)

}

}

 

3.(10分)请设计二个算法,完成优先队列的出队操作。须求:

(1)提议用什么数据布局完毕优先队列;

(2)用C语言描述算法。

答:(此题解法不唯风姿浪漫)

       (1)用堆完毕优先队列。     (2分)

       (2)算法

              SIFT(k,i,m)

              {temp = k[i];              

               j=2*i;                    (1分)

               while (j<=m)              (1分)

                      { if((j<m)&&(R[j].key<R[j+1].key))j++;  (1分)

if (temp.key <R[j].key)                 (1分)

        { R[i] = R[j];

          i=j; j=2*i;                       (1分)

        }

else break;                               (0.5分)

        R[i]=temp;                                    (0.5分)

       }

 

      Delete(n) 

          { temp = R[1]; R[1]=R[i]; R[i]=temp;        (1分)

SIFT(k,1,n-1);                        (1分)

       }

 

 

算法导论试题

题型:选择+解答

一,选择

(1)       动态规划的安插思想是a

(a卡塔尔(قطر‎自底向上   (b卡塔尔国自上而下   (c卡塔尔从左向右   (d卡塔尔从右向左

(2)       贪心算法的布署观念是b

(a卡塔尔自底向上   (bState of Qatar自上而下   (c卡塔尔国从左向右   (d卡塔尔从右向左

(3)       以下哪二个更恐怕描述实际三个可行的算法d

(a)    (b)    (c)    (d)

(4)       蝶形操作的安排思想是a

(a卡塔尔国分治法   (b卡塔尔(قطر‎贪心算法   (c卡塔尔动态规划   (d卡塔尔回溯

(5)       以下哪多少个不是NPC难点

(a卡塔尔国单源最短路径   (b卡塔尔(قطر‎巡回售货员难点   (cState of Qatar布尔可满意性难题   (d卡塔尔(قطر‎大数分解

(6)       以下哪些不是几何商量中的基本操作

(a)+   (b)—   (c)×   (d)/

(7)       哪个难题不能够用贪心算法消亡

(a卡塔尔活动布署   (b卡塔尔哈夫曼编码   (c卡塔尔国分数双肩包   (dState of Qatar0-1手提袋

(8)       哪个难题不可能用动态规划解决c

(a卡塔尔分数托特包   (b卡塔尔国0-1信封包   (cState of Qatar最长简单路线   (dState of Qatar最短轻松路线

(9)       插入排序的最佳时光复杂度是a

(a)n   (b)n^2   (c)nlgn   (d)lgn

(10)   合併列排在一条线序的时光复杂度是c

(a)n   (b)n^2   (c)nlgn   (d)lgn

 

二,解答题(共6题,此处少1题)

(1)       编写伪代码并深入分析时间复杂度,需求统筹的顺序是:运用递归算法设计插入排序,况且用到折半查找。提醒:要排序a[1……n],先排a[1……n-1],插入a[n]用折半查找。

(2)       能或不可能在给定的s[n]中剖断是或不是留存七个数的和为x,並且时间复杂度是nlgn,假如得以写出程序的伪代码,不然给出理由。

(3)       四个n维矩阵乘法A×B=C,将A,B分解为4个n/2维的矩阵,解析以下算法的时刻复杂度。

A=,B=,C=

定义P1=(A11+A22)(B11+B22),P2=(A11+A22)B11,P3=A11(B11-B22),P4=A22(-B11+B22),P5=(A12+A11)B22,P6=(-A11+A21)(B11+B12),P7=(A12-A22)(B11+B22)

则C11=P1+P4-P5+P7,C12=P3+P5,C21=P2+P4,C22=P1+P3-P2+P6

(4)       递归斐波纳切数列的小运复杂度

(5)       矩阵链乘法总结最优代价,须要画出和书籍上p200周边的三角形图(动态规划)

 

 

一。选择题

1、二分寻觅算法是利用(   A      )达成的算法。

A、分治计谋   B、动态规划法   C、贪心法    D、回溯法

2、下列不是动态规划算法基本步骤的是(   A    )。

A、找寻最优解的属性   B、布局最优解   C、算出最优解   D、定义最优解

3、最大要义优先是(  A         )的生龙活虎探求情势。

A、分支界限法      B、动态规划法    C、贪心法    D、回溯法

4、在下列算法中不经常找不到标题解的是( B       )。

A、蒙特卡罗算法    B、多特Mond算法   C、舍Wood算法   D、数值可能率算法

  1. 记忆法解游览售货员难题时的解空间树是( A      )。

A、子集树         B、排列树     C、深度优先生成树    D、广度优先生成树

6.下列算法中经常以自底向上的章程求解最优解的是(   B      )。

A、备忘录法       B、动态规划法     C、贪心法                D、回溯法

7、衡量二个算法好坏的行业内部是(C )。
A 运维速度快 B 占用空间少 C 时间复杂度低 D 代码短
8、以下不能选拔分治法求解的是(D )。
A 棋盘覆盖难题 B 接受难题 C 合并列排在一条线序 D 0/1手提包难点

  1. 完成循环赛日程表利用的算法是(    A      )。

A、分治战略          B、动态规划法        C、贪心法         D、回溯法

10、下列随机算法中运营时不时候成功不时候失败的是(C )
A 数值可能率算法 B 舍Wood算法 C 利伯维尔算法 D 蒙特卡罗算法

11.上面不是分支界限法寻找格局的是(     D     )。

A、广度优先       B、最小花费优先   C、最大职能优先      D、深度优先

12.下列算法中何奇之有以深度优先进楷模式系统查找难题解的是(      D   )。

A、备忘录法       B、动态规划法     C、贪心法                D、回溯法

13.备忘录措施是这种算法的变形。(     B )

A、分治法     B、动态规划法     C、贪心法                D、回溯法

14.Tiggo曼编码的贪婪算法所需的乘除时间为(   B     )。

A、O(n2n)       B、O(nlogn)     C、O(2n)               D、O(n)

15.分支限界法解最大团难题时,活结点表的公司格局是(    B    )。

A、最小堆            B、最大堆         C、栈                    D、数组

16.最长公共子类别算法利用的算法是(    B       )。

A、分支界限法     B、动态规划法        C、贪心法            D、回溯法

17.落到实处棋盘覆盖算法利用的算法是(     A      )。

A、分治法         B、动态规划法     C、贪心法                D、回溯法

18.底下是名缰利锁算法的基本要素的是(      C     )。

A、重叠子难题     B、布局最优解     C、贪心接受性质      D、定义最优解

19.回溯法的功效不依附于于下列哪些因素(   D     )

A.满意显约束的值的个数             B. 计算约束函数的年华 

C. 总计限界函数的时间              D. 鲜明解空间的时日

20.上面哪类函数是回主张中为幸免无效搜索选拔的国策(    B    )

A.递归函数       B.剪枝函数        C。随机数函数        D.找出函数

21、上面关于NP难题说法科学的是(B )
A NP难点都以不可能消除的难题
B P类难题暗含在NP类难题中
C NP完全难点是P类难点的子集
D NP类难点暗含在P类难题中

22、蒙特卡罗算法是(   B      )的生机勃勃种。

A、分支界限算法      B、可能率算法    C、贪心算法    D、回溯算法

23.下列哪朝气蓬勃种算法不是随机化算法(    C     )

A. 蒙特卡罗算法B. 波德戈里察算法C.动态规划算法D.舍Wood算法

  1. (   D         )是贪心算法与动态规划算法的协同点。

A、重叠子难题 B、布局最优解 C、贪心选拔性质      D、最优子布局天性

  1. 矩阵连乘难点的算法可由(          B)设计落成。

A、分支界限算法      B、动态规划算法    C、贪心算法    D、回溯算法

  1. 分段限界法解游历售货员难点时,活结点表的团体情势是(   A    )。

A、最小堆         B、最大堆         C、栈                D、数组

27、Strassen矩阵乘法是选取(    A     )完结的算法。

A、分治计策   B、动态规划法   C、贪心法    D、回溯法

29、使用分治法求解无需满足的标准是(A )。
A 子难点必需是生机勃勃致的
B 子难点不可以知道再度
C 子难点的解能够统生机勃勃
D 原难题和子难点选用相像的形式解
30、上边难点(B )无法运用贪心法解决。
A 单源最短路线难题          B N皇后主题材料
C 最小开支生成树难点        D 手拿包难点
31、下列算法中不能够歼灭0/1手提包难题的是(A )
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
32、回溯法搜索状态空间树是遵照(C )的种种。
A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 等级次序优先遍历

33、下列随机算法中运营时临时候成功有时候失利的是(C )
A 数值可能率算法 B 舍Wood算法 C 塔这那利佛算法 D 蒙特卡罗算法
34.贯彻统一排序利用的算法是(     A    )。

A、分治战略          B、动态规划法        C、贪心法         D、回溯法

35.下列是动态规划算法基本要素的是(  D     )。

A、定义最优解        B、构造最优解        C、算出最优解     D、子难点重叠性质

36.下列算法中管见所及以自底向下的法子求解最优解的是(    B     )。

A、分治法            B、动态规划法        C、贪心法         D、回溯法

37.利用广度优先政策找寻的算法是(     A      )。

A、分支界限法        B、动态规划法        C、贪心法         D、回溯法

38、合并列排在一条线序算法是行使(   A      )达成的算法。

A、分治战术   B、动态规划法   C、贪心法    D、回溯法

39、在下列算法中获取的解未必准确的是(  B      )。

A、蒙特卡罗算法    B、布兰太尔算法   C、舍Wood算法   D、数值可能率算法

40、包包难题的人欲横流算法所需的精兵简政时间为(  B      )

A、O(n2n)     B、O(nlogn)    C、O(2n)      D、O(n)

41.得以完成大整数的乘法是运用的算法(      C   )。

A、贪心法            B、动态规划法        C、分治战略       D、回溯法

42.0-1手拿包难题的追思算法所需的精打细算时间为(  A      )

A、O(n2n)          B、O(nlogn)        C、O(2n)        D、O(n)

43.使用最大成效优先找寻情势的算法是(   A        )。

A、分支界限法        B、动态规划法        C、贪心法         D、回溯法

44.贪心算法与动态规划算法的第生龙活虎差别是(  B         )。

A、最优子布局        B、贪心选取性质      C、构造最优解     D、定义最优解

  1. 落实最大子段和动用的算法是(     B      )。

A、分治战略          B、动态规划法        C、贪心法         D、回溯法

46.优先队列式分支限界法接受扩大结点的尺码是(     C      )。

A、先进先出          B、后进先出          C、结点的预先级   D、随机

47.信封包标题标贪婪算法所需的思忖时间为(   B     )。

A、O(n2n)           B、O(nlogn)     C、O(2n)            D、O(n)

48、广度优先是(    A       )的黄金年代招来情势。

A、分支界限法      B、动态规划法    C、贪心法    D、回溯法

49、舍Wood算法是(    B     )的黄金时代种。

A、分支界限算法      B、可能率算法    C、贪心算法    D、回溯算法

50、在下列算法中不常找不到难题解的是(  B      )。

A、蒙特卡罗算法    B、阿里格尔算法   C、舍Wood算法   D、数值可能率算法

51下列哪风流倜傥种算法是随机化算法(    D     )

A. 贪心算法B. 回溯法C.动态规划算法D.舍Wood算法

52. 叁个标题可用动态规划算法或贪恋算法求解的机要性子是难点的(   B          )。

A、重叠子难题     B、最优子布局性格    C、贪心接纳性质   D、定义最优解

53.接受贪心算法的最优装载问题的重点总结量在于将集装箱依其重量从小到大排序,故算法的时光复杂度为    (     B           卡塔尔国 。

A、O(n2n)           B、O(nlogn)     C、O(2n)            D、O(n)

  1. 以深度优先格局系统查找难点解的算法称为  (     D   卡塔尔(قطر‎             。

A、分支界限算法      B、可能率算法    C、贪心算法    D、回溯算法

  1. 贯彻最长公共子类别利用的算法是(     B      )。

A、分治攻略          B、动态规划法        C、贪心法         D、回溯法

 

二、 填空题

1.算法的复杂有         时间          复杂性和    空间         复杂性之分。

2、程序是    算法     用某种程序设计语言的现实得以达成。

3、算法的“鲜明性”指的是构成算法的每条  指令  是清晰的,无歧义的。

4.矩阵连乘难题的算法可由  动态规划  设计达成。

5、俄克拉荷马城算法找到的解一定是   正确解。

6、算法是指化解难题的   蓬蓬勃勃种办法  或  叁个经过  。

7、从分治法的相近设计方式能够看来,用它设计出的先几日前常是  递归算法  。

8、难题的    最优子布局脾气  是该难点可用动态规划算法或贪恋算法求解的主要本性。

9、以深度优先方式系统查找难题解的算法称为   回溯法  。

10、数值可能率算法常用于  数值难点   的求解。

11、总结两个算法时间复杂度日常能够测算  循环次数 、  基本操作的频率       或总结步。

12、利用可能率的习性总计相仿值的人身自由算法是__数值概率算法,运营时以一定的可能率获得正确解的自由算法是__蒙特卡罗算法_____________________。

14、解决0/1包包难点得以采取动态规划、回溯法和分层限界法,个中无需排序的是   动态规划    ,需求排序的是  回溯法   ,分支限界法    。
15、使用回溯法进行状态空间树裁剪分支时常有三个正规:节制原则和目标函数的界,N皇后难点和0/1手包难点正巧是二种区别的档案的次序,此中同有时候选取限制典型和对象函数的界开展裁剪的是     0/1手包难题   ,只利用节制标准进行裁剪的是    N皇后难题     。

16、  贪心选拔性质  是名缰利锁算法可行的率先个基本要素,也是名缰利锁算法与动态规划算法的机要差别。

17、矩阵连乘难点的算法可由   动态规划   设计完成。

18、奥马哈算法找到的解一定是  精确解。

19.贪心算法的基本要素是     贪心接纳   质和    最优子构造              性质 。

  1. 动态规划算法的主导思想是将待求解难点分解成若干    子难点        ,先求解  子难题          ,然后从这个  子难点        的解得到原难点的解。

22.算法是由若干条指令组成的东周体系,且要满足输入、   输出           、明确性和      有限性       四条性质。

23、大整数乘积算法是用   分治法   来安排的。

24、以广度优先或以最小花费格局搜索难题解的算法称为   分支限界法   。

25、舍Wood算法总能求得难点的   三个解  。

26、  贪心接纳性质  是名缰利锁算法可行的第贰个基本要素,也是名缰利锁算法与动态规划算法的非常重要差异。

27.神速排序算法是基于       分治政策        的生机勃勃种排序算法。

28.动态规划算法的多个基本要素是.   最优子布局                性质和    重叠子难题                性质 。

 30.回溯法是后生可畏种既蕴涵    系统性             又富含       跳跃性    的找寻算法。

31.分支限界法主要有    队列式(FIFO)                分支限界法和      优先队列式          分支限界法。

32.分支限界法是风华正茂种既包含    系统性        又饱含       跳跃性    的搜索算法。

33.回溯法寻觅解空间树时,常用的二种剪枝函数为   限定函数   和    限界函数          。

34.别的可用Computer求解的主题材料所需的年月都与其   规模   有关。

35.连忙排序算法的习性决定于  划分的对称性  。

三、算法填空

1.包包主题材料的人欲横流算法

void Knapsack(int n,float M,float v[],float w[],float x[])

{

       Sort(n,v,w);

       int i;

       for (i=1;i<=n;i++) x[i]=0;

       float c=M;

       for (i=1;i<=n;i++) {

          if (w[i]>c) break;

          x[i]=1;

          c - =w[i];

          }

       if (i<=n) x[i]=c/w[i];

}

2.最大子段和: 动态规划算法

int MaxSum(int n, int a[])

{

    int sum=0, b=0;   //sum存款和储蓄当前最大的b[j], b存储b[j]

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

        if (b>0)  b+= a[j] ;

        else  b=a[i];     ;    //后生可畏旦某些区段和为负,则从下三个职责累和

 if(b>sum) sum=b;

 

     }

     return sum;

 }        

3.自私自利算法求装载问题

template<class Type>

void Loading(int x[],  Type w[], Type c, int n)

{

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

                             ;

        for (int i = 1; i <= n; i++) x[i] = 0;

        for (int i = 1; i <= n && w[t[i]] <= c; i++)

 {x[t[i]] = 1;

           ;}

}

 

4.利令智昏算法求活动计划难题

template<class Type>

void GreedySelector(int n, Type s[], Type f[], bool A[])

{

       A[1]=true;

       int j=1;

       for (int i=2;i<=n;i++) {

          if (s[i]>=f[j])

{  A[i]=true;

j=i;

 }

          else A[i]=false;

          }

}

 

5.火速排序

template<class Type>

void QuickSort (Type a[], int p, int r)

{

      if (p<r) {

        int q=Partition(a,p,r);

        QuickSort (a,p,q-1卡塔尔国; //对左半段排序

        QuickSort (a,q+1,r卡塔尔国; //对右半段排序

        }

}

 

6.排列难题

Template <class Type>

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

{ //产生[list[k:m]的装有排列

    if(k==m)

     {  //只剩余三个因素

         for (int i=0;i<=m;i++)  cout<<list[i];

         cout<<endl;

    }

    else  //还会有三个要素待排列,递归爆发排列

       for (int i=k; i<=m; i++)

        {

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

           perm(list,k+1;m);

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

     }

  }

 

四、问答题

1.分治法的宗旨理维时将叁个局面为n的标题解释为k个规模异常的小的子难点,那个子难题相互独立且与原难题一样。递归地解这一个子问题,然后将种种子难点的解合并得到原难题的解。

 

2设计动态规划算法的首要步骤为:

(1)寻找最优解的本性,并计算其布局特征。(2)递归地定义最优值。(3)以自底向上的点子总括出最优值。(4)依据总计最优值时得到的消息,结构最优解。

3. 分治法与动态规划法的相符点是:将待求解的标题分解成若干个头难点,先求解子难题,然后从这么些子难点的解拿到原难题的解。

两岸的不一样点是:符合于用动态规划法求解的主题素材,经分解获得的子难点往往不是互相独立的。而用分治法求解的标题,经分解得到的子难题往往是并行独立的。

 

4. 分支限界法与回溯法的相似点是:都以生机勃勃种在难点的解空间树T中找找难点解的算法。

不一致点:(1)求解目的分化;

(2)找寻方式区别;

(3)对扩大结点的强盛格局各异;

(4)存款和储蓄空间的必要分裂。

5用回溯法寻觅子集树的算法为:

void backtrack (int t)

{

  if (t>n) output(x);

    else

      for (int i=0;i<=1;i++) {

        x[t]=i;

        if (constraint(t)&&bound(t)) backtrack(t+1);

      }

}

  1. 分治法所能消释的难题日常装有的多少个特色是:

(1)该难点的范围压缩到一定的水平就足以轻松地缓慢解决;

(2)该难题能够表明为多少个规模相当的小的同样难题,即该难题具有最优子布局本性;

(3)利用该难点解释出的子难题的解能够统意气风发为该难题的解;

(4)原难题所疏解出的种种子问题是相互独立的,即子难点之间不含有公共的子难题。

  1. 用分支限界法设总括法的步骤是:

(1卡塔尔国针对所给难题,定义难点的解空间(对解举行编码);分

(2卡塔尔(قطر‎鲜明易于搜索的解空间构造(按树或图协会解) ;

(3卡塔尔(قطر‎以广度优先或以最小花销(最大收入)优先的方法寻找解空间,并在找寻进度中用剪枝函数幸免无效寻觅。

  1. 广大的两种分支限界法的算法框架

(1)队列式(FIFO卡塔尔国分支限界法:依照队列先进先出(FIFO)原则选择下叁个节点为扩充节点。 (2)优先队列式分支限界法:依据优先队列中规定的预先级选用优先级最高的节点成为近来增添节点。

 

  1. 回溯法中管见所及的两类规范的解空间树是子集树和排列树。

当所给的主题素材是从n个成分的集合S中寻觅满足某种性质的子集时,相应的解空间树称为子集树。那类子集树经常常有2n个叶结点,遍历子集树需O(2n卡塔尔国总结时间 。

当所给的主题素材是规定n个成分满足某种性质的排列时,相应的解空间树称为排列树。那类排列树平常常有n!个叶结点。遍历排列树必要O(n!卡塔尔计算时间。

  1. 分支限界法的检索计谋是:     

    在强盛结点处,先生成其全体的幼子结点(分支),然后再从当下的活结点表中选择下多个扩充结点。为了有效地采纳下生龙活虎扩充结点,加快搜索的历程,在每三个活结点处,总括贰个函数值(限界),并依据函数值,从脚下活结点表中精选叁个最平价的结点作为扩充结点,使寻找朝着解空间上有最优解的分层推动,以便尽早地寻觅三个最优解。

 

五、算法题

1. 给定已按升序排好序的n个成分a[0:n-1],现要在这里n个因素中搜索风度翩翩一定成分x,重临其在数组中之处,即使未找到再次回到-1。

写出二分查找的算法,并深入分析其时间复杂度。

  1. template<class Type>

int BinarySearch(Type a[], const Type& x, int n)

{//在a[0:n]中找出x,找到x时重返其在数组中的地点,不然重回-1

     Int left=0;  int  right=n-1;

     While (left<=right){

        int middle=(left+right)/2;

        if (x==a[middle]) return middle;

        if (x>a[middle]) left=middle+1;

        else right=middle-1;

      }

      Return -1;

}

日子复杂性为O(logn卡塔尔(قطر‎

  1. 运用分治算法写出归拢列排在一条线序的算法,并深入分析其时间复杂度

  2. void MergeSort(Type a[], int left, int right)   

   {

      if (left<right) {//至少有2个元素

      int i=(left+right)/2;  //取中点

      mergeSort(a, left, i);

      mergeSort(a, i+1, right);

      merge(a, b, left, i, right卡塔尔;  //归并到数组b

      copy(a, b, left, right卡塔尔(قطر‎;    //复制回数组a

      }

   }

算法在最坏景况下的年华复杂度为O(nlognState of Qatar。

 

3.N皇后回溯法

bool Queen::Place(int k)

{ //检查x[k]地方是或不是合法

 

  for (int j=1;j<k;j++)

    if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;

  return true;

}

 

void Queen::Backtrack(int t)

{

  if (t>n) sum++;

  else    for (int i=1;i<=n;i++) {

      x[t]=i;

      if (   约束函数  卡塔尔(قطر‎ Backtrack(t+1State of Qatar;

    }

}

 

4.最大团难题

void Clique::Backtrack(int iState of Qatar // 计算最大团

{  if (i > nState of Qatar { // 达到叶结点

      for (int j = 1; j <= n; j++) bestx[j] = x[j];

      bestn = cn;   return;}

 // 检查极点 i 与这几天团的总是

   int OK = 1;

   for (int j = 1; j < i; j++)

      if (x[j] && a[i][j] == 0) {         // i与j不相连

         OK = 0;  break;}

 

   if (OK 卡塔尔(قطر‎ { // 步入左子树

      x[i] = 1;  cn++;

      Backtrack(i+1);

      x[i] = 0; cn--;  }

  

  if (     cn + n - i > bestn       卡塔尔国 { // 步向右子树

      x[i] = 0;

      Backtrack(i+1);  }

}

5.最长公共子体系难点

6.QX56曼编码算法

 

 

算法设计与解析试题

 

一、概念题

1.队列    2. 一心二叉树    3.堆        4.P类难题      5.NP标题

 

二、前后相继填空题

1.开间优先图周游算法

procedure bft(g,n)

      //g的上涨的幅度优先周游//

          declare visited(n)

          for iß1 to n do  //将全部结点标志为未访问//

                    ⑴        

          repeat

          for i<--1 to n do  //频频调用bfs//

            if visited(i)=0 then      ⑵          endif

          repeat   

        end bft

2.找二个图的全体m—着色方案 

     procedure  mcoloring(k)

//那是图着色的一个递归回溯算法。图g用它的布尔邻接矩阵graPh(1:n,1:n卡塔尔国表示。它计算并打字与印刷出适合以下须求的漫天解,把整数1,2,…,m分配给图中逐后生可畏结点且使相挨近的结点的有两样的整数。k是下三个要着色结点的下标。//

global integer  m,n,x(1:n)boolean  graPh(1;n,1:n)

integer k

loop  //发生对x(kState of Qatar全部的官方赋值。//

    call nextvalue(k卡塔尔(قطر‎。//将风华正茂种合法的水彩分配给x(kState of Qatar//

    if     ⑴         then  exit  endif  //未有可用的水彩了//   

     if     ⑵      

      then print(xState of Qatar  //至多用了m种颜色分配给n个结点//  

     else call  mcoloring<k+1卡塔尔国  //全部m—着色方案均在那每每递归调用中发出//

    endif

    repeat

    end mcoloring

 

三、问答题

1.二分查找的思想是如何?

2.请用递归方法写出归总列排在一条线序法的主要思考和算法。  

3.已知如下多段图,请用动态规划方式的向后管理法写出求解此主题素材的递推公式并做到对各结点的考虑。

   

                   

  1. 微小自然数:求全体下列两日个性的细小自然数n:
        (1卡塔尔(قطر‎n的个位数是6;
        (2卡塔尔若将n的个位数移到其它各位数字以前,所得的新数是n的4倍。

唤醒:仍用穷举法寻找,当找到三个切合条件者便结束。“找到便消声匿迹”的再度,宜利用repeat-until循环。

 

  1. 以二叉链表为存款和储蓄构造,分别写出求二叉树结点总量及叶子总的数量的算法。

 

 Copyright ©2016伊甸一点

TAG标签:
版权声明:本文由澳门mgm官网发布于新闻,转载请注明出处:澳门mgm官网算法期末考试练习题,大学算法深入