输入关键词搜索资料
分享
首 页
个人中心
意见反馈
帮助中心
首页 >
行业资料 >
互联网
最长递增子序列
2017-12-10
13页
doc
76KB
62阅读
is_624976
暂无简介
举报
最长递增子序列最长递增子序列 最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么 显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过 的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了 较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。 设L=是n个不同的实数的序列,L的递增子序列是这样一个子序列12n Lin=,其中k是对序列L=按递增排好序的序列。那么显然X与L12n12n 的最长公共子序列即为L的最长递增子序列。这样就把求...
最长递增子序列 最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么 显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过 的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了 较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。 设L=
是n个不同的实数的序列,L的递增子序列是这样一个子序列12n Lin=
,其中k
是对序列L=
按递增排好序的序列。那么显然X与L12n12n 的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长 公共子序列问题LCS了。 最长公共子序列问题用动态规划的算法可解。设Li=< a,a,…,a >,X j=< b,b,…,b >,12i 12j 它们分别为L和X的子序列。令C[ i, j]为Li与X j的最长公共子序列的长度。这可以用时间复 2杂度为O(n)的算法求解,由于这个算法上课时讲过,所以具体代码在此略去。求最长递增子序 2列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n)的时间,算法的最坏 22时间复杂度为O(nlogn)+O(n)=O(n)。 设f(i)表示L中以a末元素的最长递增子序列的长度。则有如下的递推方程: i 这个递推方程的意思是,在求以a为末元素的最长递增子序列时,找到所有序号在L前面且小i 于a的元素a,即j
f[i]-1) f[i]=f[j]+1;//更新f[i]的值。 } } System.out.println(f[n-1]); } 这个算法有两层循环,外层循环次数为n-1次,内层循环次数为i次,算法的时间复杂度 2所以T(n)=O(n)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排 序的时间,所以时间复杂度要优于第一种算法。 在第二种算法中,在计算每一个f(i)时,都要找出最大的f(j)(j
Len) Len++;//更新当前最大递增子序列长度; } System.out.println(Len); } 现在来证明这个算法为什么是正确的。要使算法正确只须证如下命题: 1每一次循环结束数组B中元素总是按递增顺序排列的。 用数学归纳法,对循环次数i进行归纳。 当i=0时,即程序还没进入循环时,命题显然成立。 设i
B[j],因为第i次循环之前数组B12 是递增的,因此第i次循环时B[j]或B[j]必有一个更新,假设B[j]被更新为元素a,由于121i+1a=B[j]> B[j],按算法a应更新B[j]才对,因此产生矛盾;假设B[j]被更新,设更新i+112i+122前的元素为s,更新后的元素为a,则由算法可知第i次循环前有B[j]=s< a< B[j],这i+12i+11与归纳假设矛盾。命题得证。 2B[c]中存储的元素是当前所有最长递增子序列长度为c的序列中,最小的最末元素, 即设当前循环次数为i,有B[c]={a|f(k)=f(j)=c?k,j?i+1?a?a}(f(i)为与第二种算法中jjk 的f(i)含义相同)。 程序中每次用元素a更新B[c]时(c=f(i)),设B[c]原来的值为s,则必有a
p(i))的最长递增子序列后面,就应该能接在B[L]后面,那么就应该有p(i)=L,与L> p(i)矛盾。因此一定有p(i)=f(i),命题得证。 算法的循环次数为n,每次循环二分查找用时logn,所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进。 本
论文
政研论文下载
论文大学下载
论文大学下载
关于长拳的论文
浙大论文封面下载
只给出了计算解的大小而没有给出构造解的方法,因为我认为计算解的大小的算法已 能给出对问题的本质认识,只要计算解大小的算法设计出,构造解就只是技术细节的问题了,而 我关心的是怎样对问题得到很好的认识而设计出良好的算法。以上几种算法已用Java实现,都能得到正确的结果。在设计和改进算法时用到了基本的算法设计和分析、证明的基本方法,很好 的锻炼了设计与分析算法的思维能力,让我从感性上认识到算法分析与设计的重要性,并且感受 了算法分析、设计和改进的乐趣。 【实验目的】 练习掌握动态规划算法。 【实验内容】 设计一个O(n*n)时间的算法,找出由n个数组成的序列的最长单调递增子序列。 【实验条件】 Microsoft Visual C++ 6.0 【需求分析】 题目要求在O(n*n)的时间内找出n个数组成的序列的最长单调递增子序列,需要 用到排序算法,查找最长公共子序列的算法。 【设计原理】 将数组a复制到数组x,先用排序算法将数组x排序,在调用查找最长公共子序 列的算法求出数组a和数组x中的最长公共子序列,因为数组x是单调递增的,所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。 【概要设计】 数据: N:数组元素个数。 a[N]:用于存放数组。 X[N]:复制数组a[N],并排序。 c[i][j]:存储a和x的最长公共子序列的长度。 b[i][j]:记录c[i][j]的值是由哪一个资问题的解得到的。 函数: int Partition(int a[],int p,int t,int x); //数组划分,将小于等于x的元素移到x左边,大于x的元素移到x右边。 void Swap(int &x,int &y); //交换元素x和y。 void QuickSort(int a[],int p,int r); //快速排序。 void LCSL(int m,int n,int *x,int *y,int **c,int **b); //计算最长公共子序列长度。 void LCS(int i,int j,int *x,int **b); 根据b[i][j]的内容打印a,x数组的最长公共子序列。 【详细设计】 #include
#include
using namespace std; #define N 10 void LCSL(int m,int n,int *x,int *y,int **c,int **b);//计算最长公共子 序列长度。 void LCS(int i,int j,int *x,int **b);//根据b[i][j]的内容打印a,x数组 的最长公共子序列。 void QuickSort(int a[],int p,int r);//快速排序。 int Partition(int a[],int p,int t);//数组划分,将小于等于x的元素移到 x左边,大于x的元素移到x右边。 void Swap(int &x,int &y);//交换元素x和y。 //计算最长公共子序列长度 void LCSL(int m,int n,int *x,int *y,int c[][N],int b[][N]) { c[0][0]=0; int i,j; for(i=1;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++) for(j=1;j<=m;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } cout<
x的元素交换到右边区域 while(true) { while(a[--j]>x); while((i
=j)break; Swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } void Swap(int &x,int &y) { int t; t=x; x=y; y=t; } void main(void) { int *a,*x; a=new int[N]; x=new int[N]; int b[N][N]; int c[N][N]; cout<<"请输入十个数:"<
>a[i]; x[i]=a[i]; } QuickSort(x,1,N-1); LCSL(N-1,N-1,a,x,c,b); LCS(N-1,N-1,a,b); }
/
本文档为【最长递增子序列】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
相关资料
单晶材料制备
劳动关系主体、管理方 政府和工会
分包单位资质和人员资格管理制度
属灵书籍目录
初任专业技术职务呈报表
医务科岗位职责及工作制度全
2023土木工程实习日记
手办项目市场营销与品牌运营方案(模板)
国家开放大学电大专科一网一平台《地域文化》教学考多选题题库及答案精品
《金瓶梅词话》校读拾零(五)
[整理]Tiguan装备MT变速箱销售顾问话术
学校更名证明英文
常用颜色调色法+颜色调配表-颜料调色表大全之欧阳体创编
电子商务园建设项目可行性研究报告
浙人社发221.222.223号文
外研版英语七年级上册说课稿
遴选公务员试题
一年级音乐上册第1课《欢迎你》课件湘艺版
科主任会议记录
【备战2016】全国2016届高考语文试题汇编(11月份)o单元 实用类文本阅读
热门搜索
传热学传热学—教材—陈维汉第五章1-5
公司企业车辆管理培训辅导实用PPT解析课件
ISO22000沟通控制程序
转办单
凌云壮语论文
捉竹鸡小窍门[宝典]
基于GIS的生态系统服务直接利用价值评估方法
KPD系列交流变频电动平车组成及原理说明
EN81-70
M580培训-3. 设备集成PPT
《放学了》说课稿
某小区白蚁防治工程招标文件2014
电梯安全管理制度汇编
培训感悟心得_初一记叙文作文300字
传热学传热学—教材—陈维汉第五章1-5
公司企业车辆管理培训辅导实用PPT解析课件
ISO22000沟通控制程序
转办单
凌云壮语论文
捉竹鸡小窍门[宝典]
基于GIS的生态系统服务直接利用价值评估方法
KPD系列交流变频电动平车组成及原理说明
EN81-70
M580培训-3. 设备集成PPT
《放学了》说课稿
某小区白蚁防治工程招标文件2014
电梯安全管理制度汇编
培训感悟心得_初一记叙文作文300字
你可能还喜欢
全球主要资本市场概况
随笔_初一随笔作文300字
电梯定期自行检查记录表
_联邦党人文集_思想探源
epc总承包合同协议范本
管理统计学第六章假设检验 参数假设检验
2023年【人教版新目标七年级上册英语期末复习资料】
2012-2013年度济南市“讲、比”活动十佳科技创新项目
二甲医院评审核心条款任务分解
qs系列水泵规格性能表
公共卫生科管理制度汇编(DOCX 40页)
乐于奉献默无声 甘做绿叶衬红花
四川省成都市双流区双流棠湖中学2023-2024学年数学高三上期末考试模拟试题含解析
小学二级教师定级述职报告
建筑工地罚款单
Unit Big cities课件
化验室电子天平使用记录表
化验室电子天平使用记录表
化验室电子天平使用记录表
化验室电子天平使用记录表
最新资料
资料动态
专题动态
搜索
热门搜索
离婚协议书
入党申请书
房屋租赁合同
贫困申请书
历史搜索
清空历史搜索