ACM程序设计-东北林业大学acm05
28页1、 今天你AC 了吗?*1第一页,共28页。第6讲DP入门*2第二页,共28页。我校的ACM在线评测系统n n课件下载地址:n 动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。*4第四页,共28页。 原问题的解 原问题 填 表子问题1子问题2子问题n动态规划法的求解过程*5第五页,共28页。n=5时分治法计算斐波那契数的过程。 F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例:计算斐波那契数:*6第六页,共28页。01234567890112358132134动态规划法求解斐波那契数F(9)的填表过程 : 注意到,计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的,所以,可以设计一张表填入n+1个F(n)的值。 *7第七页,共28页。 用动态规
2、划法求解的问题具有特征: 能够分解为相互重叠的若干子问题; 满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。(用反证法)分析问题是否满足最优性原理:1. 先假设由问题的最优解导出的子问题的解不是最优的;2. 然后再证明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。 *8第八页,共28页。动态规划法设计算法一般分成三个阶段:(1)分段:将原问题分解为若干个相互重叠的子问题;(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;(3)求解:利用递推式自底向上计算,实现动态规划过程。 v 动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。*9第九页,共28页。例1斐波那契数列 nefu 85n计算斐波那契数列的值!该数列为1 1 2 3 5 8 13 21 . n有多组数据,每组1行,用N表示,1 = N = 50。 n输出Fibonacci(N)的值! *10第十页,共28页。代码:nint n;n long long feibo51;n feibo1=1;n feibo2=1;n for(i
《ACM程序设计-东北林业大学acm05》由会员suns****4568分享,可在线阅读,更多相关《ACM程序设计-东北林业大学acm05》请在金锄头文库上搜索。
土地管理与地籍测量---第八章界址点测量
人机工程学案例分析(2)
工程安全培训_201303
第9章房地产投资决策分析
第2章房地产经纪制度
ACM程序设计-东北林业大学acm05
《亲爱的汉修先生》读书交流会
中原_深圳新世界尖岗山项目市场汇报_40P_2012年_别墅_项目分析_量价走势
五年级数学质量分析演示文稿
人工智能小镇-智慧小镇建设20180525
景观基本知识及发展历程
建设工程信息管理(2)
机电驱动技术第二章步进驱动技术
工程力学-第9章圆轴扭转时的应力变形分析与强度刚度设计
第一章第二节幼儿园文化环境建设的原则
第一章检测技术的基础知识
第一章__现代表面工程技术
第六章钢结构工程
第9节项目试运行管理
班主任工作经验交流课件(4)
2024-02-03 74页
2024-02-03 76页
2024-02-01 134页
2024-02-01 65页
2024-02-01 72页
2024-02-01 63页
2024-02-01 168页
2024-01-29 43页
2024-01-29 34页
2024-01-29 39页