当前位置:首页 >> 学科竞赛 >>

信息学奥赛问题求解选讲


问题求解选讲
江凡

August 10, 2016

江凡

问题求解选讲

August 10, 2016

归纳推理

Contents

1

归纳推理 归纳 逻辑推理 初等数论 递推递归 数据结构 其



2

3 4

5

江凡

问题求解选讲

August 10, 2016

归纳推理

归纳

例1,根据Nocomachns定理,任何一个正整数n
的立方一定可以表示成n个连续的奇数的和。 例如: 13= 1 23= 3+ 5 33= 7+ 9 +11 43= 13+15+17+19 在这里,若将每一个式中的最小奇数称为X,那么 当给出n之后,请写出X与n之间的关系表达式。

X=N2-N+1
江凡 问题求解选讲 August 10, 2016

归纳推理

归纳

例2,将边长为n的正三角形每边n等分,过每个 分点分别做另外两边的平行线,得到若干个正三角形, 我们称为小三角形。正三角形的一条通路是一条连续 的折线,起点是最上面的一个小三角形,终点是最下 面一行位于中间的小三角形。在通路中,只允许由一 个小三角形走到另一个与其有公共边的且位于同一行 或下一行的小三角形,并且每个小三角形不能经过两 次或两次以上(图中是n=5时一条通路的例子)。设 n=10,则该正三角形的不同的通路的总数 为 362880 。

江凡

问题求解选讲

August 10, 2016

归纳推理

归纳

n=2时,方案有1种。 n=3时,方案有2种。 n=4时,方案有6种。

n=5时,方案有 1×2×3×4=4! n=10时,方案有 1×2×?×9=9!

江凡

问题求解选讲

August 10, 2016

归纳推理

逻辑推理

逻辑推理
通常把只涉及一些相互关联(或依存)条件或关系,极少给出(不直接

赋与)数量关系与几何图形的一类非标准(常规)数学问题叫逻辑推理问题,
处理这类问题,要从一些关联的条件出发,应用某些数学知识,甚至日常生 活常识,依据一定的思维规律(机智灵活、准确敏捷的思考),通过分析、 推理、排除不可能情况(剔除不合理成分),然后作出正确的判断。

逻辑推理问题中常用到以下三条逻辑基本规律:
(1)同一律:是指同一东西(对象)。它是什么就是什么,不能模棱两可, 亦此亦彼; (2)矛盾律:是指互相对立(矛盾)的事不能都真,二者必有一假(即同

一思想不能既真又假);
(3)排中律:是指两个不相容的判断不能都假,二者必有一真(即任何判 断或同一思想不能既不真也不假)。

江凡

问题求解选讲

August 10, 2016

归纳推理

逻辑推理

利用表格辅助推理:

BCACACDABA 例3,某中学推理社招新题,答案是 _____________

⒈这道题的答案是 A.A B .B C .C D .D ⒉第5题的答案是 A.C 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题 ⒌以下选项中哪一题的答案与本题相同 A.第8题 B .第4题 C .第9题 D .第7题 ⒍以下选项中哪两题的答案与第8题相同 A.第2,4题 B .第1,6题 C .第3,10题 D .第5,9题 ⒎在此十道题中,被选择次数最少的选项字母为 A.C 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四个字母中出现的次数最多者与最少者的差为 A.3 B .2 C .4 D .1
江凡 问题求解选讲 August 10, 2016

归纳推理

逻辑推理

利用图形辅助推理
美国数学家斯蒂恩说过:“如果一个特定的问题可以被转化成一个图形,那么, 思想就整体地把握了问题,并且能创造性地思索问题解法。” 例4,A、B、C、D、E五支球队进行单循环比赛(每两支球队间都要进行 一场比赛),当比赛进行到一定阶段时,统计A、B、C、D四个球队已经赛过 的场数,依次为A队4场,B队3场,C队2场,D队1场,这时,E队已赛过的场 数是( A. 1

B

) B. 2 C. 3 D. 4

江凡

问题求解选讲

August 10, 2016

数论基础

Contents

1 2

