



全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、对于下列各组函数f(n)和g(n),确定f(n)=O(g(n)或或,并简述理由。(12分)(1) (2) (3) 2、试用分治法实现有重复元素的排列问题:设是要进行排列的个元素,其中元素可能相同,试计算的所有不同排列。(13分)3、试用分治法对一个有序表实现二分搜索算法。(12分)4、试用动态规划算法实现0-1闭包问题。(15分)5、试用贪心算法求解下列问题:将正整数n分解为若干个互不相同的自然数之和,使这些自然数的乘积最大。(15分)6、试用动态规划算法实现最大子矩阵和问题:求矩阵A的一个子矩阵,使其各元素之各为最大。(15分)7、试用回溯法解决下列整数变换问题:关于整数的变换和定义如下:。对于给定的两个整数和,要求用最少的变换和变换次数将变为。(18分)1、(1) 证明:O(f)+O(g)=O(f+g) (7分)(2) 求下列函数的渐近表达式:(6分) 3n2+10n; 21+1/n; 2、对于下列各组函数f(n)和g(n),确定f(n)=O(g(n)或或,并简述理由。(15分)(1) (2) (3) 3、试用分治法对数组An实现快速排序。(13分)4、试用动态规划算法实现最长公共子序列问题。(15分)5、试用贪心算法求解汽车加油问题:已知一辆汽车加满油后可行驶n公里,而旅途中有若干个加油站。试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少。(12分)6、试用动态规划算法实现下列问题:设A和B是两个字符串。我们要用最少的字符操作,将字符串A转换为字符串B,这里所说的字符操作包括:(1) 删除一个字符。(2) 插入一个字符。(3) 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的两个字符串A和B,计算出它们的编辑距离d(A,B)。(16分)7、试用回溯法解决下列整数变换问题:关于整数的变换和定义如下:。对于给定的两个整数和,要求用最少的变换和变换次数将变为。(16分) 1、 解:简答如下: (1),(2),(3)2、 解:解答如下: Templatevoid Perm(Type list,int k,int m) if(k= =m) for(int i=0;i=m;i+) coutlisti; .(4分) coutendl;else for(int i=k;i=m;i+) if(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(listk,listi); .(8分) ; 其中ok用于判别重复元素。 Template int ok(Type list,int k,int i) if(ik) for(int t=k;tI;t+) if(listt= =listi) return 0; return 1;.(13分)3、 解:解答如下: Template int BinarySearch(Type a,const Type& x,int n)/假定数组a已按非递减有序排列,本算法找到x后返回其在数组a中的位置,/否则返回-1 int left=0,right=n-1; while(leftamiddle) left=middle+1; .(8分) else right=middle-1;return -1;.(12分)4、 解:解答如下:Templatevoid Knapsack(Type v,int w,int c,int n,Type *m) Int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for(int j=wn;j1;i-) jMax=min(wi-1,c); for(int j=0;j=jMax;j+) mij=mi+1j; for(int j=wi;j=w1) m1c=max(m1c,m2c-w1+v1); .(10分)TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;in;i+) if(mic= =mi+1c) xi=0; .(12分)else xi=1,c-=wi;xn=(mnc)?1:0;.(15分)5、 解:解答如下:void dicomp(int n,int a) k=1;if(n3) a1=0;return;if(nak) k+; ak=ak-1+1; n-=ak;.(10分)if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+;.(15分)6、 解:解答如下:int MaxSum2(int m,int n,int *a) int sum=0;int *b=new intn+1;for(int i=1;i=m;i+) for(int k=1;k=n;k+) bk=0; .(5分) for(int j=i;j=m;j+) for(int k=1;ksum) sum=max; return sum; .(10分) int MaxSum(int n,int *a) int sum=0,b=0; for(int i=1;i0) b+=ai; else b=ai; if(bsum) sum=b;Return sum; .(15分)7、 解:解答如下:void compute() k=1; while(!search(1,n) k+; if(kmaxdep) break; init();.(6分)if(found) output(); else cout”No Solution!”k) return false; fo
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 天然气调峰储备信息化管理平台方案
- 国家安全日主题培训课件
- 处理网络订单教学设计-2025-2026学年中职专业课-电子商务物流-电子商务-财经商贸大类
- 医院旧楼改造施工人员管理方案
- 2025买卖合同模板
- 2025年中医药学经络穴位定位能力考核答案及解析
- 国家安全培训班课件
- 2025年皮肤科湿疹患者护理技巧模拟考试卷答案及解析
- 2025年内科常见慢性病治疗方案模拟测试卷答案及解析
- 2025年血液科白血病患者的化疗药物选择模拟考试试卷答案及解析
- 《新能源汽车》课件 课题四 纯电动汽车
- 金融领域反腐
- 应急物业合同范本(2篇)
- 《机械制图(多学时)》中职完整全套教学课件
- 高原施工保障方案
- 《颅内压增高的临床表现》教学课件
- 三洋洗衣机XQB60-M808使用说明书
- 心理问题与心理障碍
- DL∕ T 802.7-2010 电力电缆用导管技术条件 第7部分:非开挖用改性聚丙烯塑料电缆导管
- (正式版)CB∕T 4557-2024 船舶行业企业劳动防护用品配备要求
- CB-Z-807-2016吊舱推进船舶快速模型试验规程
评论
0/150
提交评论