信息学奥赛问题求解选讲.

《信息学奥赛问题求解选讲.》由会员分享，可在线阅读，更多相关《信息学奥赛问题求解选讲.（54页珍藏版）》请在金锄头文库上搜索。

1、问题求解选讲 江凡 August 10, 2016,江凡,问题求解选讲,August 10, 2016,归纳推理 Contents,归纳推理 归纳 逻辑推理 初等数论 递推递归 数据结构 其他,江凡,问题求解选讲,August 10, 2016,1 2 3 4 5,归纳推理,归纳,例1，根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。 例如： 13 1 23 3 5 33 7 9 11 43= 13+15+17+19 在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式。,江凡,问题求解选讲,August 10, 2016

2、,X=N2-N+1,归纳推理,归纳,例2，将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为 。,江凡,问题求解选讲,August 10, 2016,362880,归纳推理,江凡,问题求解选讲,August 10, 2016,n=5时，方案有

3、12344!,n=10时，方案有 1299!,n=2时，方案有1种。 n=3时，方案有2种。 n=4时，方案有6种。,归纳,逻辑推理 通常把只涉及一些相互关联（或依存）条件或关系，极少给出（不直接赋与）数量关系与几何图形的一类非标准（常规）数学问题叫逻辑推理问题，处理这类问题，要从一些关联的条件出发，应用某些数学知识，甚至日常生活常识，依据一定的思维规律（机智灵活、准确敏捷的思考），通过分析、推理、排除不可能情况（剔除不合理成分），然后作出正确的判断。 逻辑推理问题中常用到以下三条逻辑基本规律： （1）同一律：是指同一东西（对象）。它是什么就是什么，不能模棱两可，亦此亦彼； （2）矛盾律：是指

4、互相对立（矛盾）的事不能都真，二者必有一假（即同一思想不能既真又假）； （3）排中律：是指两个不相容的判断不能都假，二者必有一真（即任何判断或同一思想不能既不真也不假）。,归纳推理,逻辑推理,江凡,问题求解选讲,August 10, 2016,归纳推理,逻辑推理,利用表格辅助推理: 例3，某中学推理社招新题，答案是 _ 这道题的答案是 AA B B C C D D 第5题的答案是 AC B D C A D B 以下选项中哪一题的答案与其他三项不同 A第3题 B 第6题 C 第2题 D 第4题 以下选项中哪两题的答案相同 A第1，5题 B 第2，7题 C 第1，9题 D 第6，10题 以下选项中

5、哪一题的答案与本题相同 A第8题 B 第4题 C 第9题 D 第7题 以下选项中哪两题的答案与第8题相同 A第2，4题 B 第1，6题 C 第3，10题 D 第5，9题 在此十道题中，被选择次数最少的选项字母为 AC B B C A D D 以下选项中哪一题的答案与第1题的答案在字母表中的不相邻 A第7题 B 第5题 C 第2题 D 第10题 已知“第1题与第6题的答案相同”与“第X题与第5题的答案相同”的真假性相反，那么X为 A第6题 B 第10题 C 第2题 D 第9题 在此十道题中，ABCD四个字母中出现的次数最多者与最少者的差为 A3 B 2 C 4 D 1,江凡,问题求解选讲,Aug

6、ust 10, 2016,BCACACDABA,归纳推理,逻辑推理,利用图形辅助推理 美国数学家斯蒂恩说过:“如果一个特定的问题可以被转化成一个图形,那么,思想就整体地把握了问题,并且能创造性地思索问题解法。” 例4，A、B、C、D、E五支球队进行单循环比赛（每两支球队间都要进行一场比赛），当比赛进行到一定阶段时，统计A、B、C、D四个球队已经赛过的场数，依次为A队4场，B队3场，C队2场，D队1场，这时，E队已赛过的场数是（ ） A. 1 B. 2 C. 3 D. 4,江凡,问题求解选讲,August 10, 2016,B,数论基础 Contents,归纳推理 数论基础 同余 素数 排列组合

7、 递推递归 数据结构 其他,江凡,问题求解选讲,August 10, 2016,1 2 3 4 5,数论基础,同余,如果,a1 a2, b1 b2,(mod m) (mod m),那么,b1,a1 a2, b2 b1 b2,(mod m) (mod m),江凡,问题求解选讲,August 10, 2016,a1a2,同余的定义与性质 如果 m 整除 a b，我们就说 a 与 b 模 m 同余并记为,a, b,(mod m),简单来说，就是它们模 m 后的余数相同就可以记成这样。,数论基础,同余,江凡,问题求解选讲,August 10, 2016,（a1 a2）mod b (a1 mod b)(

8、 a2 mod b) mod b,分治思想与快速幂方法 例5，输入b，p，k的值，求 bp mod k 的值。如，59 mod 7 = ？,59 = 【（5 5） （5 5）】 【（5 5） （5 5）】 5, x a1, x a2,数论基础,同余方程与中国剩余定理,中国剩余定理 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 孙子算经 这个问题说的是：有一个整数，被 3 除余 2，被 5 除余 3，被 7 除余 2，问这个 整数是多少？ 事实上，这个问题有无穷多个解，其中一个解是 23。 中国剩余定理，又称为孙子定理，常常简写成 CRT（Chinese Remainder