归纳推理

数论基础 同余 素数 排列组合 递推递归
数据结构 其他

3 4

5

江凡

问题求解选讲

August 10, 2016

数论基础

同余

同余的定义与性质
如果 m 整除 a

? b,我们就说 a 与 b 模 m 同余并记为
a

≡b

(mod m)

简单来说,就是它们模 m 后的余数相同就可以记成这样。

如果

≡ b1 a2 ≡ b2
a1

(mod m) (mod m) (mod m) (mod m)

那么

a1 ± a2≡ b1 ± b2 a1a2≡ b1 b2

江凡

问题求解选讲

August 10, 2016

数论基础

同余

分治思想与快速幂方法

例5,输入b,p,k的值,求 bp mod k 的值。如,59 mod 7 = ?

(a1 × a2)mod b= (a1 mod b)×( a2 mod b) mod b
59 = 【(5 × 5) × (5 × 5)】× 【(5 × 5) × (5 × 5)】× 5 4 4

2
4

2 5 6

江凡

问题求解选讲

August 10, 2016

数论基础

同余方程与中国剩余定理

中国剩余定理
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何? ——《孙子算经》

这个问题说的是:有一个整数,被 3 除余 2,被 5 除余 3,被 7 除余 2,问这个 整数是多少? 事实上,这个问题有无穷多个解,其中一个解是 23。
中国剩余定理,又称为孙子定理,常常简写成 CRT(Chinese Remainder Theorem)。它给出了构造如下方程组解的方法: ? x ≡ a1 (mod m1 ) ? ? x ≡ a2 (mod m2 ) .. ? ? ? . ? x ≡ an

(mod mn )

其中 m1 , m2 , . . . , mn 两两互素。
江凡 问题求解选讲 August 10, 2016

数论基础

同余方程与中国剩余定理

中国剩余定理
首先来解只有两个方程的方程组。 x ≡ a1 x ≡ a2 我们可以把这个方程组改写成 (mod m1 )

(mod m2 )

x = a 1 + k1 m1
x = a 2 + k2 m2 消去 x 之后就可以得到 a1 + k1 m1 = a2 + k2 m2 ,这刚好是关于 k1 , k2 的一个 线性方程。 此外,中国剩余定理还告诉我们一个事实,在 m1 , m2 互素的条件下,假设 x0是 该方程组的一个解,那么该方程组的所有解都满足如下形式: x ≡ x0 (mod m1 m2 )

这样我们相当于把刚刚的两个方程合并成为了一个方程。如果有多个方程,可以 不断进行这样的合并,最后就可以解出结果了。
江凡 问题求解选讲 August 10, 2016

数论基础

同余方程与中国剩余定理

中国剩余定理

我们来拿刚刚开头的例子来试着算一算。那个方程组是: x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7) 首先来合并前两个方程,联立后得到的线性方程是 2 + 3k1 = 3 + 5k2 ,整理后 可以得到一组解是 k1 = 2, k2 = 1,这样可以得到满足前两个方程的 x 都满足: x ≡ 8

(mod 15)

江凡

问题求解选讲

August 10, 2016

数论基础

同余方程与中国剩余定理

中国剩余定理

之后可以得到新的方程组:

x ≡ 8
x ≡ 2

(mod 15) (mod 7)

再合并两个方程,联立后得到的线性方程是 8 + 15k1 = 2 + 7k2 ,整理后可以 得到一组解是 k1 = 1, k2 = 3,这样可以得到满足这两个方程的 x 都满足: x ≡ 23 这便是最后的解了! (mod 105)

江凡

问题求解选讲

August 10, 2016

数论基础

素数及基本知识

素数及基本知识

素数是只含有 1 及其本身两个正因子的数,也称为质数。如果还有其它正因子的 话,那么这个数就被称为合数。注意 1 并非素数,亦非合数。 我在这里介绍一个关于素数的定理,它们在算法复杂度分析中或许会用到: Theorem (素数定理) 当 x 很大时,小于 x 的素数个数近似等于x/lnx

江凡

问题求解选讲

