- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
实用标准文案
精彩文档
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算法的思想。
3.若n=4,在机器M1和M2上加工作业i所需的时间分别为ai和bi,且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案,并计算最优值。
4.使用回溯法解0/1背包问题:n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。
5.设S={X1,X2,···,Xn}是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二叉有哪些信誉好的足球投注网站树中有哪些信誉好的足球投注网站一个元素X,返回的结果有两种情形,(1)在二叉有哪些信誉好的足球投注网站树的内结点中找到X=Xi,其概率为bi。(2)在二叉有哪些信誉好的足球投注网站树的叶结点中确定X∈(Xi,Xi+1),其概率为ai。在表示S的二叉有哪些信誉好的足球投注网站树T中,设存储元素Xi的结点深度为Ci;叶结点(Xi,Xi+1)的结点深度为di,则二叉有哪些信誉好的足球投注网站树T的平均路长p为多少?假设二叉有哪些信誉好的足球投注网站树T[i][j]={Xi,Xi+1,···,Xj}最优值为m[i][j],W[i][j]= ai-1+bi+···+bj+aj,则m[i][j](1=i=j=n)递归关系表达式为什么?
6.描述0-1背包问题。
三、简答题(30分)
1.流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为ai和bi,请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。(函数名可写为sort(s,n))
2.最优二叉有哪些信誉好的足球投注网站树问题的动态规划算法(设函数名binarysearchtree))
答案:
一、填空
1.确定性 有穷性 可行性 0个或多个输入 一个或多个输出
2.时间复杂性 空间复杂性 时间复杂度高低
3. 该问题具有最优子结构性质
4.{BABCD}或{CABCD}或{CADCD}
5.一个(最优)解
6.子问题 子问题 子问题
7.回溯法
8. o(n*2n) o(min{nc,2n})
9.最优子结构 重叠子问题
10.动态规划法
二、综合题
1.①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解;
2. ①令N1={i|aibi},N2={i|ai=bi};②将N1中作业按ai的非减序排序得到N1’,将N2中作业按bi的非增序排序得到N2’;③N1’
3.步骤为:N1={1,3},N2={2,4};
N1’={1,3}, N2
最优值为:38
4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),
(1,1,0),(1,1,1)}。
解空间树为:
A
A
B
C
F
E
D
G
K
J
I
H
O
N
M
L
1
1
1
0
0
0
0
1
0
1
1
0
1
0
该问题的最优值为:16 最优解为:(1,1,0)
5.二叉树T的平均路长P=+
m[i][j]=W[i][j]+min{m[i][k]+m[k+
您可能关注的文档
- 数学建模实例—-汽车购买决策.doc
- 数学建模-食堂排队问的题目.doc
- 数学建模售货亭地位置选择问的题目-.doc
- 数学建模选址问的题目.doc
- 数学建模-药物浓度与药效地研究.doc
- 数学建模--运输问的题目.doc
- 数学模型课程设计报告材料范文.doc
- 数学模型期末考试试的题目及问题详解.doc
- 数学期望在经济决策中地运用.doc
- 数学实验5:线性代数方程组地数值解法.doc
- 2024年江西省寻乌县九上数学开学复习检测模拟试题【含答案】.doc
- 2024年江西省省宜春市袁州区数学九上开学学业水平测试模拟试题【含答案】.doc
- 《GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语》.pdf
- 中国国家标准 GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语.pdf
- GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- 《GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构》.pdf
- 中国国家标准 GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 中国国家标准 GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 《GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南》.pdf
文档评论(0)