算法分析及设计习题集整理Word文档格式.docx
- 文档编号:7728381
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:28
- 大小:252.44KB
算法分析及设计习题集整理Word文档格式.docx
《算法分析及设计习题集整理Word文档格式.docx》由会员分享,可在线阅读,更多相关《算法分析及设计习题集整理Word文档格式.docx(28页珍藏版)》请在冰点文库上搜索。
2、什么是算法?
算法的特征有哪些?
1)算法:
指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲,算法:
就是解决问题的方法或过程。
2)特征:
1)算法有零个或多个输入;
2)算法有一个或多个输出;
3)确定性;
4)有穷性
3、给出算法的定义?
何谓算法的复杂性?
计算下例在最坏情况下的时间复杂性?
j++)
(1)
for(i=1;
i++)
(2)
(3)
k++)(4)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}(5)
1)定义:
2)算法的复杂性:
指的是算法在运行过程中所需要的资源(时间、空间)多少。
所需资源越多,表明算法的复杂性越高
3)该算法的主要元操作是语句5,其执行次数是n3次。
故该算法的时间复杂度记为O(n3).
4、算法A和算法B解同一问题,设算法A的时间复杂性满足递归方程
,算法B的时间复杂性满足递归方程
,若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶,a的最大整数值可取多少?
分别记算法A和算法B的时间复杂性为
和
,解相应的递归方程得:
依题意,要求最大的整数a使得
〈
。
显然,当a<
=4时,
;
当a>
4时,
a<
=16。
所以,所求的a的最大整数值为15。
5、算法分析的目的?
1)为了对算法的某些特定输入,估算该算法所需的内存空间和运行时间;
2)是为了建立衡量算法优劣的标准,用以比较同一类问题的不同算法。
6、算法设计常用的技术?
(写5种)
答:
①分治法;
②回溯法;
③贪心法;
④动态规划法
⑤分治限界法;
⑥蛮力法;
⑦倒推法
三、算法设计题
1、蛮力法:
百鸡百钱问题?
2、倒推法:
穿越沙漠问题?
第二章分治算法
(1)----递归循环
1、直接或间接地调用自身的算法称为递归算法,用函数自身给出定义的函数称为递归函数。
2、递归方程和约束函数(递归终止条件)是递归函数的两个要素。
二、判断题:
1、所有的递归函数都能找到对应的非递归定义。
(√)
2、定义递归函数时可以没有初始值。
(X)
三、简答题:
1、什么是递归算法?
递归算法的特点?
1)递归算法:
是一个模块(函数、过程)除了可调用其它模块(函数、过程)外,还可以直接或间接地调用自身的算法。
2)递归算法特点:
①每个递归函数都必须有非递归定义的初值;
否则,递归函数无法计算;
(递归终止条件)
②递归中用较小自变量函数值来表达较大自变量函数值;
(递归方程式)
2、比较循环与递归的异同?
1)相同:
递归与循环都是解决“重复操作”的机制。
2)不同:
就效率而言,递归算法的实现往往要比迭代算法耗费更多的时间(调用和返回均需要额外的时间)与存贮空间(用来保存不同次调用情况下变量的当前值的栈栈空间),也限制了递归的深度。
每个迭代算法原则上总可以转换成与它等价的递归算法;
反之不然。
递归的层次是可以控制的,而循环嵌套的层次只能是固定的,因此递归是比循环更灵活的重复操作的机制。
3、递归算法解题通常有三个步骤?
1)分析问题、寻找递归:
找出大规模问题与小规模问题的关系,这样通过递归使问题的规模逐渐变小。
2)设置边界、控制递归:
找出停止条件,即算法可解的最小规模问题。
3)设计函数、确定参数:
和其它算法模块一样设计函数体中的操作及相关参数。
四、算法设计题:
1、楼梯上有n个台阶,上楼时可以上1步,也可以上2步,设计一递归算法求出共有多少种上楼方法F(n)。
①写出F(n)的递归表达式?
②并写出其相应的递归算法?
解:
①写出F(n)的递归表达式
分析:
到n阶有两种走法:
1)n-1阶到n阶;
2)n-2阶到n阶;
1n=1
F(n)=2n=2
F(n-1)+F(n-2)n>
2
②写出其相应的递归算法?
IntF(intn)
{
if(n=1)return1;
elseif(n=2)
return2;
else
returnF(n-1)+F(n-2);
}
2、设a,b,c是3个塔座。
开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。
各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则:
规则1:
每次只能移动1个圆盘;
规则2:
任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则3:
在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。
①写出该问题的解题步骤?
①第一步:
将n-1个盘子看成一个整体,从A移到C;
第二步:
将第n个盘子移到B;
第三步:
将n-1个盘子看成一个整体,从C移到B;
②写出其相应的递归算法:
voidhanoi(intn,inta,intb,intc)
{if(n>
0)
{
hanoi(n-1,a,c,b);
move(a,b);
hanoi(n-1,c,b,a);
}}
第二章分治算法
(2)分治算法
1、在快速排序、插入排序和合并排序算法中,插入排序算法不是分治算法。
2、合并排序算法使用的是分治算法设计的思想。
3、二分搜索算法是利用分治算法思想设计的。
1、适合用分治算法求解的问题具有的基本特征?
1)该问题的规模缩小到一定的程度就可以容易解决;
2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
3)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。
4)利用该问题分解出子问题解可以合并为该问题解;
2、分治算法基本思想,解题步骤?
三、算法设计题:
1、改写二分查找算法:
设a[1…n]是一个已经排好序的数组,改写二分查找算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i,和大于x的最小元素位置j;
当搜索元素x在数组中时,i和j相同,均为x在数组中的位置。
并分析其时间复杂度?
intbinsearch(inta[n],intx,)//x待查数据
{intmid,i,j;
low=1;
inthigh=n;
while(low<
=high)
{mid=(low+high)/2;
if(a[mid]=x)returni=j=mid;
if(a[mid]>
x)high=mid-1;
//继续在左边查找
else//(a[mid]<
x)
low=mid+1;
//继续在右边查找
}
i=right;
j=left;
return0;
//low大于high查找区间为空,查找失败
}
计算时间复杂性为O(logn)
2、棋盘覆盖在一个2k×
2k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
求:
①简述分治算法的基本思想?
②设计该棋盘覆盖问题的分治算法?
③计算所设计算法的时间复杂度?
(要求写出递推公式)
①
分解:
将一个难以直接解决的大问题,分割成一些规模较小的相同子问题,以便各个击破,分而治之。
对这k个子问题分别求解:
如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止
求小问题解、合并:
将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
②、③
3、金块问题(求最大最小元问题)
老板有一袋金块(共n块),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。
假设有一台比较重量的仪器,我们希望用最少的比较次数找出最重的金块。
②设计该金块问题的分治算法?
(要求写出递推公式)
①简述分治算法的基本思想:
问题可以简化为:
在含n(n是2的幂(n>
=2))个元素的集合中寻找极大元和极小元。
用分治法(二分法)可以用较少比较次数地解决上述问题:
1)将数据等分为两组(两组数据可能差1),目的是分别选取其中的最大(小)值。
2)递归分解直到每组元素的个数≤2,可简单地找到最大(小)值.
3)回溯时将分解的两组解大者取大,小者取小,合并为当前问题的解。
②、③
第三章动态规划算法
1、动态规划算法中存储子问题的解是为了避免重复求解子问题。
2、(最优子结构)是问题能用动态规划算法求解的前提。
3、矩阵连乘问题的算法可由(
动态规划
)算法设计实现。
1、动态规划算法基本要素的是最优子结构。
2、最优子结构性质是指原问题的最优解包含其子问题的最优解。
3、动态规划算法求解问题时,分解出来的子问题相互独立。
(X)
1、动态规划算法解题步骤?
①找出最优解的性质,并刻划其结构特征;
(即原问题的最优解,包含了子问题的最优解)
②递归地定义最优值;
(即子问题具有重叠性,由子问题定义原问题)
③以自底向上的方式计算出最优值;
④根据计算最优值时得到的信息,构造最优解;
2、动态规划算法基本思想?
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题;
但是经分解得到的子问题往往不是互相独立的。
不同子问题的数目常常只有多项式量级。
在用分治法求解时,有些子问题被重复计算了许多次;
如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
3、动态规划与分治算法异同点?
4、动态规划算法的基本要素?
四、算法设计与计算题:
1、
的最长公共子序列为
问:
若用
记录序列
公共子序列长度。
①用动态规划法求解时,计算最优值的递归公式?
②设计计算最优值的算法?
以及构造最优解的算法?
2、长江游艇俱乐部在长江上设置了n个游艇出租站1,2…n.游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。
游艇出租站i到游艇出租站j之间的租金为r(i,j),其中1<
=i<
=n;
①用动态规划法求解时,计算最优值(最少租金)的递归公式?
②设计计算最优值(最少租金)的算法?
③并分析其时间复杂度?
②计算最优值算法
publicstaticvoidmatrixChain(int[]p,int[][]m,int[][]s)
intn=p.length-1;
for(inti=1;
i<
=n;
i++) m[i][i]=0;
//1个站
for(intr=2;
r<
r++)
=n-r+1;
{intj=i+r-1;
m[i][j]=m[i][i]+m[i+1][j];
s[i][j]=i;
//断点位置在i处
for(intk=i+1;
k<
j;
k++)
{int t=m[i][k]+m[k+1][j];
if(t<
m[i][j])
{m[i][j]=t;
s[i][j]=k;
}}}
构造最优解算法
publicvoidtraceback(ints[][],intI,intj)
if(i=j)return;
traceback(s,i,s[i][j]);
traceback(s,s[i][j]+1,j);
System.out.println(“A”+i+“,”+s[i][j]+“A”+s[i][j]+1+“,”+j)
}//(m[i,s[i][j]])(m[s[i][j]+1,j])
③时间复杂度:
O(n3)
第4章贪心算法
1、某单位给每个职工发工资(精确到元)。
为了保证不要临时兑换零钱,且取款的张数最少,统计所需各种币值(100,50,20,10,5,2,1元共七种)的张数。
贪心算法如下:
voidgreedy_zhaoling(floatGZ,intB[],intS[])//GZ应发工资
{for(j=1,j<
=7;
j++)//贪心选择,依次给最大币种
{A=GZ/B[j];
//A表示对应j币种张数
S[j]=S[j]+A;
//S[j]存放对应j币种总张数
GZ=GZ-A*B[j];
print(B[i],“----”,S[i]);
//输出币种和对应张数
2、贪心算法的两个基本要素是(贪心选择性)和(最优子结构)。
3、给定n种物品和一个背包。
物品i的重量是Wi,其价值为Vi,背包的容量为M,应如何选择装入背包的物品,使得装入背包中物品的总价值最大。
floatgreedy_knapsack(floatM,floatw[],floatp[],floatx[])
//x[]背包问题最优解,w[]物品重量,P[]物品价值
{intn=w.length;
floatpp=0;
floatmm=M;
//pp计算当前总价值,mm背包剩余载重
for(inti=1;
i++)
{floatww[i]=p[i]/w[i];
//计算物品单位价值ww[]
x[i]=0;
}//初始化
Mergesort(w[],n);
//按单位价值将物品排序,便于贪心选择
i<
i++)//贪心选择,总是选择价值最大放入背包
{if(w[i]<
=mm)//当前物品小于背包剩余载重
{x[i]=1;
mm=mm-w[i];
pp=pp+p[i];
else{x[i]=mm/w[i];
pp=pp+x[i]*p[i];
break;
}//i部分放入背包
returnpp;
1、满足贪心选择性质必满足最优子结构性质。
1、贪心算法的基本思想?
2、贪心算法的基本要素?
3、贪心算法与动态规划算法的异同?
1、假设有7个物品,它们的重量和价值如下表所示。
若这些物品均可以被分割,且背包容量M=150,如果使用贪心方法求解此背包问题(背包不超载的前提下,装载的物品价值达到最大)。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
①利用贪心算法求解该问题时,为了进行贪心选择,首先应该做什么?
然后进行贪心装载,给出一种正确的物品装载顺序?
并给出其最优装载方案?
②利用贪心思想设计该普通背包问题的贪心算法?
③分析其时间复杂度?
①1)依据不同的标准对这些物品进行排序,标准有重量、价值、单位价值;
2)重量从小到大:
FGBAEDC,得到的贪心解为:
FGBAE全部放入,D放入20%,得到价值为165;
价值从大到小:
DFBEGCA,得到的贪心解为:
DFBE全部放入,G放入80%,得到价值为189;
单位价值从大到小:
FBGDECA,得到的贪心解为:
FBGD全部放入,E放入87.5%,得到价值为190.625;
3)显然使用单位价值得出最佳转载方案。
②、③
2、设有n个活动集合,其中每个活动都要求使用同一资源,如足球场,而在同一时间只能有一个活动使用该资源。
每个活动i都有一个要求使用该资源起始时间si和结束时间fi,且si<
fi;
如果选择了活动i,则它在半开区间[si,fi)占用资源。
若两个活动[si,fi)与[sj,fj)不相交,则称活动i与活动j是相容的;
活动安排问题:
就是在所给的活动集合中选出最大相容活动子集合;
①利用贪心算法求解该问题的基本思想?
②设计该活动安排问题的贪心算法?
并分析其时间复杂度?
3、给定下图G=(V,E)是一个无向连通图,对每一条边(v,w),其权值为c(v,w);
①利用prim算法构造其最小生成树,画出其选边的过程?
并构造其算法?
②利用kruskal算法构造其最小生成树,画出其选边的过程?
4、对下图中的有向图,应用Dijkstra算法计算从源(顶点1)到其它顶点间最短路径的过程.
要求:
给出Dijkstra算法的迭代过程,计算源到给个顶点的最短路径?
(用表表示)
见课本123页 表4-2
迭代过程:
第5章回溯算法
一、填空题
1、回溯法与分支限界法搜索方式不同,回溯法按深度优先搜索解空间,分支限界法按广度优先或最小耗费优先搜索解空间。
二、判断题
1、回溯法中限界函数的目的是剪去得不到最优解的子树。
2、分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法,两者的搜索方式是相同的。
三、简答题
1、简述回溯法和分支限界法的相同点和不同点?
2、什么是子集树?
什么是排列树?
什么叫满m叉树?
3、回溯算法的基本思想?
回溯算法的解题步骤?
四、算法设计题
1、n皇后问题
在4×
4格的棋盘上放置彼此不受攻击的4个皇后。
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
用回溯算法解决4皇后问题:
①构造求解该问题的解空间树?
②设计该4皇后问题的回溯算法?
①解空间树
②回溯算法
2、0-1背包问题:
假设有3个物品,它们的重量和价值如下表所示。
若这些物品均不可以被分割,且背包容量M=10,问应该如何装入使背包中物品的总价值最大?
6
5
42
用回溯算法求解该0-1背包问题:
②设计该0-1背包问题的回溯算法?
1)解空间树;
2)
3、图的着色问题:
如下图
给定无向连通图G和m种不同的颜色;
用这m种颜色为图G的各个顶点着色,是否有一种方法使得图G中每一条边的两个顶点着不同颜色;
①构造求解该问题的解空间树?
②设计该图的着色问题回溯算法?
1)解空间树:
2)算法:
doublemcoloring(intmm)
{intm=mm;
//m可用颜色数
doublesum=0;
//sum当前着色方案数
backtrack
(1);
//深度优先搜索解空间
returnsum;
voidbacktrack(intt)
{if(t>
n)//搜索到叶子节点
{sum++;
//着色方案数加1
for(inti=1;
system.out.print(x[i]);
}//输出解,顶点i着颜色x[i]
else//搜索到中间节点
{for(inti=1;
=m;
{x[t]=i;
//顶点t着颜色i=1…m
if(ok(t))backtrack(t+1);
booleanok(intk)//当前着色顶点与以前相邻顶点是否同色
{for(intj=1;
j<
j++)
if(a[k][j]&
&
(x[j]==x[k])) //数组a[][]是图的邻接矩阵
//当前顶点k到j有边:
a[k][j],且色同:
x[j]==x[k]
returnfalse;
elsereturntrue;
③算法分析(m种颜色,n个节点)
计算限界函数,一重for循环时间复杂度:
O(n);
在最坏的情况下每一个内节点都需要判断约束,内节点个数:
1+m+m2+m3+……+mn-1=(mn-1)/(m-1)个;
故图的m着色问题的回溯算法,时间复杂度为:
O(n*mn)。
第六章分支限界算法
1、按照活结点表的组织方式的不同,分支限界法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 习题集 整理