August 10, 2016

数论基础

素数及基本知识

素数的判定
如何判定一个数 m 是不是素数,我们可以直接从定义出发,从 2 开始到m-1 为 止,检测是否有一个数整除 m,如果没有,那么这个数就是素数。 例6,求105内的所有素数。 ⒈Eratosthenes 筛法是一种用来求素数的方法,它的思路比较简单。 由于每个合数都可以被分解成几个素数的乘积,如果我们将所有素数的倍数都删 去,那么剩下的就是素数了。 因此,我们可以从 2 开始,先将 2 的所有倍数都删去。然后往下找到第一个没有 被删去的数,这个数一定是素数,再将这个数的所有倍数都删去,不断进行这个操作。 ⒉线性筛法,又称欧拉筛法。 避免冗余的运算。每个合数必有一个最大因子(不包括它本身) ,用这个因子把 合数筛掉。 对于每一个数i,乘上小于等于i的最小素因数的素数,就得到以i为最大因数的合 数。设有一个数t,只要将所有以比t小的数为最大因数的合数筛去,那么比t小的数里 剩下的就只有素数了。
江凡 问题求解选讲 August 10, 2016

组合数学基础

排列组合

组合数学基础
例7,在1与106之间,有多少个整数的各位数字之和等于9?

江凡

问题求解选讲

August 10, 2016

组合数学基础

排列组合

排列
现在来考虑一个问题:你需要在 n 个不同的人里面选出 m 个人排成一行,问有 多少种排列方案?

n(n ? 1)(n ? 2) · · · (n ? m + 1)
这个数通常被成为排列,记成 An ,或者 P n 。 如果我们定义一种名为阶乘的运算:
m
m

n! = 1 × 2 × 3 × ··· × n
特别地,当 n = 0 时,0! = 1。

那么这个数就可以简单地写成:

m An =

n!
(n ? m)!
August 10, 2016

江凡

问题求解选讲

组合数学基础

排列组合

排列
圆排列 (1)由 A ? {a1, a2 , a3 ,?, an } 的个元素中,每次取出r个元素排在一个圆环上,叫做一 个圆排列(或叫环状排列)。 (2)圆排列有三个特点:(i)无头无尾;(ii)按照同一方向转换后仍是同一排 列;(iii)两个圆排列只有在元素不同或者元素虽然相同,但元素之间的顺序不同, 才是不同的圆排列。 Pr (3)定理:在的个元素中,每次取出个不同的元素进行圆排列,圆排列数为 n 。
r

不尽相异元素的全排列 如果n个元素中,有p1个元素相同,又有p2个元素相同,?,又有ps个元素相同 ( p1 ? p2 ? ? ? ps ? n ),这个n元素全部取的排列叫做不尽相异的n个元素的全排 n! 列,它的排列数是 p !? p !?? ? p ! 。
1 2 s

江凡

问题求解选讲

August 10, 2016

组合数学基础

排列组合

组合
研究无次序的选取问题。把前述排列问题改成:你只需要在 n 个不同的人里面选

出 m 个人,问有多少种方案?
如果我们选出来 m 个人后,再将他们排成一队,那么方案数就是先前的排列 数

An

m



但是这样的计数会出现很多的重复,也就是每次我们都多算了将 m 个人排成一队

的方案数,那么这个数是什么呢?
它就是

Am

m

,或者说 m!。

那么由于每种方案都被重复计算了 m! 次,我们只要将 组合数的公式了!

An 除以 m! 就可以得到

m

m An n! m Cn = m! = m!(n ? m)!

江凡

问题求解选讲

August 10, 2016

组合数学基础

排列组合

组合数的基本性质

首先第一个性质就是先前的递推关系

m m m-1 Cn = Cn?1 + Cn?1
此外,直接根据通项可以得到一个对称的性质:

(1)

m n-m Cn = Cn

(2)

江凡

问题求解选讲

August 10, 2016

组合数学基础

排列组合

