- 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
您可能关注的文档
- 检测技术1(中ch1).ppt
- 检测技术03.ppt
- 检测技术WSL-第02讲 检测系统的基本特性.ppt
- 检测技术第3章.ppt
- 检测技术基础3周-应变片.ppt
- 检测技术下篇6章下.ppt
- 检测理论.ppt
- 检测与传感器2.ppt
- 检测与转换技术复习.ppt
- 检测元件.ppt
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
最近下载
- 7.2 类比推理及其方法-高中政治课件 (统编版选择性必修3).pptx VIP
- 《数学物理方程-福州大学-江飞》作业chapter1.pdf VIP
- 重庆渝北中交·中央公园 C96, C98-1 地块山地新中式商业街项目 GOA.pdf
- 2024年江苏省高考物理真题试卷含答案.pdf VIP
- 《数学物理方程-福州大学-江飞》数学物理方程A.doc VIP
- 《数学物理方程-福州大学-江飞》作业chapter2.ppt VIP
- 《数学物理方程-福州大学-江飞》第四章.doc VIP
- 《数学物理方程-福州大学-江飞》数学物理方程A答案.doc VIP
- 2023年辽宁省检察系统招聘聘用制书记员考试真题及答案.docx VIP
- 2024年高考真题——物理(河北卷)含答案.pdf VIP
文档评论(0)