书签 分享 收藏 举报 版权申诉 / 47
上传文档赚钱

类型《算法艺术与信息学竞赛》标准课件学习培训模板课件.ppt

  • 上传人(卖家):林田
  • 文档编号:4141878
  • 上传时间:2022-11-14
  • 格式:PPT
  • 页数:47
  • 大小:1.24MB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《《算法艺术与信息学竞赛》标准课件学习培训模板课件.ppt》由用户(林田)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    算法艺术与信息学竞赛 算法 艺术 信息学 竞赛 标准 课件 学习 培训 模板
    资源描述:

    1、算法艺术与信息学竞赛标准课件目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)五、最大m子段和O(mn)六、0-1背包问题O(minnc,2n,n1.44n)一、最长公共子序列 Longest Common Subsequence(LCS)分析 考虑前缀x1.i和y1.j,定义ci,j=|LCS(x1.i,y1.j)|则cm,n=|LCS(x,y)|.递推公式为 很直观.考虑xi=yj的情形:关键点一:最优子结构 为了使用动态规划,问题需具备最优子结构最优子结构(Optimal Substructure)直接书写的程序递归树

    2、分析关键点二:重叠子问题 为了让动态规划确实发挥功效,问题应该包含尽量多的重叠子问题重叠子问题(overlapping subproblems)解决方法:记忆化 注意memoization不是memorization自底向上递推空间优化 如果只需要最优值,可以用滚动数组实现 按照i递增的顺序计算,di,j只和di-1,j和di,j-1以及di-1,j-1有关系,因此只需要保只需要保留相邻两行留相邻两行,空间复杂度为O(minm,n)更进一步的,可以只保留一行,每次用单独的变量x保留di-1,j,则递推方程为If(i=j)dj=x;else x=dj;dj=maxdj-1,dj;变形.回文词 给

    3、一个字符串a,保持原字符的顺序不变,至少要加几个字符才能变成回文词?例:abfcbfa afbcfcbfa分析 红、绿色表示原字符,白色为新增字符 显然,s和s在任何一个位置不可能都是白色(不需要加那个字符!)应该让红色字符尽量多!相当于求相当于求s和逆序串和逆序串s的的LCS,让LCS中的对应字符(红色)对齐,中间的每个绿色字符都增加一个字符和它相等二、最优排序二叉树 给n个关键码和它们的频率,构造让期望比较次数最小的排序二叉树分析 定理:定理:最优排序二叉树的子树也是最优排序二叉树 给出关键码-频率对照表(升序排列)问题:把哪个关键码做为根?则左右子树可以递归往下做ABCDE23 1081

    4、2 30FGHIJKLMNOP.514 18 202411722 22 10.分析 用递归来思考,但用递推来做 先考虑两个结点的情形分析 可以用矩阵来保存结果 Cj,k表示从j到k的关键码组成的最优排序二叉树 Rootj,k记录这棵排序二叉树的根分析 考虑三个结点的情形 最优值放在CB,D中,根放在rootB,D中分析 类似地,更新所有Cj-2,j和rootj-2,j分析 四个结点的情形(如A-D)分析 最终计算结果为分析 可以利用root矩阵递归地构造出最优树分析 时间复杂度:计算每个Ci,j和rooti,j需要枚举根结点,故为O(n3)空间复杂度:需要两个n*n矩阵,O(n2)三、最长上升

    5、子序列 最长上升子序列问题(最长上升子序列问题(LIS)给一个序列,求它的一个递增子序列,使它的元素个数尽量多。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7(还有其他的,这里略去)分析 定义di是从第1个元素到第i个元素为止的最长子序列长度,则状态转移方程为 直接使用这个方程得到的是O(n2)算法 下面把它优化到O(nlogn)状态的组织 d值相同的a值只需要保留最小的只需要保留最小的,因此用数组gi表示d值为i的数的a最小值,显然g1=g2=ai,需要更新gj=ai代码 使用STL的lower_bound可以直接求出比ai大的第一个数,用二分查找实现,每次转移时间O(log

    6、n),总时间O(nlogn)fill(g,g+n,infinity);for(inti=0;in;i+)intj=lower_bound(g,g+n,ai)-g;di=j+1;gj=ai;变形1:航线问题 有两行点,每行n个.第一行点和第二行点是一一对应的,有线连接,如下图所示 选择尽量多的线,两两不交叉分析 设与第1行第i个点对应的是第2行第fi个点 假设ij,两条线(i,fi)和(j,fj)的充要条件是fifj,因此问题变成了求求f的最长上升子序列的最长上升子序列 时间复杂度为O(nlogn)变形2:两排列的LCS 给1n的两个排列p1,p2 求p1和p2的最长公共子序列 例:1 5 3

    7、2 4 5 3 4 2 1分析 算法一:直接套用LCS算法,时间O(n2)算法二:注意到把两个排列做相同的置换相同的置换,LCS不变,可以先把p1排列为1,2,3,n1 5 3 2 4 1 2 3 4 5 即映射52,24,45,p2作同样置换5 3 4 2 1 2 3 5 4 1 与1,2,3.n的LCS显然是最长上升子序列,时间降为O(nlogn)推广:DAG上的最短路“上升”依赖于序关系=,它具有一般性 DAG(有向无环图)的最长路径问题:把有向边看成偏序关系,则本题的算法一仍然适用,时间复杂度为O(n2).如果图的边数m比较,可进一步优化到O(m),因为每条边恰好考虑一次(用邻接表或前

    8、向星,而不是邻接矩阵)算法二不再适用算法二不再适用!因为d值相同的a不一定可以两两相互比较,不一定存在最小值.四、最优三角剖分 给一个n个顶点的凸多边形,有很多方法对它进行三角剖分(polygon triangulation)每个三角形有一个权计算公式(如周长,顶点权和),求总权最小(大)的三角剖分方案分析 用di,j表示由顶点i,i+1,j组成的多边形(注意i可以大于j)的最小代价 方案一:枚举三个顶点,组成一个三角形,决策是O(n3)的 方案二:边(i,j)一定属于一个唯一的三角形,设第三个顶点为k,则决策仅为O(n)采用方案二,状态O(n2),决策O(n),总O(n3)分析 确定k后,最

    9、优方案应该是di,k+dk,j+w(i,k,j)因此转移方程di,j=maxdi,k+dk,j+w(i,k,j)变形1:最优矩阵乘法链 需要计算n个矩阵的乘积A1A2An 由于矩阵乘法满足结合律,可以有多种计算方法.例如A1是10*100,A2是100*5,A3是5*50,则 顺序1:(A1A2)A3,代价为10*100*5+10*5*50=7500 顺序2:A1(A2A3),代价为100*5*10+10*100*50=75000 求代价最小的方案(加括号方法)共同的结构 用二叉树二叉树(binary tree)可以表示两个问题相同的结构,每个结点表示一个区间(结点区间/矩阵区间),左子树和右

    10、子树表示分成的两个序列 如果在原问题中让di,j表示i-1j的最优值,则在方程形式上也完全等价变形2.决斗 编号为1n的n个人按逆时针方向排成一圈圈,他们要决斗n-1场。每场比赛在某相邻两人间进行,败者退出圈子,紧靠败者右边的人成为与胜者直接相邻的人。任意两人之间决斗的胜负都将在一矩阵中给出(如果Ai,j=1则i与j决斗i总是赢,如果Ai,j=0则i与j决斗时i总是输),求出所有可能可能赢得整场决斗的人的序号分析 首先把圈想象成一条链 设di,j表示i是否能和j相遇,则相遇的充要条件是存在k,i和k,k和j都能相遇,且i或或j能打败k 同样是O(n2)个状态,决策O(n),总O(n3)五、最大

    11、m子段和 给一个序列a1,a2,an 求m个不相交不相交(可以相接)的连续序列,总和尽量大 例如m=2,1 2-3 4 5-6 7分析 设di,j为以j项结尾的i段和的最大值,则需要枚举此段开头y和上一段结尾x,即di,j=maxdi-1,x+ay.j 每次需要枚举xy=j,决策量为O(n2),状态为O(nm),共O(n3m)注意到如果aj-1也是本段的,答案变成为di,j-1+aj,因此方程优化为di,j=maxdi,j-1+aj,di-1,x+aj,xj分析 优化后状态仍然是二维的,但决策减少为O(n),总O(n2m)可以继续优化.注意到时间主要耗费在对x的枚举上,计算maxdi-1,x.

    12、这个值 我们把d的第一维称为”阶段”,则本题是典型的多阶段决策问题 计算一个阶段时,顺便记录顺便记录本阶段最大值 只保留相邻两个阶段(滚动数组)则时间降为O(nm),空间降为O(n)六、0-1背包问题 给定n种物品和一个背包,物品i的重量是wi,价值是vi,背包容量为c 对于每个物品,要么装背包,要么不装 选择装背包的物品集合,使得物品总重量不超过背包容量c,且价值和尽量大分析 设di,j为背包容量为j时,只考虑前i个物品时的最大价值和 如果装第i个物品,背包容量只剩j-wi 如果不装,背包容量不变 因此di,j=maxdi,j-wi+vi,di-1,j 状态有nc个,每个状态决策只有两个,因

    13、此总时间复杂度为O(nc).用滚动数组后,空间复杂度只有O(c)分析 当c大时,算法效率非常低.事实上,由于c是数值范围参数数值范围参数,一般不把它看作输入规模.这样的O(nc)只是一个伪多项式算法 事实上,如果物品重量和背包容量都是实数时,算法将失败,因为看起来看起来物品的重量和可以是”任何实数”.但事实是:物品重量和只有2n种可能的取值,并不是无限多种分析 算法一:枚举2n个子集合,再计算,枚举2n,计算n,共n2n 算法二:采用递归枚举,共2n 算法三:先考虑一半元素,保存2n/2个和.再考虑后一半元素,每计算出一个和w,查找重量=c-w的元素中价值的最大值.下面考虑实现细节下面考虑实现细节算法三 前一半元素的2n/2个和按重量从小到大排序后放在表a里.对于任何两个和i,j,如果wivj,则j是不需要保存的,因此按重量排序好以后也是按价值排序的 考虑后一半元素时,每得到一个重量w,用二分查找得到重量不超过c-w的最大元素,则它的价值也最大.预处理时间复杂度2n/2log2n/2,每个重量w二分查找时间为log2n/2,因此总2n/2log2n/2=O(n1.414n)

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:《算法艺术与信息学竞赛》标准课件学习培训模板课件.ppt
    链接地址:https://www.163wenku.com/p-4141878.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库