9、 Theorem）。它给出了构造如下方程组解的方法：, ,(mod m1 ) (mod m2 ),.,x, an,(mod mn ),其中 m1 , m2 , . . . , mn 两两互素。,江凡,问题求解选讲,August 10, 2016,同余方程与中国剩余定理,数论基础 中国剩余定理 首先来解只有两个方程的方程组。,x x, a1 a2,(mod m1 ) (mod m2 ),我们可以把这个方程组改写成,x x,= a1 + k1 m1 = a2 + k2 m2,消去 x 之后就可以得到 a1 + k1 m1 = a2 + k2 m2 ，这刚好是关于 k1 , k2 的一个 线性方程。

10、 此外，中国剩余定理还告诉我们一个事实，在 m1 , m2 互素的条件下，假设 x0是该方程组的一个解，那么该方程组的所有解都满足如下形式：,江凡,问题求解选讲,August 10, 2016,x, x0,(mod m1 m2 ),这样我们相当于把刚刚的两个方程合并成为了一个方程。如果有多个方程，可以 不断进行这样的合并，最后就可以解出结果了。,x 2,x 2,数论基础,同余方程与中国剩余定理,中国剩余定理 我们来拿刚刚开头的例子来试着算一算。那个方程组是：,x 3,(mod 3) (mod 5) (mod 7),江凡,问题求解选讲,August 10, 2016,首先来合并前两个方程，联立后

11、得到的线性方程是 2 + 3k1 = 3 + 5k2 ，整理后 可以得到一组解是 k1 = 2, k2 = 1，这样可以得到满足前两个方程的 x 都满足：,x, 8 (mod 15),数论基础,同余方程与中国剩余定理,中国剩余定理 之后可以得到新的方程组：,x x, 8 2,(mod 15) (mod 7),再合并两个方程，联立后得到的线性方程是 8 + 15k1 = 2 + 7k2 ，整理后可以 得到一组解是 k1 = 1, k2 = 3，这样可以得到满足这两个方程的 x 都满足：,x, 23,(mod 105),这便是最后的解了！,江凡,问题求解选讲,August 10, 2016,数论基

12、础,素数及基本知识,江凡,问题求解选讲,August 10, 2016,素数及基本知识 素数是只含有 1 及其本身两个正因子的数，也称为质数。如果还有其它正因子的 话，那么这个数就被称为合数。注意 1 并非素数，亦非合数。 我在这里介绍一个关于素数的定理，它们在算法复杂度分析中或许会用到： Theorem (素数定理) 当 x 很大时，小于 x 的素数个数近似等于x/lnx,数论基础,江凡,问题求解选讲,August 10, 2016,素数的判定 如何判定一个数 m 是不是素数，我们可以直接从定义出发，从 2 开始到m-1 为止，检测是否有一个数整除 m，如果没有，那么这个数就是素数。 例6，

13、求105内的所有素数。,Eratosthenes 筛法是一种用来求素数的方法，它的思路比较简单。 由于每个合数都可以被分解成几个素数的乘积，如果我们将所有素数的倍数都删去，那么剩下的就是素数了。 因此，我们可以从 2 开始，先将 2 的所有倍数都删去。然后往下找到第一个没有被删去的数，这个数一定是素数，再将这个数的所有倍数都删去，不断进行这个操作。,素数及基本知识,线性筛法，又称欧拉筛法。 避免冗余的运算。每个合数必有一个最大因子（不包括它本身） ，用这个因子把合数筛掉。 对于每一个数i，乘上小于等于i的最小素因数的素数，就得到以i为最大因数的合数。设有一个数t，只要将所有以比t小的数为最大因

14、数的合数筛去，那么比t小的数里剩下的就只有素数了。,组合数学基础,排列组合,组合数学基础 例7，在1与106之间，有多少个整数的各位数字之和等于9？,江凡,问题求解选讲,August 10, 2016,组合数学基础,排列组合,排列 现在来考虑一个问题：你需要在 n 个不同的人里面选出 m 个人排成一行，问有 多少种排列方案？ n(n 1)(n 2) (n m + 1) 这个数通常被成为排列，记成 ，或者 。 如果我们定义一种名为阶乘的运算：,n!,= 1 2 3 n,特别地，当 n = 0 时，0! = 1。 那么这个数就可以简单地写成：,=,n! (n m)!,江凡,问题求解选讲,Augus

15、t 10, 2016,组合数学基础,排列组合,排列 圆排列 （1）由 的个元素中，每次取出r个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）。 （2）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列。 （3）定理：在的个元素中，每次取出个不同的元素进行圆排列，圆排列数为 。 不尽相异元素的全排列 如果n个元素中，有p1个元素相同，又有p2个元素相同，又有ps个元素相同（ ），这个n元素全部取的排列叫做不尽相异的n个元素的全排列，它的排列数是 。,江凡,问题求解选讲,August 10, 2016,组合数学基础,排列组合,组合 研究无次序的选取问题。把前述排列问题改成：你只需要在 n 个不同的人里面选出 m 个人，问有多少种方案？ 如果我们选出来 m 个人后，再将他们排成一队，那么方案数就是先前的排列数 。 但是这样的计数会出现很多的重复，也就是每次我们都多算了将 m 个人排成一队的方