logo

您所在位置网站首页 > 海量文档  > 计算机 > 软件编程

正难则反浅谈逆向思维在解题中的应用.ppt 24页

本文档一共被下载: ,您可全文免费在线阅读后下载本文档。

  • 支付并下载
  • 收藏该文档
  • 百度一下本文档
  • 修改文档简介
全屏预览

下载提示

1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值,立即自动返金币,充值渠道很便利
特别说明: 下载前务必先预览,自己验证一下是不是你要下载的文档。
  • 上传作者 爱是你我(上传创作收益人)
  • 发布时间:2019-05-15
  • 需要金币100(10金币=人民币1元)
  • 浏览人气
  • 下载次数
  • 收藏次数
  • 文件大小:709.5 KB
下载过该文档的会员
你可能关注的文档:
正难则反 —— 浅谈逆向思维在解题中的应用 引入 有一排路灯,一共八盏,均关闭。要求打开其中三盏,没有任意两盏相邻,有多少种不同的方式。 如果直接考虑三盏打开的灯,需要讨论! 不妨来考虑没有被打开的那些灯。 引入 要开3盏灯,则有5盏是关闭的 两盏相邻的关闭的灯之间只能插入一盏开着的灯 等价于在六个可选位置中选三个插入开着的灯 所以答案为C(6,3) 逆向思维 引入 逆向思维是一种思考问题的方式,它有悖于通常人们的习惯,而正是这一特点,使得许多靠正常思维不能或是难于解决的问题迎刃而解。 问题 答案 例一、Dinner Is Ready [题目描述] M根骨头分给n个孩子,第i个孩子有两个参数Mini和Maxi,表示第i个孩子至少要得到Mini根骨头,至多得到Maxi根骨头。 给出n(0<n≤8) , M(0<M)以及Mini和Maxi (0≤Mini≤Maxi≤M) 计算有多少种分配方案(骨头不能浪费,必须都分给孩子们) 例一、Dinner Is Ready 实例: N=3 M=7 Min1=1 , Max1=2 Min2=2 , Max2=4 Min3=3 , Max3=6 1 2 4 1 3 3 2 2 3 3组可行方案 例一、Dinner Is Ready 该题模型即求如下方程组的整数解的个数: X1+X2+X3+…+Xn=M Min1 ≤X1 ≤Max1 Min2 ≤X2 ≤Max2 …… Minn ≤Xn ≤Maxn 对于方程组的简单形式 xxxX1+X2+…+Xn=M xxxXi ≥ 0(1≤i≤n) 我们知道方程解数为C(M+n-1,n-1) 设Yi = Xi + Mini 则方程组变为: Y1+Y2+Y3…+Yn=M-Min1-Min2-…-Minn 0 ≤Y1 ≤Max1-Min1 0 ≤Y2 ≤Max2-Min2 …… 0 ≤Yn ≤Maxn-Minn 下界我们可以通过换元得到简单形式 但是上界仍然无法解决! 例一、Dinner Is Ready 设S为全集,表示满足Xi≥Mini的整数解集。 设Si为S中满足约束条件Xi≤Maxi的整数解集, Si为Si在S中的补集,即满足Xi>Maxi(Xi≥Maxi+1) |Si|无法计算,但是,|Si|可解!!! 那么,我们是否可以通过可解的|Si|从而得到无法计算的|Si|呢? 例一、Dinner Is Ready 于是,我们就得到了: 例一、Dinner Is Ready 至此,问题已经被解决。 时间复杂度为O(2n*(n+M)) 在原集合Si的模|Si|不可解的情况下,我们通过可解的|Si|得到了一个基于容斥原理的算法。 例二、Greedy Path [题目描述] 给定一个有向图G=(V,E) 对于e∈E,有参数Ce和Te,分别表示该条边的费用与时间。 求一个回路,使得回路中费用总和与时间总和的比值最大。 例二、Greedy Path 题目是求一条回路,但不是边权和最大或者最小,不能直接使用经典算法,似乎无从下手。 我们的目标是找一条回路C=(V’,E’) , 使得F(C)最大: 例二、Greedy Path 设S为G中所有回路组成的集合。 假定C*=(V*,E*) ∈S就是我们要求的最优回路 定义函数O(t) : 例二、Greedy Path 我们做一个猜想: 如果有o (t*)=0,也就是存在C* = (V*,E*) ∈S 满足: 我们认为C*就是最优回路! 证明:如果存在另一条回路C1=(V1,E1) ∈S更优 则 与O(t*)=0矛盾 例二、Greedy Path 更进一步,可以发现: 如果t*是最优答案,则存在: 根据该性质,便得到了算法: 我们只要从一个包含t*的区间(tl,th)开始,不断地二分,计算o((tl+th)/2),得到新的上下界,直到达到精度要求。时间复杂度为O(lgK*N3) 例三、Building Towers [题目描述] 用N块积木来搭建H层的塔(不一定要用完所有的积木) 要求相邻的两层积木数量相差为1 最底层积木数量为M (N≤32767, H≤60, M≤10) 任务1:可以搭建成多少种不同的塔? 任务2:用H个整数从底到顶表示一个塔的结构,问字典序第K小的塔是什么? (H=6 , M=2 , N=13) 例三、Building Towers 动态规划算法 用F[i,j,k]表示当前层有i块砖,还剩下j层,可用的砖块数量为k的方案总数 动态规划方程 : F[i,j,k] = F[i+1

发表评论

请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
用户名: 验证码: 点击我更换图片

2010-2013 max.book118.com在线文档投稿赚钱网. All Rights Reserved 蜀ICP备08101938号