当前位置:首页 > 教材 > 竞赛奥赛 > 信息学奥林匹克教程·提高篇
出版社:湖南师范大学出版社
出版日期:2003-1
ISBN:9787810810678
作者:吴耀斌
页数:360页
作者简介
《信息学奥林匹克教程》(提高篇)既有各个算法设计基本思路的讲解及对求解问题的分析,注重了算法引导分析与不同算法的比较,又给出了具体的编程思路与参考程序,程序采用信息学竞赛流行的Turbo Pascal7.0语言编写,并注重结构化与可读性。
书籍目录
1 基本算法设计策略 1.1 枚举策略 1.2 归纳策略 1.3 递推策略 1.4 递归算法策略 1.5 分治策略 1.6 贪心策略 1.7 模拟方法2 深度优先和广度优先 2.1 产生式系统 2.2 深度优先搜索 2.3 广度优先搜索 2.4 深度优先和广度优先搜索的深入讨论 2.5 深度优先搜索中的剪枝优化方法 2.6 广度优先搜索的优化方法 2.7 搜索对象与策略的选取3 图论算法 3.1 最小生成树 3.2 最短路径的算法 3.3 拓扑排序算法 3.4 关键路径的算法 3.5 网络流算法 3.6 图论模型的构造4 动态规划 4.1 动态规划的基本模型 4.2 动态规划的设计与实现 4.3 动态规划的深入思考 4.4 动态规划与其他算法的比较5 排序 5.1 简单排序算法 5.2 快速排序 5.3 堆排序 5.4 线性时间排序 5.5 排序的应用6 模型构建与综合算法设计 6.1 模型的建立 6.2 构造法解题和综合算法设计7 Linux操作系统与编程环境 7.1 Linux操作系统 7.2 Gcc编程环境 7.3 Free ntseal编程环境 7.4 模拟试题
编辑推荐
《信息学奥林匹克教程》(提高篇)是作者几年来成功培养学生参加国际、国内信息学奥林匹克竞赛并获奖的经验总结。
内容概要
吴耀斌
中南大学计算机科学与技术专业副教授。编著《信息学奥林匹克教程》《信息学(计算机)奥林匹克Turbo C++2.0》等教材20本,已发表论文30余篇,多次获得省部级科技进步和教学成果奖。现任国家信息学奥林匹克联赛湖南省特派员、国家信息学奥林匹克竞赛湖南省领队、湖南省信息学奥林匹克竞赛组织委员会副主任兼秘书长。
章节摘录
1 基本算法设计策略 在信息学奥林匹克竞赛中,其主要任务是设计一个有效的算法,去求解所给出的问题。实际问题的算法设计方法总是建立在各种基本算法设计策略的基础上,本章将围绕设计算法时常用的一些基本算法设计策略来展开讨论,如枚举、归纳、递推和递归、分治、数学方法等。在介绍每一种基本算法设计策略时,给出了算法效率的分析和应用的实例。读者通过本章的学习,应该掌握基本的算法设计策略以及如何在竞赛中运用这些策略找到解决问题的具体思考方法。 1.1 枚举策略 1.1.1适合枚举策略的问题 枚举法,常常称之为穷举法,是指在一个有穷的可能的解的集合中,枚举出集合中的每一个元素,用问题给定的解的检验条件去判断其是否符合条件,若满足条件,该元素即为问题的一个解,若不满足,该元素就不是这一问题的解。 枚举的思想往往是最容易想到的一种解题策略,枚举方法从本质上说,它是一种搜索算法,即对问题的所有可能解的状态集合进行一次扫描或遍历。因此,适合枚举策略求解的问题,首先必须满足其问题规模和可能解的规模(个数)不是特别大,且解变量的值的变化具有一定的规律性,在具体的程序实现过程中,可以通过循环和条件判断语句来完成。
图书封面