排列组合分析原理
全部组合分析公式的推导基于以下两原理: ⒈加法原理 如果完成一件事情有n种方式A1,???,An,每种方式中又有mi种方法(1≤i≤n), 且Ai Aj=? ,则要完成此事共有 N ? m1 ? m2 ??? mn ,即

N ? ? mi
i ?1

n

⒉乘法原理

如果完成一件事情要分几个步骤B1 ,B2 ,? ,Bn ,而每个步骤Bi有mi种方法 (1≤i≤n) ,那么完成这事共有 N ? m1 ? m2 ??? mn ,即

N ? ? mi
i ?1

n

江凡

问题求解选讲

August 10, 2016

组合数学基础

排列组合

例题分析
例8.7名学生站成一排,甲、乙必须站在一起有多少不同排法?(相临问题——整体

捆绑法 ) A6 ? A2 ? 1440 6 2 例9.7名学生站成一排,甲乙互不相邻有多少不同排法? (不相临问题——选空插
5 入法 ) A5 ? A62 ? 3600 例10.我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内 5 5 的抽法有多少种? (复杂问题——总体排除法或排异法 ) C43 ? C40 例11.某班新年联欢会原定的5个节目已排成节目单,开演前又增加了两个新节目.如

果将这两个节目插入原节目单中,那么不同插法的种数为( 分类讨论法 )

)(多元问题——

6 2 6 A.42 B.30 C.20 D.12 例12.从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种,分别种在不同土质的三块

A1 ? A2 ? A2

土地上,其中黄瓜必须种植,不同的种植方法共有( )(混合问题——先选后排法 ) A.24种 B.18种 C.12种 D.6种 1 2 2
3 3 2 例7 .在1与106之间,有多少个整数的各位数字之和等于9?(相同元素分配——转化 与档板分隔法 )

A ?C ? A

9 5 C9 ? 6-1 ? C14 ? 2002
江凡 问题求解选讲 August 10, 2016

组合数学基础

排列组合

例题分析
例13 .小陈现有2个任务A,B要完成,每个任务分别有若干步骤如下:A=a1-

>a2->a3,B=b1->b2->b3->b4->b5。在任何时候,小陈只能专心做某个任务的一个步 骤。但是如果愿意,他可以在做完手中任务的当前步骤后,切换至另一个任务,从上
次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱,例如??a2->b2>a3->b3??是合法的,而??a2->b3->a3->b2??是不合法的。小陈从B任务的b1步 骤开始做,当恰做完某个任务的某个步骤后,就停工回家吃饭了。当他回来时,只记 得自己已经完成了整个任务A,其他的都忘了。试计算小陈饭前已做的可能的任务步 骤序列共有 种。 排列组合+加法原理: B任务中的b1一定做,而且肯定是第一个做的。除了b1外, 第一类:完成A任务 只有1种。 第二类:完成A任务和b2 第三类:完成A任务和b2、b3 第四类:完成A任务和b2、b3、b4 第五类:完成A任务和b2、b3、b4、b5
1 有 C4 种。 2 有 C5 种。 1+4+10+20+35=70 有 C63 种。 有 C74 种。

江凡

问题求解选讲

August 10, 2016

组合数学基础

排列组合

例题分析
鸽巢原理(又称抽屉原理)(简介)
我们在讨论重排列时,如将问题化为:设盒子是有区别的,每个盒子的容量不限, 而且球数k≥盒数n,现计算无空盒出现的情况数目。 假设要用n-1块隔板,将排成一行的k个球隔成n段,但任意两块隔板不能相邻,否 则就要出现空盒,同理隔板也不能出现在两端。所以相当于要自k个球之间的k-1个间 隔中选出n-1个来放置隔板,如图 O|OO|O|OOO|O|O|OOO|OO|O 所以是一个组合问题,知有
n ?1 Ck ?1

种不同情况。

例14.x + y + z + w = 23,有多少正整数解? 解:与前面例子相似,但x、y、z、w不能等0。即知

4?1 3 C23 ?1 ? C22 ? 1540

个正整数解。

江凡

问题求解选讲

August 10, 2016

递推递归

Contents

1 2 3

归纳推理

数论基础

递推递归
递推 递归

4

数据结构 其他

5

江凡

问题求解选讲

August 10, 2016

递推递归

递推

递推
给定一个数的序列H0,H1,?,Hn,?若存在整数n0,使当n>n0时,可以 用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来, 这样的式子就叫做递推关系。
解决递推问题的一般步骤: 建立递推关系式 确定边界条件 递推求解 几种典型递推关系 Fibonacci数列 Hanoi塔问题 平面分割问题 Catalan数
江凡 问题求解选讲 August 10, 2016

递推递归

递推

递推——斐波那契数列
例15.有2×n的一个长方形方格,用一个1×2的骨牌铺满方格。 例如n=3时,为2×3方格。 此时用一个1×2的骨牌铺满方格,共有3种铺法:

试对给出的任意一个n(n>0),求出铺法总数的递推公式。

对给出的任意一个n(n>0),用F(n)表示其铺 法的总数的递推公式为: F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1)(n≥3)
江凡 问题求解选讲 August 10, 2016

