树结构在程序设计中的运用.ppt

《树结构在程序设计中的运用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树结构在程序设计中的运用上海市控江中学　王建德浙江省２００4年NOI组队赛目录引言树结构在程序设计中的运用2003年竞赛的知识结构分布竞赛试题算法NOIP乒乓球数据统计NOIP数字游戏动态程序设计NOIP栈回溯法或组合数学的Catalan数NOIP麦森数高精度运算NOIP神经网络图的递归运算NOIP侦探推理回溯法NOIP加分二叉树递归的动态程序设计NOIP传染病扩展回溯法竞赛试题算法IOI可视边界线段树IOI代码转换程序语句在满足加法交换率和变量名改换情况下的匹配IOI猜牛游戏贪心或类博弈树算法IOI路径维护在无向图的生成过程过程中计算最小生

2、成树IOI逆向输出开放性试题IOI机器人宽度优先搜索2003年竞赛的知识结构分布竞赛试题算法NOI木棒游戏枚举搜索NOI文本编辑器数据结构NOI卫星探测二分查找NOI草莓后序遍历NOI数据生成器前序遍历和后序遍历NOI智破连环阵回溯法2003年竞赛的知识结构分布试题特点1、强调基础知识的灵活应用。每一轮竞赛都有基础知识题，但对灵活应用基础知识的要求愈来愈高。例如IOI的《路径维护》在逐边添入无向图的过程中计算最小生成树；《文本编辑器》要求设计多样的数据结构。例如线性表、非线性的树和图；NOIP的《加分二叉树》采用的动态程序设计是递归形式的；NO

3、I的《数据生成器》必须综合使用前序遍历和后序遍历2、首次出现了线段树和可以选择类博弈树算法的试题3、近似算法类的试题增加。例如IOI的《猜牛游戏》、《逆向输出》、《机器人》、NOI的《卫星探测》、《草莓》、《智破连环阵》等。由于这些例题视程序逼近最优解和最优效率的程度给分，因此拓展了选手思维的空间，易启发选手的创造性。但反过来说，由于近似算法类的选题空间比较大，因此有可能使得题目的难度加大。试题特点4、树形结构类的问题增多。例如NOI的《卫星探测》通过二分查找构造一棵隐形的二叉树；《草莓》和《数据生成器》使用了人们容易被忽视的后序遍历；IOI的

4、《路径维护》要求计算最小生成树；5、可“一题多解”和开放性的试题增多。例如，IOI的《逆向输出》就是一道没有固定模式和经典算法可套用、需要量身定制合适算法的试题；《猜牛游戏》既可以采用贪心法，亦可以采用类博弈树的算法；NOIP的《栈》既可以通过回溯法计算，亦可以通过组合数学的Catalan数计算；6、出现一些“陷阱题”。例如NOIP的《传染病扩展》极易诱导选手错误地使用贪心法或动态程序设计，实际上该问题不具备最优子结构的特征，正确的算法是回溯搜索。启示培养内省智力充分利用网络资源以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创

5、新为目的组织集训培养内省智力入门自信心提高自省力自信心和自知之明是对立的统一。自信心倘若不是建立在自知之明的基础上，则会变成一种无知的自负，不可能取得持续的成功。科学精神的核心是怀疑和批评。这种态度既对他人又对自己，“知人者智，自知者明”，“知常曰明”不能用看书取代上机实践，经常要想“自己怎样面对这个问题的挑战；如果由自己当场独立解题的话，会得到怎样的结果”。“纸上得来终觉浅，绝知此事要躬行”。看懂了不稀奇，会做有灵气，能讲清原理、提出质疑、拓延思路、探索新知才算了不起在挑选练习题时，既不要因为轻视而放弃基础题；也不要因为畏难而放弃大题难题。充

6、分利用网络上与信息学活动相关的信息资源1、由于网络上大量的算法知识和试题的出现，使得学生学习的大部分时间和空间由课堂转移到网上学习，自主性显著提高，学习方式发生了根本性的变化2、学习的效率取决于如何在浩如烟海的网上信息中选择适应于竞赛需要和个性发展的东西3、千万不要有“太易了不屑做、太难了不愿做”的主观随意性充分利用网络上与信息学活动相关的信息资源编程解题能力是在长期的上机实践中积累起来的。如果长期的无所事事、无所作为，迟早会落得了“小题做不对、大题难题不会做”的可悲结局应该对试题本身有一个科学的价值判断：“这道题是不是有利于夯实基础，或者这道

7、题是不是引出带规律性的东西，能不能派生出更多类似的问题”，真正从提高自身的算法认知水平和编程能力的高度，来决定练习题的取舍。以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训第一步：界定问题。即明确试题要求我们做什么,解决什么问题，输出怎样的结果第二步：明确出发点，即明确试题的初始状态是什么，给出了哪些求解条件，其中哪些是显性的，哪些是隐性的，必须无一漏失。第三步：寻找怎样做的创意。即要求学生独立思考，尽可能多地收集相关资料，尝试各种组合，调动所有的灵感和思考方式。第四步：集中测试。每人设计三组测试数据,分别从一

8、般情况、边界情况、扩大问题规模三个角度测试程序的正确性、时间效率和空间效率。然后交流测试数据，学生间进行互测。这样做既能测出自己程序的正确程度，又能在