上海市控江中学王建德.PPT
《上海市控江中学王建德.PPT》由会员分享,可在线阅读,更多相关《上海市控江中学王建德.PPT(44页珍藏版)》请在三一文库上搜索。
1、上海市控江中学 王建德,浙江集训队辅导讲义,1、2002年竞赛概述,2、构造法,算法知识分布,虽然2002年全国奥林匹克信息学竞赛中含许多可“一题多解” 的试题,但如果按照较优算法标准分类的话,大致可分为,特 点,1、凸现信息学知识和数学知识整合的趋势。为了考核学生的数学能力,激发学生的创造力,2002年全国奥林匹克信息竞赛(NOI)、IOI组队赛和IOI,数论(荒岛野人)、组合分析(机器人M号)、图论类(玩具兵)的试题增加,并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与数学的依赖关系日益凸现,数学素质好的人虽然不一定会编程,但希望学习编程的人愈来愈多;编程解题能力强的人势必有数学
2、的潜质和爱好,他们中愈来愈多的人也希望深造数学。两门学科的交融和整合是奥林匹克信息学活动发展的一个大趋势(有专家提议,数学教材讲算法,信息科技教材讲语言,上海的信息科技教材出现真值表(初中)和c语言(高中)。,2、“构造法”(调皮的小孩、新俄罗斯方块、丹奇方块 )或贪心策略类试题(月亮森林)的引入,使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质知识是不断推陈出新的。,3、试题的综合性增加,并不一定随知识的分类而发生变化,有时几乎找不到一个单一的经典算法(玩具兵通过最短路径构造二分图),也找不到一个纯粹的数据结构问题(银河英雄传说 要求计算并查集中元素的相对位置),关键是你从哪个角度
3、去分析,也就是说能不能综合所学的知识,应用自如地解决问题。选手的综合素质愈高,得胜的机率愈大;,4、经常面对着不知道算法的试题,面对着谁都不知如何处置的情境(经常出现许多选手在一题中得0分、优秀选手表现失常的情况),因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战,成为培训的基本要求和目标。,1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考,有了思考才有解决问题的方法,才有找到独立思路的可能(陶行知)”。有问题虽然不一定有创造,但没有问题一定没有创造(想一想当前的解法有没有缺陷,有没有更好的算法,它与哪些问题有联系,与
4、哪些知识相关联,还可以拓延出哪些问题,要解决这些问题还需要哪些知识);,启 示,2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序,不谋求跳跃式学习,将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时,必须有追逐前沿的选择性学习。这里,有时候心理的障碍比科学上的障碍更难跨越,敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃,不少人还能够实现比较大的跳跃( 2002年noi中的欧拉函数、冬令营营员讲的polya定理、博弈原理和遗传算法,爱笛生小学三年级退学、比尔.盖茨大学三年级
5、退学),学生必须学会从浩如烟海的信息中选择最有价值的知识,构建个性化(符合自己能力结构和兴趣结构)和竞争需要的知识结构 培训内容要有选择性,因为除了出题者,谁也说不清楚在未来竞赛中究竟什么知识是必要的(对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同,有的同年级同学科的教材相差三分之二),因此不可能把所有重要的东西都选择好了给学生,而是应该将直线培训与散点培训相结合,选择部分重要的东西交给学生,让他们自己去探索若干知识点之间的联系,补充自己认为需要补充的知识。,3、参与活动的学生应由竞争关系和独立关系(你做你的,我干我的,程序和算法互相保密,彼此津津乐道于对方的失败和自己的成
6、功)转向合作学习的关系(通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务),学生的心理调适: 我掌握的知识仅不过是沧海一粟(进取心); 固守错误的概念比一无所知更可怕(明智); 三人之行必有我师(谦虚); 知识生产社会化条件下人的基本素质之一是合作精神(现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作,例如制作windows,人类基因工程)(现代意识);,前提条件:水平相当的同质成员或各有所长(包括数学知识、编程能力和思维方式等解题所需的各种因素)的异质成员是开展合作学习的组织基础;,合作学习的效应: 集思广益容易出好的算法; 群体设计的测试数据相对全面; 在群体活动中能
7、比较客观的反映自己能力情况; 每个学生在付出与给予中可提高合作精神和编程能力,成功者往往是那些相容性好、 乐于帮助他人,并且善于取他人之长的学生(符文杰、张一飞等)。,4、选手面对从未遇到过的挑战应调整好心态,不要急功近利,要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两次失误,也是砥砺之石,可从中汲取有益的经验和教训。“不是一番寒彻骨,哪得梅花扑鼻香”。,对一些不能套用简单的条条框框和现成模式、需要独立思考、见解独创和有所创新的非标准题,通过构造数学模型解决问题。数学模型的功能: 解释功能:就是用数学模型说明事物发生的原因; 判断功能:用数学模型判断原来的知识和认识的可靠性。 预见功能:
8、利用数学模型揭示事物的发展规律,为人们的行为提供指导或参考。 构造法解题的思路或步骤可以归纳为:,构造法解题的类型 数学建模:通过沿用经典的数学思想建立起模型;或者提取现实世界中的有效信息,用简明的方式表达其规律,这种规律可以是一条代数公式、一幅几何图形,一个物理原理、一个化学方程式,等等。 直接构造问题解答:只是构造法运用的一种简单类型。它只能针对问题本身,探索其独有性质,不具备可推广性。 通常考虑的因素 选择的模型必须尽量多地体现问题的本质特征。但这并不意味着模型越复杂越好,累赘的信息会影响算法的效率。 模型的建立不是一个一蹴而就的过程,而是要经过反复地检验、修改,在实践中不断完善。 数学
9、模型通常有严格的格式,但程序编写形式可不拘一格。,在建模过程中经常使用的策略有 对应策略:将问题a对应另一个便于思考或有求解方法的问题b,化繁为简,变未知为已知。 分治策略:将问题的规模逐渐减少,可明显降低解决问题复杂程度。算法设计的这种策略称之为分治策略,即对问题分而治之。 递推的分治策略 递归的分治策略 归纳策略:归纳策略则是通过列举试题本身的特殊情况,经过深入分析,最后概括出事物内在的一般规律,并得到一种高度抽象的解题模型。 递推式 递归式 制定目标 贪心方案,模拟策略:模拟某个过程,通过改变数学模型的各种参数,进而观察变更这些参数所引起过程状态的变化,由此展开算法设计。模拟题没有固定的
10、模式,一般形式有两种: 随机模拟:题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值,将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数,其随机的意义要比实际问题中真实的随机变量稍差一些,因此模拟效果有不确定的因素; 过程模拟:题目不给出概率,要求编程者按照题意设计数学模型的各种参数,观察变更这些参数所引起过程状态的变化,由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性,不含任何不确定因素。由于过程模拟的结果无二义性,因此竞赛大都采用过程模拟。 模拟的解题方法一般有三种类型 直叙式模拟 筛选法模
11、拟 构造法模拟,构造的一般思想方法,1、统计分析法,2、机理分析法,1、统计分析法: 我们在一时得不到事物的特征机理的情况下,通过某种方法测试得到一些数据(即问题的部分解),再利用数理统计知识对数据进行处理,从而得到最终的数学模型,极值问题 m,n 为整数,且满足下列两个条件: m,n 1, 2, 3, ,k (1k109); (n2-mn-m2)2=1。 由键盘输入k,求一组满足上述两个条件的m,n 并且使m2+n2的值最大。,如果我们的猜想正确,那么当(n,m)是方程(n2-mn-m2)2=1的一组解时,根据斐波拉契数列关系,(n+m,n)也一定是方程的一组解。 若(n+m)2-(m+n)
12、n-n2)2=1成立,则 =(n2+(m+n)n-(n+m)2)2=1=(n2+mn+n2-n2-2mn-m2)2=1=(n2-mn-m2)2=1成立 以上各步可逆,所以当(n,m)是方程(n2-mn-m2)2=1的一组解时,(n+m,n)一定是方程的另一组解。,var m,n,next,k :longint; begin write(k= ); readln(k); 读入n和m的上限k if (k1000000000) then halt; 如果k不在要求范围内,就终止 m1; n1; nextm+n; 确定斐波拉契数列的头三项 while next=k do 顺推,求出m,n的最大值 be
13、gin mn; nnext;nextm+n; end;while writeln(m= ,m); writeln(n= ,n); 输出可使m2+n2的值最大的m和n end.main,取石子问题 有两堆石子,数量可能不同。有两个人轮流取。每次有两种不同的取法。一是在任意一堆中取走任意多的石子。二是在两堆中同时取走相同数量的石子。最后把石子全部取完的是胜者。现在给出初始的两堆石子的数目,现在如果轮到你来取,又假设双方都采取最好的策略,问最后你是胜者还是败者。 输入文件只有一行,其中包含两个非负整数a和b,表示两堆石子的数目。(a,b1,000,000,000)。 输出文件也只有一行,包含一个数字
14、。如果最后你是胜者,则输出1。反之,则输出0。 输入示例:6 10 输出示例:0,1、分析失败的情况 测试结果有两种可能 失败的情况:(1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20) (14,23) (16,26) (17,28)(19,31) (21,34)。 胜利的情况:(1,1)(1,3)(1,4)。 胜利的情况比失败的情况多得多。 在上述两种情况中,我们选择相对容易得出的失败情况展开分析,寻找规律; 从1开始的每一个数字,在这些数字对中都会出现一次且仅会出现一次; 数对的差成等差数列1,2,3,4; 有些数对的数字排列来自斐波
15、那契数列 有些数对虽然不是标准斐波那契数列中的数字,但还是符合斐波那契数列的规则; 如果数对(a,b)出现在其中,则(a+b,a+2b)也必然出现在数对中(相反的结论是不对的); 数对中两个数之比都非常接近于=0.618,即著名的黄金分割数。,2 、判别a、b的输赢 由于从1开始的每一个自然数,按照斐波那契数列的规则不重复地出现在失败的数对中,因此,可以得出如下结论: 在失败的数对中如果一个数为x,则取(x*0.618)的小数部分k。 若数对按照递增顺序排列成(a,b),且满足a=,则确定(a,b)失败。由此得出算法: readln(x,y); if xy then begin cy;yx;x
16、c;end; 按照递增顺序排列x和y if x=y div 1.618 若x和y接近黄金分割数,则失败;否则胜利 then writeln(0) else writeln(1);,根据客观事物的特性,分析其内部的机理,弄清关系,在适当抽象的条件下,得到可以描述事物属性的数学工具。 我们在联赛中可以用这种方法建立数学模型,然后根据所对应的算法求出解。如下图所示:,国际象棋(knight) 国际象棋是我们休息娱乐时所常玩的游戏。在各个棋子中,马的行进方式最为特殊,也为人们所津津乐道。我们都知道:马走的是“日”字,也就是说每次都是向水平或竖直方向移动1格,而向另一个方向移动2格,所以也可称作是1*2
17、的马(走法如下图所示)。在图中我们看到一个马由8种跳的方向。 小明是一个数学爱好者,他将马的走法重新定义了一下,重新定义后的广义马成为n*m的马。为了研究广义马,小明让马从(0,0)出发,随意的在一张足够大的棋盘上跳。他发现,有时候广义马总是无法跳入某些格子中,比如从2*2的马永远不可能跳到(1,1),这令他非常感兴趣。他希望知道对于给定的n,m,n*m的广义马是否能够跳到所有的格子。由于n,m可以非常大,这令小明花了许多功夫在尝试上,但仍不能得出肯定的结论。于是他就来找你这个计算机专家了帮忙。 【输入】 在输入文件knIGHT.In中包含了多组测试数据,每个测试数据占一行。 每组测试数据由2
18、个数n,m(1n,m108)组成,表示广义马的类型。文件最后一行由2个0表示文件结束。 【输出】 将答案输出到文件knIGHT.OUT中,每组测试数据占一行。如果马能跳到指定的位置输出YES,否则输出ImPOSSIbLE。,当n为奇数时,将棋盘染色成黑白相间。自(0,0)出发的马始终在白格子上跳跃,黑色的格子是马永远到不了的。,当n为偶数时,我们有这样的移动方案(如上图(b)所示),使得马从(0,0)开始经过一系列的跳步后,到(1,0)的位置,也就是说可是让马到达相邻的格子,所以马可以遍历整个棋盘。,从最简单的1*n的广义马开始分析,将n*m的广义马对应1*n的广义马 第1种情况:若n,m有最
19、大公约数p(p1),则马只能跳到形似(p*s,p*t)的格子上,其他的格子都到达到不了。 第2种情况:若n+m是偶数,类似于1*n马的情况,马只能在同色的格子内跳动,不能遍历棋盘。 第3种情况:若n+m为奇数且n,m互质。不妨设n为奇数,那么m为偶数。因为1*n马的问题已经被彻底解决,所以很自然的想将n*m经过一系列变换转化成1*n马的问题。我们可以看到马的跳法本质上是4种(另4种可以看成是以下4种跳法反跳一步): (m,n) (m,-n) (n,m) (n,-m) 马经过跳p次、q次、r次、s次后 水平方向的位移为(p+q)*m+(r+s)*n 竖直方向的位移为(p-q)*n+(r-s)*m
20、 为了利用1*n马的结论,解不定方程(p+q)*m+(r+s)*n=1。 n,m互质。该方程一定有解(p0,q0,r0,s0)。 又m是偶数n是奇数。(p0+q0)是偶数,(r0+s0)是奇数。 (p0+q0)与(p0-q0)同奇偶,而(r0+s0)与(r0-s0)同奇偶。 (p0-q0)是偶数,(r0-s0)是奇数。 (p0-q0)*n+(r0-s0)*m是偶数。 也就是马通过一系列的跳动所得到的效果相当于1*len的马跳一步的效果(len=(p0-q0)*n+(r0-s0)*m)。根据前面的结论,1*len的马可以遍历整个棋盘,所以当n+m为奇数且n,m互质时,n*m的马可以遍历整个棋盘。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上海市 中学 建德
链接地址:https://www.31doc.com/p-2632850.html