信息学奥林匹克复赛辅导材料汇总.doc

信息学奥林匹克复赛辅导一： 数学分析 在去年竞赛中，数学分析类试题频繁出现，由此可以看出数学和程序设计之间的“孪生关系”：数学中难以用笔和纸推算的问题需要借助计算机解决；而编程者要解决此类问题，需要有坚实的数学功底和灵活的应变能力，能够对运算对象进行组合分析—怎样计算具有某种特性的对象个数，怎样枚举这些对象。信息学竞赛中离散数和有限数一类试题激增，正说明了信息学与数学的依赖关系日益凸现，数学需要反映计算机的计算、检索、记忆、决策的原理和机制，信息学的发展需要现代数学的支撑。两门学科的整合是国际中学理科教育发展的一个大趋势。 §1.1 解方程 使用计算机解方程，与其说是考核选手的编程技术，不如说是考核选手的数学机巧和能力。解题的关键是通过数学分析得出计算公式和公式中变数的取值范围，在此基础上通过顺序查找或分治法枚举变数的可能值，将符合条件的变数代入表达式，即可得出问题的解。这是编程解数学题的一般思路，也是程序设计竞赛与数学竞赛的区别所在 【例题一】反正切函数的应用（全国赛） 反正切函数可展开成无穷级数，有如下公式 (其中) 公式(1) 使用反正切函数计算是一种常用的方法。例如，最简单的计算的方法： 公式(2) 然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式： 公式(3) 通过简单的变换得到： 公式(4) 利用这个公式，令，则，有 使用和的反正切来计算，速度就快多了。 我们将公式(4)写成如下形式 其中、和均为正整数。 我们的问题是：对于每一个给定的（），求＋的值。我们保证对于任意的a都存在整数解。如果有多个解，要求你给出+最小的解。 输入文件（arctan.in） 输入文件中只有一个正整数，其中。 输出文件（arctan.out） 输出文件中只有一个整数，为+的值。 输入样例 1 输出样例 5 【例题二】一元三次方程求解（分区联赛） 有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d 均为实数），并约定该方程存在三个不同实根（根的范围在—100至100之间），且根与根之差的绝对值≥1。 要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。 提示：记方程f（x）=0，若存在2个数x1和x2，且x1x2，f（x1）*f（x2）＜0，则在（x1，x2）之间一定有一个根。 【样例】 输入： 1 -5 -4 20 输出： -2.00 2.00 5.00 §1.2逻辑推理 将运算对象定义为逻辑变量，按照题意要求和对象间的关系进行布尔运算，推理问题的解。这里提醒大家的是注意理解题意。解题过程是一个不断发掘已知条件、向目标靠拢的过程，因此不能视题目的文字描述为鸡肋，不屑一顾。有时候文字描述中蕴藏了丰富的信息，对解题起到了决定性的作用。只有在全面正确的理解题意的基础上，才能准确定义对象间的关系，通过布尔运算进行合乎逻辑的推理。 【例题三】聪明的学生（组队赛） 一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，B和C。有一天,教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。 这时，教授先对学生A发问了：“你能猜出自己的数吗？”A回答：“不能。” 教授又转身问学生B：“你能猜出自己的数吗？”B想了想，也回答：“不能。” 教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能”。 接着，教授又重新问A同样的问题，再问B和C，……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。 现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M，你能推断出另外两个学生的头上贴的是什么数吗？ 提示：在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在A，B，C之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。 教授总是从学生A开始提问的。 你可以假定，这三个足够聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。 稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。 输入： 输入文件为guess.in。 该文件包括若干组测试数据，其中的每一行代表一组测试数据，由两个整数N和M组成（即在教授第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后，由-1 -1组成的一行标志着输入数据的结束。 0N500； 0M3000