程序设计算法与分析

《程序设计算法与分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计算法分析信息学奥林匹克竞赛联赛知识辅导上册肖兆青前言上世纪人类科学技术的最伟大成果非计算机莫属。自从二十世纪中叶，第一台计算机问世以来，立即引起了当代科学、技术、生产、生活和教育事业等各方面的革命。半个多世纪以来，计算机技术得到了迅猛的发展，其势可谓日新月异，她应用的领域也越见广阔，几乎没有计算机不能涉及的方面。面对这一场巨大的技术革命，计算机知识的教育已成了从小学、中学到大学的一门必不可少的课程。邓小平同志早就指示，计算机教育要从娃娃抓起，所以作为基础教育的中学，如何在普及计算机知识和技能的

2、教学活动中，探索出一条在现代教育理论的指导下提高现代信息科技知识教学质量之路，是很值得我们研究的。为了普及计算机知识，丰富学生课余生活，培养学生的创新思维能力，特别是对学有专长的资优学生进行个性化培养，我国每年都举办一次全国青少年信息学奥林匹克竞赛分区联赛，为全国青少年信息学奥林匹克竞赛、国际青少年信息学奥林匹克竞赛中国队组队赛、国际青少年信息学奥林匹克竞赛选拔人才。从内容上看，这些颇具影响力和权威性的竞赛都是以程序设计为主的。有人问，计算机技术是多方面的，为什么不选基础教育课程内的文字处理、多媒体应

3、用和网络知识，而偏偏选中程序设计呢？这是因为：1.程序设计与软件工具的使用不同，它要求编程者以某种高级语言为媒介，通过构造算法去解决由现实生活中抽象出来的各种问题，这些问题非一般软件工具所能解决。如果说计算机应用是“人脑延伸”的话，程序设计即为这种延伸的最高形式；2.程序设计对人的能力要求是多方面的。编程者不仅要熟悉计算机语言功能，而且还必须具备：（1）扎实的数学基础和算法知识，能够对客观存在的事物及其所要解决的问题具有正确的认识和深刻的理解，包括弄清问题的需求，弄清事物的属性、行为及其彼此之间的关系

4、；（2）娴熟的编程技术，能够把对问题及其方法的认识描述出来，最终产生一个计算机能够理解和执行的计算机程序代码，并通过上机运行让计算机系统实现编程者解决问题的描述；（3）较高的实践能力和创造能力，能够独立思考、提出质疑、拓延思路、洞悉规律，创造性地运用知识于不同的问题情景；正因为程序设计能比较客观地反映人的综合素质，因此国际、国内的信息学奥林匹克竞赛都将其作为考核内容。过去是这样，现在是这样，将来恐怕亦不会随计算机技术的发展而发生改变。计算机程序设计技术将会愈来愈成为现代学生投身信息化环境，从根本上掌握

5、现代信息技术，将来1能自由驾驭信息化时代的重要基础。计算机程序设计人才的培养，其意义不仅在收获人才，更重要的是凸现了青少年人才的培养规律，为各个领域的人才辈出提供了重要的启示。由于程序设计的算法知识具有一定的难度要求，所以对于一些学有余力的资优学生将更具有挑战性，学习程序设计的算法知识是培养资优学生的自主学习能力和创造性思维能力的绝好平台。由于算法知识的益智性和数学味对培养资优学生的推理归纳能力、发散思维能力、构造创新能力具有事半功倍的效果，事实证明，凡是在程序设计的算法知识学习中能够自由翱翔的资优学

6、生，他在学习其它相关领域的知识时也会感到非常的得心应手。在对学生进行程序设计知识训练的过程中有一条非常重要，就是我们特别要注意培养学生通过自学取得独立获取知识和运用知识的能力。比如数据结构和算法的知识对学生们进一步提高程序设计能力非常关键，但由于知识的难度高、内容多，学生的水平差距可能会拉开很大，而我们的课时有可能很有限，靠教师教根本教不过来。所以我感到教师的作用更多的应该是放在精选知识点和例题上，给学生铺出一条仅用一块块不连续的大石块点缀的通路来，而这条道路的夯实和拓宽很多必须通过学生自学来解决。特

7、别是现在计算机的知识更新很快，新的方法、新的技术层出不穷，要适应日新月异的信息时代的要求，学生掌握独立获取知识和运用知识的能力才是今后人生中能胜任终身学习的任务所必不可少的。要培养专长就必须打破课堂教学和现有知识结构的限制，因材施教，鼓励冒尖，为资优学生们减负松绑，提供最佳的学习环境。不能要求一刀切，必要的时候要针对个别特殊情况开小灶，为资优学生们在扎实基础上的特长发挥创造条件。课堂教学最大的弊端是讲求整齐划一，它在一定程度上抑制了学生特长的发挥。从计算机程序设计知识的学习看青少年人才培养规律，启示很

8、多。但最重要的问题还是教育观念的改变。本人在进行了数年的《资优学生培养模式研究》课题的实践中，写下了这本关于信息学奥林匹克竞赛分区联赛中需要用到的一些程序设计算法知识的讲义，现在整理出来，抛砖引玉，供同行们批评指导。2第一讲深度优先搜索搜索是计算机程序设计竞赛中最常用的一种策略，对于那些一时难以找到规律或公式，或者根本没有规律或公式可循的问题，我们可以利用计算机高速运算的特点，用穷举策略来进行搜索。所谓穷举策略，原则地说，就是第一步只考虑问题的部分条件，