递推递归

递推

递推——斐波那契数列
练习,设有一个共有n级的楼梯,某人每步可走1级,也可走2级, 也可走3级,用递推公式给出某人从底层开始走完全部楼梯的走法。 例如:当n=3时,共有4种走法,即1+1+1,1+2,2+1,3。

F(1)=1 F(2)=2 F(3)=4 F(N)=F(N-3)+F(N-2)+F(N-1)(N≥4)

江凡

问题求解选讲

August 10, 2016

递推递归

递推

递推——Hanoi塔问题
例16.Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开 始时,这n个圆盘由大到小依次套在a柱上,如图1所示。
a b c

递推关系:hn=2hn-1+1

边界条件:h1=1
图1

要求把a柱上n个圆盘按下述规则移到c柱上: (1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?

江凡

问题求解选讲

August 10, 2016

递推递归

递推

递推——平面分割问题
例17.设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好 相交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲 线把平面分割成的区域个数。

递推关系:an=an-1+2(n-1) 边界条件:a1=2
8 2 6 10 11 14 6 12 3 2 1 5 8 4 9 7 13 n=4

2 1 1 2 4 3 5 3 1

4
7

n=1

n=2 图2

n=3

江凡

问题求解选讲

August 10, 2016

递推递归

递推

递推——Catalan数
例18.在一个凸n边形中,通过不相交于n边形内部的对角线, 把n边形拆分成若干三角形,不同的拆分数目用hn表之,hn即为 Catalan数。例如五边形有如下五种拆分方案(图3),故h5=5。求对 于一个任意的凸n边形相应的hn。

图3

?C C
i ?2 i
江凡

n ?1

n ?i ?1

边界条件:C2=1
问题求解选讲 August 10, 2016

递推递归

递推

递推的应用——组合计数
例19.错排问题(经典问题)。 n个数,分别为1~n,排成一个长度为n的排列。若每一个数的位 置都与数的本身不相等,则称这个排列是一个错排。例如,n=3,则 错排有2 3 1、3 1 2。求n的错排个数。

分析:
我们设k个元素的错位全排列的个数记做:W(k)。 四个元素的错位排列W(4)用穷举法可以找到如下9个: (4,3,2,1) (3,4,1,2) (2,1,4,3) (4,1,2,3) (3,4,2,1) (3,1,4,2) (4,3,1,2) (2,4,1,3) (2,3,4,1) 它们有什么规律呢?
江凡 问题求解选讲 August 10, 2016

递推递归

递归

递推的应用——组合计数 通过反复的试验,我们发现事实上有两种方式产生错位排列: A.将k与 (1 ,2 ,?,k-1)的某一个数互换,其他k-2个数进 行错排,这样可以得到(k-1)×W(k-2)个错位排列。 B.另一部分是将前k-1个元素的每一个错位排列(有W(k-1)个) 中的每一个数与 k 互换,这样可以得到剩下的 (k - 1)×W(k-1) 个错位排列。 根据加法原理,我们得到求错位排列的递推公式W(k): W(k) = (k–1) × [W(k–1)+W(k–2)]

江凡

问题求解选讲

August 10, 2016

其他

传球问题

传球问题 例20.4个人进行篮球训练,互相传球接球,要求每个人 接球后马上传给别人,开始由甲发球,并作为第一次传球,第 五次传球后,球又回到甲手中,问有多少种传球方式?

江凡

问题求解选讲

August 10, 2016

其他

传球问题

传球问题

江凡

问题求解选讲

August 10, 2016

其他

传球问题

传球问题应用

练习:设有棱长为1米的正四面体ABCD,一只蚂蚁从顶点A 出发,遵循下列规则爬行:在每个顶点相交的3条棱中选一条, 然后沿这条棱到另一个顶点。求蚂蚁爬行了7米路之后,又回到 顶点A的方法总数。
解:设从点A出发走过n米回到点A的走法为an种。由于从A出发

走n-1米的走法共有3n-1种,其中有an-1种是走到A的,下一步一定 离开A,除去这an-1种,其它的每一种都可以再走1米到达A点。 因此, an= 3n-1 - an-1。

江凡

问题求解选讲

August 10, 2016

其他

传球问题

传球问题应用 练习:一个学生暑假在A、B、C三个城市游览。他今天在这

个城市,明天就到另一个城市。假设他第一天在A市,第五天又 回到A市,问他有几种不同的游览方案?

江凡

问题求解选讲

August 10, 2016

递推递归

递归

递归的概念与基本思想
一个函数、过程、概念或数学结构,如果在其定义或说明内部 又直接或间接地出现有其本身的引用,则称它们是递归的或者是递 归定义的。 递归过程是借助于一个递归工作栈来实现的 问题向一极推进,这一过程叫做递推; 而问题逐一解决,最后回到原问题,这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。 例,用递归算法求n的阶乘,记n! 定义:函数 fact( n ) = n! fact( n-1 ) = ( n-1 )! 则有 fact( n ) = n * fact( n-1 ) 已知 fact( 1 ) = 1

江凡

问题求解选讲

August 10, 2016

递推递归

递归

递归的概念与基本思想

下面画出了调用和返回的递归示意图

A B fact(3) 调用 fact(2) C 调用 =3*fact(2) =2*fact(1) fact(1) =3*2 =2*1 =1 =6 =2 返回 E 返回 D

江凡

问题求解选讲

August 10, 2016

递推递归

递归

递归的应用
例21.某城市的街道是一个很规整的矩形网络(见下图),有7

条南北向的纵街,5条东西向的横街。现要从西南角的A走到东北角的 B,最短的走法共有多少种?_____ 210

1
1 1

5

15

35

70

126

210

4
3 2 1

10
6 3 1

20
10 4 1

35
15 5 1

56
21 6 1

84
28 7 1

1

递归关系:F(x,y)=F(x-1,y)+F(x,y-1) 边界条件:F(1,y)=1 F(x,1)=1
江凡 问题求解选讲 August 10, 2016

递推递归

递归

递归的应用——子集划分 例22.将n个数(1,2,?,n)划分成r个子集。每个数都

恰好属于一个子集,任何两个不同的子集没有共同的数,也没 有空集。将不同划分方法的总数记为S(n,r)。 例如,S(4,2)=7, 这7种不同的划分方法依次为{(1),(234)},{(2),(134)}, {(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)}, {(14),(23)}。 当n=6,r=3时,S(6,3)=______ 90 。

江凡

问题求解选讲

August 10, 2016

递推递归

递归

递归的应用——子集划分
对任一元素an ,必然出现以下两种情况: ⑴{an}是r个子集合中的一个,于是我们只要把a1,a2,?,an-1划分为 r-1个子集,便解决了本题,这种情况下的划分数共有s(n-1,r-1)。 ⑵ {an}不是r个子集合中的一个,则an必与其它的元素构成一个子 集。则问题相当于先把a1,a2,?,an-1划分为r个子集,这种情况下的划 分数共有s(n-1,r)。然后再把元素an加入到r个子集合中的任一个中去, 共有r种加入方式,这样对于an的每一种加入方式,都可以使集合划分 为r个子集。因此根据乘法原理,划分数共有r*s(n-1,r)。

S(n,r) = S(n-1,r-1) + r × S(n-1,r)

江凡

问题求解选讲

August 10, 2016

递推递归

递归

递归的应用——子集划分
确定边界: 首先不能把n个元素不放进任何一个集合中去,即r=0时, s(n,r)=0; 也不可能在不允许空集的情况下把n个元素放进多于n的r个集合 中去,即r>n时, s(n,r)=0 ;

再者,把n个元素放进一个集合或把n个元素放进n个集合,方案 数显然都是1,即r=1或r=n时, s(n,r)=1。

S(6,3) = S(5,2) + 3 × S(5,3)
= S(4,1) + 2 × S(4,2) + 3 × (S(4,2) + 3 × S(4,3)) = ……

= 90
江凡 问题求解选讲 August 10, 2016

数据结构

Contents

1
2 3 4

归纳推理

数论基础

递推递归
数据结构 其他

5

江凡

问题求解选讲

August 10, 2016

数据结构



栈——先进后出(FILO)结构
例23.如下图,有一个无穷大的的栈S,在栈的右边排列着 1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S 让后面的车厢通过。现已知第一个到达出口的是3号车厢,请写出所 有可能的到达出口的车厢排列方案。

3
2 1 3 4 5 3 5 4

4 5

34521 34215 32145 32154 35421 32541
江凡

32451 34251 32415
问题求解选讲 August 10, 2016

数据结构



哈夫曼树(贪心思想)
以N进制编码方式对一个英文字串中的字符进行编码,每个不 同的字符其编码不同.使得由新的编码替代原串后总码长最小,且 输入0,1,2,...,N-1构成的数字串后,依照该编码方 式可以正确的对译出唯一的英文原串. 如: N=3 英文原串为 ABBCBADDACE 其对应的一种编码方式为 A:00 B:01 C:020 D:021 E:022 原串对译后的编码为000101020010002102 100020022 其码长为27 若输入编码串 0102002200 则对应的英文原串为 BCEA
江凡 问题求解选讲 August 10, 2016

数据结构



图——最短路径 例24.有 6个城市,任何两个城市之间有一条道路连接,6 个城市之间两两之间的距离如下表表示,则城市1到城市 6 的最 短距离为______。
城市1 城市2 城市3 城市4 城市5 城市6

城市1 城市2 城市3 城市4 城市5 城市6

0 2 3 1 12 15

2 0 2 5 3 12

3 2 0 3 6 5

1 5 3 0 7 9

12 3 6 7 0 2

15 12 5 9 2 0

江凡

问题求解选讲

August 10, 2016

数据结构



图——最短路径 Dijkstra迪杰斯特拉算法是解决单源最短路径问题的贪心算法。
基本思想:设置两个顶点的集合S和T=V-S,集合S中存放已找到最短

路径的顶点,集合T存放当前还未找到最短路径的顶点。初始状态时,
集合S中只包含源点v0,然后不断从集合T中选取到顶点v0路径长度最 短的顶点u加入到集合S中,集合S每加入一个新的顶点u,都要修改顶 点v0到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短 路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u 到该顶点的路径长度值中的较小值。此过程不断重复,直到集合T的 顶点全部加入到S中为止。

江凡

问题求解选讲

August 10, 2016

30

0 8 2 5 3 6 4

13
2

32 1 9 7 5 17 6

终点

从V0到各终点的最短路径及其长度 13 13 V1 -------------------<V0,V1> <V0,V1> 8 V2 -------------------------<V0,V2> 13 13 ? V3 ------<V0,V2,V3> <V0,V2,V3> -------19 30 30 30 V4 <V0,V4> <V0,V2,V3,V4> -------<V0,V4> <V0,V4> 22 ? 22 21 ? V5 <V0,V1,V5> <V0,V1,V5> <V0,V2,V3,V4,V5> 20 32 20 20 32 V6 <V0,V1,V6> <V0,V6> <V0,V6> <V0,V1,V6> <V0,V1,V6> V4:19 V1:13 V3:13 V6:20 V2:8 Vj <V0, V1,V6> <V0,V2> <V0,V1> <V0,V2,V3><V0,V2,V3,V4>

其他

Contents

1
2 3 4

归纳推理

数论基础

递推递归
数据结构 其他

5

江凡

问题求解选讲

August 10, 2016

其他

容斥原理

容斥原理(基于集合论)
例25.用|A|表示集合A中元素的个数,如A={1,2,3},则|A|=3 原理一:给定两个集合A和B,要计算A∪B中元素的个数,可以分成两步 进行:
第一步:先求出∣A∣+∣B∣(或者说把A,B的一切元素都“包含”进来,加在一 起); 第二步:减去∣A∩B∣(即“排除”加了两次的元素)

即公式:|A∪B|=∣A∣+∣B∣-∣A∩B∣ 原理二:给定三个集合A,B,C;计算A∪B∪C中元素的个数,有以下公 式:
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣B∩C∣- |C∩A|+|A∩B∩C∣
江凡 问题求解选讲 August 10, 2016

其他

容斥原理

容斥原理应用

练习:在1和2015之间(包括1和2015在内)不能被4、5、6 三个数任意一个数整除的数有______个。

江凡

问题求解选讲

August 10, 2016


相关文章:
信息学奥赛普及组1-18届问题求解题解析
信息学奥赛普及组1-18届问题求解题解析_学科竞赛_高中...a 会讲英语;b 会讲英语和汉语;c 会讲英语、...行每行可以选第一、三个顶点 最多选 8 个 注意...
信息学奥赛问题求解(带答案)
信息学奥赛问题求解(带答案)_学科竞赛_初中教育_...a 会讲英语;b 会讲英语和汉语;c 会讲英语、...按条件能选出的物品是:a,b,c,f 5.答:用这些...
高中信息学竞赛各种问题求解试题及答案
高中信息学竞赛各种问题求解试题及答案_学科竞赛_高中教育_教育专区。小学、初中、...分析四个选 项,只有 D 的表述是不正确的。 本题正确答案为 D。 72.网络...
信息学竞赛中问题求解题常见考查题型分析
-1一、 二、 信息学竞赛问题求解题常见考查题型...各类信息学竞赛中的重要内容,本讲就来学习它的有关...不相临问题——选空插入法 临问题—— 不相临...
信息学奥赛7.8.9.10初赛问题求解试题
信息学奥赛7.8.9.10初赛问题求解试题_学科竞赛_小学教育_教育专区。第 7.8....10. 已知 a,b,c,d,e,f,g 七个人中,a 会讲英语;b 会讲英语和汉语;c...
信息学竞赛中问题求解题常见考查题型分析
信息学竞赛问题求解信息学竞赛问题求解题常见...各级各类信息学竞赛中的重要内容,本讲就来学习它的...不相临问题———选空插入法 二、不相临问题——...
信息学奥赛中的数学问题
整理了历年信息学奥赛普及组初赛中出现的数学问题。二、问题求解 1.已知一个...如果要在 3 个小组中分别选出 3 位组长,一位同学最多只能担任一个小组的...
信息学奥赛教学的几点心得
可能我讲了半天学生都没有理 解的问题,学生用他们自己的语言跟学生一讲,竟然...我们每年都会将在初中阶段学过 Pascal 语言、参加过竞赛或者获过奖的选 手, ...
信息学奥赛(问题求解题练习)
信息学奥赛(问题求解题练习) 隐藏>> 问题求解 姓名: 1、一个商场有 m 种颜色的小球,每种小球足够多,在这 m 种小球中挑选 n 个小 球的选法有多少种? 如...
更多相关标签:
遗传算法求解tsp问题 | 约瑟夫斯问题求解 | 回溯法求解01背包问题 | 蚁群算法求解tsp问题 | matlab求解最优化问题 | 贪心算法求解背包问题 | cplex求解tsp问题代码 | 求解l1范数最小化问题 |