算法与程序设计.doc

算法与程序设计Algorithm and Program Design【课程性质】专业必修课【课程学分】2学分。【教学目标】这是为教育硕士开设的一门专业课程，其主要目标旨在使学生进一步体验算法思想，了解算法和程序设计在解决问题过程中的地位和作用；能从简单问题出发，设计解决问题的算法，并能初步使用一种程序设计语言编制程序，实现算法解决问题，能够胜任中小学计算机竞赛的培训。具体的教学目标包括：1.知识与技能（1）理解算法、程序、语言等内涵及其相互关系。（2）了解顺序、选择、循环三种基本结构及其重要作用。（3）掌握计算机程序的基本概念，能解释计算机程序执行的基本过程。（4）了解程序设计语言、编辑程序、编译程序、连接程序以及程序开发环境等基本知识。（5）了解面向对象与软件工程的基本思想。2.过程与方法（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。（2）掌握用自然语言、流程图或伪代码等方法描述算法的过程。（3）通过观看演示、模仿、探究、实践等活动，在使用计算机解决实际问题的过程中，分析其特点，了解人与计算机解决问题的异同。3.情感态度与价值观（1）培养对算法与程序设计的兴趣。（2）感受计算机解决问题的优势。（3）逐步养成运用计算机分析问题、解决问题的习惯。【教学方式】采用网络授课和假期集中授课相结合的方式。由学生在网络平台进行自我学习，PPT按教学内容制作，便于同学形象理解。教学视频由老师录制，与上课同步，使网络授课的学生也能得到在课堂上的效果。以上资源在网上共享，便于同学下载学习。程序设计例题以online judge上的题目为主，阅读文献以国家集训队论文为主。【考核方式】本课程采用多种考核评价方式，包括自我评价、同伴评价、教师评定。侧重于对学生的过程评价。课程一共分为10个专题，每个专题一个算法，每个算法除了理论知识外，还有相应的实例。并且每个专题都留有相应的练习题，需要学生在课后之余训练，而且都是通过在线评判系统提交。在线评判系统及时反馈评测结果，这样达到学生进行自我评价。每个专题的练习结果都将作为最终评价的一部分，这样可以更好地突出学生整个的学习状况和程度。在寒暑期集中学习阶段，结合分组讨论，进行同伴评价。最终的评价将由主讲老师结合这3个方面给出每个学生的成绩。【学习建议】算法与程序设计是一门实践性非常强的课程，因此要求学习者多动手，多上机，为此我们给出以下学习建议：（1）算法与数据结构相辅相成，密不可分程序设计不仅仅需要算法，还需要相应的数据结构来支撑。因此要想学好程序设计，除了要学会和掌握相应的算法，还需要掌握数据结构的内容。因此建议学习者在学习算法与程序设计课程之前，复习已经学过的数据结构的内容，重点掌握像线性表、堆栈、队列、串、树、图等常见的数据结构。（2）算法的描述方法、算法的设计、算法的分析优化，是学习和掌握各种算法的基础建议学习者在学习这门课程之前学习有关算法设计和分析方面的理论知识。（3）在“做中学”和“学中做”调查表明,我们所掌握的知识，有10是通过“阅读”得来的，有15是“听”来的，有80是亲身经历获得来的。对于算法和程序设计来说，众多的算法是前辈们通过各种途径总结出来的，是非常经典的。要想学会和掌握它们，仅仅通过阅读和背诵是不行的，必须多上机练习，掌握其实际的应用，这样才能达到学以致用。（4）各个专题的重点内容第一专题：信息学竞赛简介与算法基础重点掌握信息学竞赛的整体状况和NOI竞赛的比赛规则、试题类型、知识范畴，以及算法基础知识。第二专题：数制转换与高精度计算重点掌握各种数制及其它们之间转换以及高精度数的各种运算。第三专题：字符串处理重点掌握字符串的比较、查找等处理。第四专题：排序算法重点掌握各种常见排序算法及其使用，如冒泡排序、插入排序、快速排序。第五专题：搜索算法重点掌握二分查找法。第六专题：递归算法重点掌握递归算法的设计，注意递归出口。第七专题：贪心算法重点掌握贪心算法的基本思想以及贪心算法解题的基本要素。第八专题：图论重点掌握图的搜索算法，如深度优先搜索和广度优先搜索。第九专题：动态规划重点掌握动态规划求解时如何寻找“子问题”，如何定义“状态”，如何给出“状态转移方程”。第十专题：模拟重点掌握用计算机模拟解决现实中难以用公式解决的问题。专题一 信息学竞赛简介与算法基础【主要内容】1.信息学奥林匹克相关知识：介绍信息学奥林匹克竞赛的基本常识、比赛规则、题目范围等。2.算法与程序设计的基础：介绍算法的基本常识以及常见的算法介绍等。【学习重点】信息学奥林匹克竞赛的基本常识、算法的基本介绍，包括信息学奥林匹克竞赛的基本常识、比赛规则、题目范围以及算法的基本常识以及常见的算法介绍等。一、信息学竞赛简介（一）信息学竞赛概述信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成了“地级市省（直辖市）全国国际”四级相互接轨的竞赛网络。信息学竞赛系列活动主要包括以下六个方面：（1）各省市组织的与NOI有关的培训和竞赛活动；（2）全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，简称NOIP）；（3）全国青少年信息学奥林匹克竞赛（National Olympiad in Informatics，简称NOI），同时举行夏令营和全国青少年信息学奥林匹克团体对抗赛；（4）全国青少年信息学奥林匹克竞赛冬令营；（5）亚洲和太平洋地区信息学奥林匹克竞赛（Asia and Pacific Informatics Olympiad，简称APIO）；（6）国际信息学奥林匹克中国队选拔赛，全国信息学奥林匹克精英赛，参加国际信息学奥林匹克（International Olympiad in Informatics，简称IOI）。其大致顺序为：先举办全国信息学（计算机）奥林匹克分区联赛（NOIP），联赛分高中组，初中组进行，以普及为主。在分区联赛的基础上，各省市组成自己的代表队，参加第二个层次的比赛，即全国青少年信息学奥林匹克竞赛（NOI）。第三个层次是从NOI中选拔优秀选手（20人），经过培训，考试选拔，组成国家队（一般4-5人），参加国际信息学奥林匹克竞赛，即IOI，这是国际性的最高水平的竞赛。（二）各类比赛简介1全国青少年信息学奥林匹克竞赛（NOI）1984年邓小平指出：“计算机的普及要从娃娃做起。”教育部和中国科协委托中国计算机学会（CCF）举办了全国青少年计算机程序设计竞赛。从此每年举办一次全国青少年计算机程序设计竞赛。该竞赛是经国家教委批准，中国科协具体领导，由中国计算机学会主办的，是国内包括港澳在内的省级代表队最高水平的大赛。由各省市组织参赛，经各省NOIP选拔产生5名选手（其中一名是女选手），每年由中国计算机学会在计算机普及较好的城市举办一次比赛。奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队。而自从1989年我国参加第一届国际信息学奥林匹克（简称IOI）以来，全国青少年计算机程序设计竞赛也更名为全国青少年信息学（计算机）奥林匹克（NOI）。NOI期间，举办同步夏令营和NOI网上同步赛，给那些程序设计爱好者和高手提供机会。为增加竞赛的竞争性、对抗性和趣味性以及可视化，NOI组织进行团体对抗赛，团体对抗赛实质上是程序对抗赛，其成绩纳入总分计算。2全国青少年信息学奥林匹克竞赛冬令营全国青少年信息学奥林匹克竞赛冬令营（简称冬令营）自1995年起。每年在寒假期间开展为期8天的培训活动。冬令营包括授课、 讲座、讨论、测试等。参加冬令营的营员分正式营员和非正式营员。获得NOI前20名的选手和指导教师为正式营员，非正式营员限量自愿报名参加。在冬令营授课的是著名大学的资深教授及已获得国际金牌学生的指导教师。IOI的选手是从获NOI前20名选手中选拔出来的，获得前4名的优胜者代表中国参加国际竞赛。选拔科目包括：NOI成绩、冬令营成绩、论文和答辩、平时作业、选拔赛成绩、口试。上述项目加权产生最后成绩。官方网站：/3全国青少年信息学奥林匹克联赛（NOIP）全国青少年信息学奥林匹克联赛（NOIP）是由中国计算机学会主办的以省为赛区单位组织实施的全国性竞赛，是全国青少年信息学奥林匹克竞赛（NOI）系列活动的重要组成部分。在举办1995年NOI活动之前，为了扩大普及面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。4亚洲和太平洋地区信息学奥林匹克竞赛亚洲和太平洋地区信息学奥赛（APIO）于2007年创建，该竞赛为区域性的网上准同步赛，是亚洲和太平洋地区每年一次的国际性赛事，旨在给青少年提供更多的赛事机会，推动亚太地区的信息学奥林匹克的发展。APIO每年5月举行，由不同的国家轮流主办。每个参赛团参赛选手上限为100名，其中成绩排在前6名的选手作为代表该参赛团的正式选手统计成绩。APIO中国赛区由中国计算机学会组织参赛，获奖比例将参照IOI。5国际信息学奥林匹克竞赛1987年，保加利亚的sendov教授在联合国教科文组织（UNESCO）第24次全体会议上提出了举办IOI的倡议。从此IOI成为五项国际学科奥林匹克竞赛之一，是由联合国教科文组织于1988年创建。首届竞赛于1989年5月在保加利亚的布拉维茨举行，有13个国家的46名选手参赛。我国只有信息学是首届就获得参赛资格的，而且首届竞赛的试题原型是由中国提供的。IOI的宗旨是：宣传信息学这一新兴学科；激发学生对计算机科学和信息技术的兴趣；给学校这一类课程增加动力和新思路；通过竞赛形式对有才华的青少年给予激励，促使其能力得以发展；特别是使世界各国有才华的中学生汇聚一堂，进行科学文化上的交流，并学习主办国优秀的文化。中国参赛队由中国计算机学会组织，代表中国参加国际每年一次的IOI。中国是IOI创始国之一。出国参赛得到中国科协和国家自然科学基金委的资助。自1989年开始，我国在NOI（网上同步赛1999年开始）、NOIP、冬令营、选拔赛的基础上，组织参加国际信息学奥林匹克（IOI）竞赛。中国已成为世界公认的信息学奥林匹克竞赛强国。官方网站：/index.shtml二、全国青少年信息学奥林匹克联赛组织指南1竞赛组别：竞赛分普及组和提高组两个组别，各分初赛和复赛两轮进行。2参赛对象：凡初、高中阶段的学生和同等年龄段中等专业学校的在校学生均可以报名参加。3大纲与命题：联赛大纲由主办单位NOI科学委员会制订并颁布。命题采取开放形式，任何有兴趣者均可志愿提供候选赛题。最终竞赛题目由主办单位 NOI科学委员会确定。4组织形式：由主办单位统一大纲、统一命题、统一制卷、统一评分标准、统一竞赛时间、统一评测。5竞赛形式和时间初赛为笔试，主要测试选手有关计算机方面的基本知识，每年10月份的第三个周六下午2:30-4:30在各赛区进行。复赛为上机编程，主要测试选手算法设计编程能力，每年11月份的第三个周六在各赛区进行：提高组于上午8:30-11:30进行，普及组于下午1:30-4:30进行。6参赛报名及参赛资格：参赛的选手到各省组织单位报名，确认后参加。报名工作由各赛区特派员负责实施。报名截止日期：当年的9月20日。初赛：报名参赛的选手填写好报名表。各赛区特派员将按普及组和提高组（分语言）分别统计出报名人数，于当年的9月20日前用电子邮件或网络方式将NOIP试卷数量申请表上报主办单位。复赛：各赛区根据初赛成绩从高到低依次确定参加复赛的选手，不参加初赛的选手不具有参加复赛的资格。参加复赛的人数不高于参加初赛人数的20%。特派员应于初赛后10天内，按普及组和提高组（分语言）统计出参加复赛的选手和人数以及复赛试卷申请数量，用电子邮件或网络方式上报主办单位。三、全国青少年信息学奥林匹克联赛大纲解读（一）竞赛宗旨由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛（NOIP）是全国信息学奥林匹克竞赛（NOI）系列活动中的一个重要组成部分，旨在向中学生普及计算机基础知识，培养计算机科学和工程领域的后备人才。普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些核心内容有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。对学生的能力培养将注重以下的几个方面：想象力与创造力；对问题的理解和分析能力；数学能力和逻辑思维能力；对客观问题和主观思维的口头和书面表达能力；人文精神：包括与人的沟通能力，团队精神与合作能力，恒心和毅力，审美能力等。（二）竞赛形式和成绩评定NOIP分两个等级组：普及组和提高组。每组竞赛分两轮：初试和复试。初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。初试为资格测试，获本省初试成绩在本赛区前15%的学生进入复赛。复试形式为上机编程，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。各省NOIP的等第将在复试的优胜者中产生。比赛中使用的程序设计语言是：初赛：PASCAL或C/C+：复赛：PASCAL或C/C+。每年复赛结束后，各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。经复审和评测后，由中国计算机学会报送中国科协和教育部备案。中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见，各省可按照成绩确定获奖名单。（三）试题形式每次NOIP的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。其中，A1和B1类型基本相同，A2和B2类型基本相同，但题目不完全相同，提高组难度高于普及组。1初赛初赛全部为笔试，满分100分。试题由四部分组成：（1）选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。普及组20个都是单选题。（2）问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。（3）程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。（4）程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。2复赛复赛的题型和考试形式与NOI类似，全部为上机编程题，但难度比NOI低。题目包括4道题，每题100分，共计400分。每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得1020分，累计分即为该道题的得分。特别说明的是：自2011年起，复赛提高组由一试改为两试，分两天进行。每天竞赛试题由原来的4题改为3题。所有进入复赛的提高组选手均参加一试和二试，选手最终成绩由一试与二试成绩算术相加而得。复赛普及组不变：复赛普及组仍为一试，四个题目。四、试题的知识范围（一）NOIP初赛内容与要求1计算机的基本常识（1）计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）；（2）信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）；（3）信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序和存储程序原理、程序的三种基本控制结构）；（4）信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）；（5）信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）；（6）人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）；（7）信息技术的新发展、新特点、新应用等。2计算机的基本操作（1）Windows和LINUX的基本操作知识；（2）互联网的基本使用常识（网上浏览、搜索和查询等）；（3）常用的工具软件使用（文字编辑、电子邮件收发等）。3程序设计的基本知识（1）数据结构 程序语言中基本数据类型（字符、整数、长整、浮点） 浮点运算中的精度和数值比较 一维数组（串）与线性表 记录类型（PASCAL）/ 结构类型（C）（2）程序设计 结构化程序设计的基本概念 阅读理解程序的基本能力 具有将简单问题抽象成适合计算机解决的模型的基本能力 具有针对模型设计简单算法的基本能力 程序流程描述（自然语言/伪码/NS图/其他） 程序设计语言（PASCAL/C/C+）- 2003仍允许BASIC（3）基本算法处理 初等算法（计数、统计、数学运算等） 排序算法（冒泡法、插入排序、合并排序、快速排序） 查找（顺序查找、二分法） 回溯算法（二）NOIP复赛内容与要求在初赛内容的基础上增加以下内容：1数据结构（1）指针类型（2）多维数组（3）单链表及循环链表（4）二叉树（5）文件操作（从文本文件中读入数据，并输出到文本文件中）2程序设计（1）算法的实现能力（2）程序调试基本能力（3）设计测试数据的基本能力（4）程序的时间复杂度和空间复杂度的估计3算法处理（1）离散数学知识的应用（如排列组合、简单图论、数理逻辑）（2）分治思想（3）模拟法（4）贪心法（5）简单搜索算法（深度优先、广度优先），搜索中的剪枝（6）动态规划的思想及基本算法（三）NOI竞赛内容NOI竞赛的题目以考查选手对算法和编程能力的掌握为主。题目类型有以下三种：1非交互式程序题非交互式程序题要求选手提交答案程序的源文件。该程序从一个正文文件中读入数据，并向指定的输出文件中写入计算结果。非交互式程序题的题面包括下列内容：（1）求解问题的描述（2）输入文件名和输出文件名（可以是标准输入/输出）（3）输入数据格式、输出数据格式以及输入数据范围（4）对程序使用计算资源的限制以及其它可能的限制2交互式程序题交互式程序题要求选手提交答案程序的源文件。该程序通过调用所提供的库函数实现数据的输入和输出。交互式程序题的题面包括下列内容：（1）求解问题的描述（2）库函数的功能、函数原型以及获取和链接方式（3）输入数据格式、输出数据格式以及输入数据范围（4）对程序使用计算资源的限制以及其它可能的限制3答案提交题答案提交题不要求选手提交程序的源文件。选手需要按题目要求，根据给定的输入数据文件生成一组输出数据文件。该组数据文件既可以是由选手的程序输出的，也可以是由选手手工构造的。当选手使用自行设计的程序生成题目答案时，其所使用的程序不应提交。答案提交题的题面包括下列内容：（1）求解问题的描述（2）输入数据格式、输出数据格式（3）输入数据文件的获取方法对于交互式程序题和非交互式程序题，对选手程序使用内存大小的限制包括运行代码、程序运行时所需的栈和堆在内的所有工作内存的总和。当题面中没有给出对使用内存的限制时，以选手用机的实际使用限制为准。对选手程序运行时间的限制一般均大于标准答案程序所需最长运行时间的50%以上，以避免测试中的超时判断误差。五、竞赛允许使用的编程语言NOIP：允许使用Basic、Pascal或C语言。在个别赛区的个别年份允许使用C+，不过这只是极个别的情况。因此准备NOIP竞赛的时候最好别考虑C+。推荐使用Pascal，因为当前市场上分区联赛的相关辅导书籍都使用Pascal描述的。不推荐使用Basic，因为NOI中不允许使用这种语言。NOI：允许使用C/C+或Pascal语言。六、算法基础（一）算法概述1算法定义用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。2算法特征一个算法应该具有以下五个方面的重要特征：（1）输入：所谓输入是指从算法在执行时需要从外界取得必要的信息。一个算法有零个或多个输入，以刻画运算对象的初始情况。（2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。（3）有穷性（有限性）：一个算法在执行有限步之后必须结束。也就是说，一个算法，它所包含的计算步骤应是有限的。（4）输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。（5）有效性（可行性）：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。（二）复杂度不同的算法可能用不同的时间、空间或效率来完成同样的任务。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。1时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T（n）。（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T（n）也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n），称O（f（n） 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O（1），另外，在时间频度不相同时，时间复杂度有可能相同，如T（n）=n2+3n+4与T（n）=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O（n2）。按数量级递增排列，常见的时间复杂度有：常数阶O（1），对数阶O（log2n）（以2为底n的对数，下同），线性阶O（n），线性对数阶O（nlog2n），平方阶O（n2），立方阶O（n3），.，k次方阶O（nk），指数阶O（2n）。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。2空间复杂度算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作：S（n）=O（f（n）我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。四、试题的知识范围（一）NOIP初赛内容与要求1计算机的基本常识（1）计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）；（2）信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）；（3）信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序和存储程序原理、程序的三种基本控制结构）；（4）信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）；（5）信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）；（6）人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）；（7）信息技术的新发展、新特点、新应用等。2计算机的基本操作（1）Windows和LINUX的基本操作知识；（2）互联网的基本使用常识（网上浏览、搜索和查询等）；（3）常用的工具软件使用（文字编辑、电子邮件收发等）。3程序设计的基本知识（1）数据结构 程序语言中基本数据类型（字符、整数、长整、浮点） 浮点运算中的精度和数值比较 一维数组（串）与线性表 记录类型（PASCAL）/ 结构类型（C）（2）程序设计 结构化程序设计的基本概念 阅读理解程序的基本能力 具有将简单问题抽象成适合计算机解决的模型的基本能力 具有针对模型设计简单算法的基本能力 程序流程描述（自然语言/伪码/NS图/其他） 程序设计语言（PASCAL/C/C+）- 2003仍允许BASIC（3）基本算法处理 初等算法（计数、统计、数学运算等） 排序算法（冒泡法、插入排序、合并排序、快速排序） 查找（顺序查找、二分法） 回溯算法（二）NOIP复赛内容与要求在初赛内容的基础上增加以下内容：1数据结构（1）指针类型（2）多维数组（3）单链表及循环链表（4）二叉树（5）文件操作（从文本文件中读入数据，并输出到文本文件中）2程序设计（1）算法的实现能力（2）程序调试基本能力（3）设计测试数据的基本能力（4）程序的时间复杂度和空间复杂度的估计3算法处理（1）离散数学知识的应用（如排列组合、简单图论、数理逻辑）（2）分治思想（3）模拟法（4）贪心法（5）简单搜索算法（深度优先、广度优先），搜索中的剪枝（6）动态规划的思想及基本算法（三）NOI竞赛内容NOI竞赛的题目以考查选手对算法和编程能力的掌握为主。题目类型有以下三种：1非交互式程序题非交互式程序题要求选手提交答案程序的源文件。该程序从一个正文文件中读入数据，并向指定的输出文件中写入计算结果。非交互式程序题的题面包括下列内容：（1）求解问题的描述（2）输入文件名和输出文件名（可以是标准输入/输出）（3）输入数据格式、输出数据格式以及输入数据范围（4）对程序使用计算资源的限制以及其它可能的限制2交互式程序题交互式程序题要求选手提交答案程序的源文件。该程序通过调用所提供的库函数实现数据的输入和输出。交互式程序题的题面包括下列内容：（1）求解问题的描述（2）库函数的功能、函数原型以及获取和链接方式（3）输入数据格式、输出数据格式以及输入数据范围（4）对程序使用计算资源的限制以及其它可能的限制3答案提交题答案提交题不要求选手提交程序的源文件。选手需要按题目要求，根据给定的输入数据文件生成一组输出数据文件。该组数据文件既可以是由选手的程序输出的，也可以是由选手手工构造的。当选手使用自行设计的程序生成题目答案时，其所使用的程序不应提交。答案提交题的题面包括下列内容：（1）求解问题的描述（2）输入数据格式、输出数据格式（3）输入数据文件的获取方法对于交互式程序题和非交互式程序题，对选手程序使用内存大小的限制包括运行代码、程序运行时所需的栈和堆在内的所有工作内存的总和。当题面中没有给出对使用内存的限制时，以选手用机的实际使用限制为准。对选手程序运行时间的限制一般均大于标准答案程序所需最长运行时间的50%以上，以避免测试中的超时判断误差。五、竞赛允许使用的编程语言NOIP：允许使用Basic、Pascal或C语言。在个别赛区的个别年份允许使用C+，不过这只是极个别的情况。因此准备NOIP竞赛的时候最好别考虑C+。推荐使用Pascal，因为当前市场上分区联赛的相关辅导书籍都使用Pascal描述的。不推荐使用Basic，因为NOI中不允许使用这种语言。NOI：允许使用C/C+或Pascal语言。六、算法基础（一）算法概述1算法定义用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。2算法特征一个算法应该具有以下五个方面的重要特征：（1）输入：所谓输入是指从算法在执行时需要从外界取得必要的信息。一个算法有零个或多个输入，以刻画运算对象的初始情况。（2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。（3）有穷性（有限性）：一个算法在执行有限步之后必须结束。也就是说，一个算法，它所包含的计算步骤应是有限的。（4）输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。（5）有效性（可行性）：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。（二）复杂度不同的算法可能用不同的时间、空间或效率来完成同样的任务。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。1时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T（n）。（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T（n）也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n），称O（f（n） 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O（1），另外，在时间频度不相同时，时间复杂度有可能相同，如T（n）=n2+3n+4与T（n）=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O（n2）。按数量级递增排列，常见的时间复杂度有：常数阶O（1），对数阶O（log2n）（以2为底n的对数，下同），线性阶O（n），线性对数阶O（nlog2n），平方阶O（n2），立方阶O（n3），.，k次方阶O（nk），指数阶O（2n）。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。2空间复杂度算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作：S（n）=O（f（n）我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。专题二 数制转换与高精度计算【主要内容】1. 数制转换：介绍数制的相关概念以及常见的各种数制及其它们之间的转换。2. 高精度计算：介绍高精度数的各种运算。【学习重点】数制的相关概念、常见的各种数制及其它们之间的转换以及高精度数的各种运算。一、数制转换（一）相关概念1数制数制是人们利用符号进行计数的一种科学方法。数制也称计数制，是用一组固定的符号和统一的规则来表示数值的方法。2进制进制也就是进位制，是人们规定的一种进位方法。对于任何一种进制X进制，就表示某一位置上的数运算时是逢X进一位。 十进制是逢十进一，十六进制是逢十六进一，二进制就是逢二进一。3数码数制中表示基本数值大小的不同数字符号。例如，十进制有10个数码：0、1、2、3、4、5、6、7、8、9。4基数数制所使用数码的个数。例如，二进制的基数为2；十进制的基数为10。5位权位权表示数的符号在不同的位置上时所代表的数的值是不同的。也就是数制中某一位上的1所表示数值的大小（所处位置的价值）。例如，十进制的123，1的位权是100，2的位权是10，3的位权是1。（二）各种常见的进制人们通常采用的进制有十进制、二进制、八进制和十六进制等。1十进制（Decimal）十进制是人们日常生活中最熟悉的进位计数制。在十进制中，数码共有0，1，2，3，4，5，6，7，8，9这十个符号。计数规则是逢十进一。2二进制（Binary）二进制是在计算机系统中采用的进位计数制。二进制数有两个特点：在二进制中，数码有0和1两个符号。计数规则是逢二进一。为区别于其它进制数，二进制数的书写通常在数的右下方注上基数2，或在后面加上B表示。例如：二进制数10110011可以写成（10110011）2，或写成10110011B。3八进制数（Octal）由于二进制数据的基数比较小，所以二进制数据的书写和阅读很不方便，为此，在小型机中引入了八进制。八进制的基数R=8=23，有数码0、1、2、3、4、5、6、7，并且每个数码正好对应三位二进制数，所以八进制能很好地反映二进制。八进制用下标8或数据后面加O表示 例如：二进制数据 （ 11 101 010 . 010 110 100 ）2 ，对应的八进制数据 ( 3 5 2 . 2 6 4 )8或352.264O。4十二进制（Duodecimal）十二进制在生活中也是经常用到的，例如，长度单位一英尺等于12英寸，一先令等于12便士，就连足球比赛罚点球的英制长度也是12码。此外还有一打12个，钟表转一圈12小时等等。一般在十二进制中，10和11可用M和N表示，有时候也可用A和B表示。5十六进制（Hexadecimal）十六进制是人们在计算机指令代码和数据的书写中经常使用的数制。在十六进制中，由十六个字符09以及A，B，C，D，E，F（或a，b，f）组成（它们分别表示十进制数1015）来描述。计数规则是逢十六进一，即基数R=16=24，通常在表示时用尾部标志H或下标16以示区别。例如：十六进制数4AC8可写成（4AC8）16，或写成4AC8H。6六十进位制数（Sexagesimal）古代人由于生产劳动的需要，要研究天文和历法，就牵涉到时间和角度了。因为历法需要的精确度较高，时间的单位小时，角度的单位度都嫌太大。必须进一步研究他们的小数。它们的小数都具有这样的性质：使1/2，1/3，1/4，1/5，1/6等都能成为他的整数倍。以1/60作为单位，就正好具有这个性质。譬如：1/2等于30个1/60，1/3等于20个1/60，1/4等于15个1/60这种小数的进位制在表示有些数时很方便。例如常遇到的1/3，在十进位制中要变成无限小数，但在这种进位制中就是一个整数。因此就出现了六十进制。（三）进制转换在实际运算中，我们经常用到各种不同的进制，这就需要在各种数制之间进行转换。1其他进制转换为十进制（按权求和）方法是：将其它进制按权位展开，然后各项相加，就得到相应的十进制数。例：N=（10110.101）B=（？）D按权展开N=1*24+0*23+1*22+1*21+0*20+1*2-1+0*2-2+1*2-3 =16+4+2+0.5+0.125 =（22.625）D例：(38A.11)16转换为十进制数 (38A.11)16 =3162+8161+10160+116-1+116-2 =768+128+10+0.0625+0.0039 =906.06642十进制转换成其它进制方法是：分两部分进行的，即整数部分和小数部分。（1）整数部分：（基数除法）把我们要转换的数除以新的进制的基数，把余数作为新进制的最低位；把上一次得的商在除以新的进制基数，把余数作为新进制的次低位；继续上一步，直到最后的商为零，这时的余数就是新进制的最高位。（2）小数部分：（基数乘法）把要转换数的小数部分乘以新进制的基数，把得到的整数部分作为新进制小数部分的最高位。把上一步得的小数部分再乘以新进制的基数，把整数部分作为新进制小数部分的次高位；继续上一步，直到小数部分变成零为止。或者达到预定的要求也可以。3二进制与八进制、十六进制的相互转换二进制转换为八进制、十六进制：它们之间满足23和24的关系，因此把要转换的二进制从低位到高位每3位或4位一组，高位不足时在有效位前面添“0”，然后把每组二进制数转换成八进制或十六进制即可。八进制、十六进制转换为二进制时，把上面的过程逆过来即可。例：N=（C1B）H=（？）B（C1B）H=1100/0001/1011=（110000011011）B4数制转换的一般化（1）R进制转换成十进制 任意R进制数据按权展开、相加即可得十进制数据。例如：N = 1101.0101B = 1*23+1*22+0*21+1*20+0*2-1+1*2-2+0*2-3+1*2-4 = 8+4+0+1+0+0.25+0+0.0625 = 13.3125N = 5A.8H = 5*161+A*160+8*16-1 = 80+10+0.5 = 90.5（2）十进制转换R进制十进制数转换成R进制数，须将整数部分和小数部分分别转换。整数转换除R取余法，规则：用R去除给出的十进制数的整数部分，取其余数作为转换后的R 进制数据的整数部分最低位数字；再用R去除所得的商，取其余数作为转换后的R 进制数据的高一位数字；重复执行操作，一直到商为0结束。小数转换乘R取整法，规则：用R去乘给出的十进制数的小数部分，取乘积的整数部分作为转换后R 进制小数点后第一位数字；再用R 去乘上一步乘积的小数部分，然后取新乘积的整数部分作为转换后R 进制小数的低一位数字；重复操作，一直到乘积为0，或已得到要求精度数位为止。解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再把十进制表示转换成所求的数制表示。转换的结果也用一个字符型数组表示，每个元素表示转换结果的一位数字。根据数制表示中相邻位的基数关系，可以把不同的数制分成两类。一类数制表示中，相邻位的基数是等比关系，例如我们熟悉的十进制表示。另一类数制表示中，相邻位的基数是不等比的。例如在时间表示中，从秒到分采用60进进制；从月到年采用12进制。把一个数值从数制B的表示bmbm-1bm-2 . b1 转换成十进制表示dndn-1dn-2 . d1 比较简单。假设数制B中，第i位的基数为basei(1=i=m)，直接把basei与bi 相乘，然后对全部乘积求和。从十进制表示dndn-1dn-2 . d1 到bmbm-1bm-2 . b1 的转换需要分两种情况考虑： l数制B 中相邻数字的基数是等比关系，即：basei(1=i=m)可以表示成Ci-1 ，其中C是一个常量。将dndn-1dn-2 . d1 除以C，余数即为b1；将dndn-1dn-2 . d1 和C 相除的结果再除以C，余数即为b2； ；直至计算出为bm 止。 l数制B 中相邻数字的基数不等比。需要先判断dndn-1dn-2 . d1 在数制B中需要的位数m，然后从高位到低位依次计算bm、bm-1、bm-2、.、b1。（四）数制转换实例1特殊的四位数（201）（来源：POJ 2196 ZOJ 2405）问题描述：找出并输出所有的4位数（十进制数）中具有如下属性的数：四位数字之和等于其十六进制形式各位数字之和，也等于其十二进制形式各位数字之和。例如：十进制数2991，其四位数字之和2+9+9+1 = 21。由于2991 = 1*1728 + 8*144 + 9*12 + 3， 其十二进制形式为1893(12)， 其各位数字之和也为21。但是它的十六进制形式为BAF(16)，其各位数字之和等于11+10+15 = 36。因此你的程序要舍去2991这个数据。下一个数2992，其十进制、十二进制、十六进制形式各位数字之和均为22，因此2992符合要求，应该输出来