- 1、本文档共53页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 我们设k个元素的错位全排列的个数记做:W(k)。 四个元素的错位排列W(4)我们用穷举法可以找到如下9个: (4,3,2,1)(3,4,1,2)(2,1,4,3) (4,1,2,3)(3,4,2,1)(3,1,4,2) (4,3,1,2)(2,4,1,3)(2,3,4,1) 它们有什么规律呢? 分析 通过反复的试验,我们发现事实上有两种方式产生错位排列: ?A.将k与(1,2,…,k-1)的某一个数互换,其他k-2个数进行错排,这样可以得到(k-1)×W(k-2)个错位排列。 ?B.另一部分是将前k-1个元素的每一个错位排列(有W(k-1)个)中的每一个数与k互换,这样可以得到剩下的(k-1)×W(k-1) 个错位排列。 根据加法原理,我们得到求错位排列的递推公式W(k): W(k) = (k–1) * [W(k–1)+W(k–2)] 分析 构造法 “构造法”解题,就是构造数学模型解决问题。包括直接构造问题解答的模型,图论模型,网络流模型以及组合数学模型。 构造法解题的思路或步骤 构造法解题的类型: 直接构造问题解答。这只是构造法运用的一种简单类型。它只能针对问题本身,探索其独有性质,不具备可推广性。 数学建模。通过沿用经典的数学思想建立起模型;或者提取现实世界中的有效信息,用简明的方式表达其规律,这种规律可以是一条代数公式、一幅几何图形,一个物理原理、一个化学方程式,等等。 无论是直接构造问题解答还是构造数学模型,都要通过算法实现。如何设计一个有较低编程复杂度和时空复杂度且结构清晰的算法,十分重要。通常考虑的因素有 选择的模型必须尽量多地体现问题的本质特征。但这并不意味着模型越复杂越好,累赘的信息会影响算法的效率。 模型的建立不是一个一蹴而就的过程,而是要经过反复地检验、修改,在实践中不断完善。 数学模型通常有严格的格式,但程序编写形式可不拘一格。 利用数学方法进行构造 例1:求Fibonacci数列 定义:f0=f1=1, fn=fn-1+fn-2(n=2)。{fi}称为Fibonacci数列。 输入n,求fn mod q。其中1=q=30000。n=109 【解题分析】 简单的模拟显然不能满足题目的要求,我们考虑构造解答。 定义矩阵 0 1 1 1 为A, 发现(x,y)×A=(y,x+y),恰好与 数列性质相似 。 于是有,? 有(1,1)×A=(1,2), (Fi,Fi+1)×A=(Fi+1,Fi+Fi+1)=(Fi+1,Fi+2) , 即(1,1)×An=(Fn,Fn+1) 在㏒(n)的时间内即可出解。 ? 例题2: 毛毛虫是含N个节点的一棵树,它包含一条主链,所有点要么在链上,要么和主链上某点相邻。我们希望给毛毛虫的每个顶点标号1,2,3,…,N,使得所有边的两端节点标号差的绝对值恰好包含了1,2,3,…,N-1,每个数正好一次(N=10000)。 8 1 5 2 9 48 6 3 7 2 6 3 5 8 1 4 7 这个题目初看上去,似乎无从下手。由于题目中所给的这种特殊的树以及顶点标号的约束条件都是我们以前没有见到过的,再加上数据的规模很大,最大可以达到N=10000。使得我们不得不朝着贪心或者构造的方向去思考。 首先观察样例,再进行了一些尝试后,我们找到了对于样例的很多种合法的标号,其中有一种引起了我们的注意,如下图所示: 1 9 2 3 4 8 7 6 5 1 2 3 4 5 6 7 8 很容易发现,图中边的权值,也就是边的两端顶点标号差的绝对值,是从左向右依次递减的。这个发现使我们不由得想到,是不是对于所有的毛毛虫都存在一种这样的合法标号方式。 例题分析 一序列(见文本) 利用图论模型进行构造 例题3:圆桌吃饭问题 n个人围着一张圆桌吃饭,每个人都不愿意两天与同一人为邻,问最多能坐多少天,并给出一种排列方案? 转化为图论模型 设G=(V,E)为一完全图,|V|=n。图中的每个顶点代表一个人,连结顶点的边表示人之间的相邻关系。因此,每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=v1,v2,…,vn为G中的一条哈密尔顿回路,其中所含的边的集合记为e(L)。问题转化为: 求m与L1,L2,…,Lm,使得e(Li)∩e(Lj)=φ, 并且m达到最大值。 构造方法 作一圆,把圆周分成n-1等分,标上n-1
您可能关注的文档
- 《快乐读书》小学生主题队会活动.ppt
- 动物词汇的文化内涵.ppt
- 《思念食品人力资源管理培训》.ppt
- 会考复习物质的组成结构化学键.ppt
- 会计电算化说课(必威体育精装版).ppt
- 动画作品之爱情篇.ppt
- 伟大的创造源于学习和模仿.ppt
- 《我们的民族小学1》.ppt
- 传感器基础之误差分析处理.ppt
- 传播与艺术性的联姻.ppt
- 2020年工作得失总结心得_个人工作得失心得 .pdf
- 2020-2021学年度教科版八年级物理上册同步练习——第6章质量与密度.pdf
- 2021-2022学年山东省济南市平阴县七年级(上)期末数学试题及答案解析.pdf
- 2021-2022学年北师大版七年级数学上册《第3章整式及其加减》期末综合.pdf
- 2020年高考化学提升突破专题十 电化学知识的应用(含答案) .pdf
- 2020年协同管理软件行业分析报告 .pdf
- 2021-2022年初级银行从业资格之初级银行管理押题练习试卷B卷附答案.pdf
- 2020-2021学年人教版道德与法治八年级下册 4.2依法履行义务 课堂练习.pdf
- 2020-2021学年苏教版三年级下册数学第六单元测试 (含答案) .pdf
- 2019版七年级数学下册第五章生活中的轴对称5.1轴对称现象 .pdf
文档评论(0)