当前位置:首页 >> 学科竞赛 >> 信息学奥林匹克竞赛辅导课件-归纳策略

信息学奥林匹克竞赛辅导课件-归纳策略


第三节、归纳策略
如果说对应策略的核心是举一反三、触类旁 通地对已经解决的类似问题和有关事实作联 想,外推出事物间联系的话,那么归纳策略 则是通过列举试题本身的特殊情况,经过深 入分析,最后概括出事物内在的一般规律, 并得到一种高度抽象的解题模型。

归纳法要比搜索的方法(例如以后将讲解 的枚举法、回溯法等)更能反映问题的本质。 但是并不是所有实际

问题都可以总结归纳出 一般规律,即便是可以,归纳也不是一件容 易的事情,尤其要归纳出一个数学模型更为 困难。而且归纳过程通常没有一定的规则可 供遵循。从本质上讲,归纳就是通过观察一 些简单而特殊的情况,最后总结出有用的结 论或解决问题的有效途径。

通常,归纳的过程分四个步骤:
? ? ? ?

(1) 细心的观察 (2) 丰富的联想 (3) 继续尝试 (4) 总结归纳出结论

归纳是一种抽象,即从特殊现象中找出一般关 系。但在归纳过程中不可能列举所有情况,因而最后 得出的结论还只是一种猜测(即归纳假设)。通过精 心观察而提出的归纳假设得不到证实或最后证明是错 的,也是常有的事。因此要尽可能对归纳假设加以严 格的证明,证明的方法通常使用数学归纳法。即便找 不到证明方法,也必须尽可能多地提出那些容易出错 和疏漏的边界情况加以验证,使归纳出的结论和解决 问题的途径经得起各种测试数据的检验。

问题经过分析归纳后,一般产生 四种结果:
(1) (2) (3) (4) 递推式 递归式 制定目标 贪心方案

当然,经过分析直接概括出高度抽象的数学公式 亦是一种归纳过程、一种解题的途径。但是怎样进行这 种归纳,这个问题太宽泛,与其说它是计算机算法的策 略,还不如说它是一种数学知识和数学能力,取决于解 题者本身的数学功底。我们已经在“对应策略”一节中, 对如何将试题与数学公式对应的问题作了一些讨论,这 里不再赘述。

一、递推法
瞬息变幻的世界,每一件事物都在随时间的流逝 发生着微妙的变化。而在这纷繁的变幻中,许多现象 的变化是有规律的,这种规律往往呈现出前因和后果 的关系。即某种现象的变化结果与紧靠它前面变化的 一个或一些结果紧密关联。所谓“三岁看老”,说的 就是这个道理。这一道理也正体现了递推的思想。递 推关系几乎在所有的数学分支中都有重要作用,在联 赛中更因其简捷高效而显示出独特的魅力。

1.递推关系的定义和求解方法
有一类试题,每相邻两项数之间的变化有一定的规律 性,我们可将这种规律归纳成如下简捷的递推关系式: fn=g(fn-1)或者fn-1=g’(fn)

这样就在数的序列中,建立起后项和前项之间的关 系。然后从初始条件(或最终结果)入手,一步步地按递 推关系式递推,直至求出最终结果(或初始值)。很多程 序就是按这样的方法逐步求解的。如果对一个试题,我 们要是能找到后一项数与前一项数的关系并清楚其起始 条件(或最终结果),问题就比较容易解决,让计算机 一步步计算就是了。让高速的计算机从事这种重复运算, 可真正起到“物尽其用”的效果。

递推分倒推法和顺推法两种形式:
顺推法就是由边界条件出发,通过递推关系式推 出后项值,再由后项值按递推关系式推出再后项值, 依次递推,直到从问题初始陈述向前推进到这个问题 的解为止。
倒推法就是在不知初始值的情况下,经推理而获 知问题的最终解或目标,再倒过来,推知它的初始条 件。因为这种问题的运算过程是一一映射的,故可分 析其倒推公式。然后再从最终解或目标出发,采用倒 推手段,一步步地倒推到这个问题的初始陈述。

一般分析思路:
if (求解初始条件f1) //倒推 { 由题意(或递推关系)确定最终结果fn; 求出倒推关系式fi-1=g’(fi); for(i=n; i>=2;i--) fi-1=g’(fi); //从最终结果fn进行倒推 推出倒推结果f1; } else //顺推 { 由题意(或递推关系)确定初始值f1(边界条件); 求出顺推关系式 fi=g(fi-1); for(i=2; i<=n;i++) fi=g(fi-1); //从边界条件f1出发进行顺推 推出顺推结果fn; }

由此可见,递推算法的时间复杂度一般为W(n)。 我们之所以将递推法划入归纳策略,是因为初始条件 (或最终结果)除试题己明确给定外,都是通过对问 题的整理与化简而确定的,其递推式也是对实际问题 的分析与归纳而得到的,因此递推本质上属于归纳。

2.递推关系的建立
递推关系中存在着三大基本问题:
? ? ?

如何建立递推关系,

已给出的递推关系有何性质,
以及如何求解递推关系。

其中核心问题是如何建立递推关系。

建立递推关系的关键在于寻找第n项与前面 (或后面)几项的关系式,以及初始项的值(或最 终结果值)。它不是一种抽象的概念,而是针对某 一具体题目或一类题目而言的。
下面,我们对五种典型的递推关系的建立作比 较深入具体的讨论。递推程序一般是将递推公式 “直译”成一重循环,模式性很强。

( 1 ) Fibonacci 数列
Fibonacci数列的代表问题是由意大利著名数学家 Fibonacci于1202年提出的“兔子繁殖问题”(又称 “Fibonacci问题”):
有雌雄一对兔子,假定过两个月便可繁殖雌雄各一 的一对小兔子。问过n个月后共有多少对兔子?

分析:设满X月共有兔子Fx对,其中当月新生的兔子数目 为Nx对。第x-1个月留下的兔子数设为Ox 对。则:

Fx=Nx+Ox 而Ox=Fx-1 Nx=Ox-1=Fx-2(即第x-2个月的所有兔子到第x个月都有 繁殖能力了) 所以 Fx=Fx-1+Fx-2

边界条件: F0=0, F1=1
由上面的递推关系可依次得到: F2=F1+F0=1,F3= F2+F1=2,F4=F3+F2=3 ,…, Fibonacci 数列常出现在比较简单的组合计数问题中,例 如【例9】极值问题、【例10】取石子问题、【例13】 蜜蜂爬行等问题都可以用这种方法来解决。

( 2 ) Hanoi 塔问题
?

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

要求把a柱上n个圆盘按下述规则移到c柱上: 1.一次只能移一个圆盘;

2.圆盘只能在三个柱上存放;
3.在移动过程中,不允许大盘压小盘。

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

分析:设hn为n个盘子从a柱移到c柱所需移动的盘次。 显然, 当n=1时,只需把a柱上的盘子直接移动到c柱就可以了, 故 h1=1。 当n=2时,先将a柱上面的小盘子移动到b柱上去;然后 将大盘子从a柱移到c柱;最后,将 b柱上的小盘子 移到c柱上,共计3个盘次,故h2=3。

以此类推,当a柱上有n(n>=2)个盘子时,总是先借 助c柱把上面的n-1个盘子移动到b柱上,然后把a 柱最下面的盘子移动到c柱上;再借助a柱把b柱 上的n-1个盘子移动到c柱上;总共移动 hn=2hn-1+1 边界条件:h1=1

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

分析:设an为n条封闭曲线把平面分割成的区域个数。由图 可得: a2-a1=2; a3-a2=4; a4-a3=6 。

?

从这些式子中可以看出
an-an-1=2(n-1)

?

当然,上面的式子只是我们通过观察4幅图后得出的结 论,它的正确性尚不能保证。下面不妨让我们来试着证 明一下。当平面上已有n-1条曲线将平面分割成an-1个区 域后,第n条曲线每与其他曲线相交一次,就会增加一 个区域,因为平面上已经有了n-1条封闭曲线,且第n条 曲线与己有的每一条闭曲线恰好相交于两点,不会与任 两条曲线交于同一点,故平面上一共增加 2(n-1)个区 域,加上已有的an-1个区域,一共有an-1+2(n-1)个区域。 所以本题的递推关系是

an=an-1+2(n-1),边界条件是a1=2 。

?

平面分割问题是竞赛中经常触及到的一类问题,由 于其灵活多变,常常让选手感到棘手,下题是另一 种平面分割问题,有兴趣的读者不妨自己先试着求
一下其中的递推关系。

( 4 ) Catalan 数
?

在一个凸n边形中,通过不相交于n边形内部的对角线, 把n边形拆分成若干三角形,不同的拆分数目用 hn表之, hn即为Catalan数。例如五边形有如图所示的五种拆分 方案,故h5=5。求对于一个任意的凸n边形相应的hn。 Catalan 数首先是由Euler在精确计算对凸n边形不同的 对角三角形剖分的个数问题时得到的,它经常出现在组 合计数问题中。

?

分析:设Cn表示凸n边形的拆分方案总数。由题目中的要 求可知一个凸n边形的任意一条边都必然是一个三角形 的一条边,边P1Pn也不例外,再根据“不在同一直线上 的三点可以确定一个三角形”,只要在P2,P3,… , Pn-1,点中找一个点Pk(1<k<n),与P1, Pn共同构成一 个三角形的三个顶点,就将n边形分成了三个不相交的

部分,我们分别称之为区域①、区域②和区域③。

其中区域③必定是一个三角形,区域①是一个凸k
边形,区域②是一个凸n-k+1边形,区域①的拆分方案 总数是Ck,区域②的拆分方案数Cn-k+1,故包含 △P1PkPn 的n边形的拆分方案数为 CkCn-k+1种,而Pk可 以是P2, P3, … , Pn-1 中任一点,根据加法原理, 凸n边形的三角拆分方案总数为

加法原理和乘法原理
(1)加法原理:做一件事,完成它可以有n类办法,在第 一类办法中有m1种不同的方法,在第二类办法中有m2种 不同的方法,……,在第n类办法中有mn种不同的方法, 那么完成这件事共有N=m1+m2+…+mn种不同方法. (2)乘法原理:做一件事,完成它需要分成n个步骤,做 第一步有m1种不同的方法,做第二步有m2种不同的方 法,……,做第n步有mn种不同的方法,那么完成这件事 共有N=m1×m2×…×mn种不同的方法. 要做一件事,完成它若是有n类办法,是分类问题, 第一类中的方法都是独立的,因此用加法原理;做一件 事,需要分n个步骤,步与步之间是连续的,只有将分成 的若干个互相联系的步骤,依次相继完成,这件事才算 完成,因此用乘法原理.

?

同时考虑到计算的方便,约定边界条件C2=1.

Catalan 数是比较复杂的递推关系,尤其在竞赛的时候, 选手很难在较短的时间里建立起正确的递推关系。当 然,Catalan数类的问题也可以用搜索的方法来完成, 但是,搜索的方法与利用递推关系的方法比较起来, 不仅效率低,编程复杂度也陡然提高。

( 5 )第二类 stirling 数
n个有区别的球放到m个相同的盒子中,要求无一空盒,不 同的方案数用s2(n,m)表示,称为第二类Stirling数。 分析:设有n个不同的球,分别用b1, b2,… ,bn表示。 从中取出一个球bn,bn的放法有以下两种: ? ① bn独自占一个盒子,那么剩下的球只能放在 m-1 个 盒子中,方案数为S2(n-1,m-1); ? ② bn与别的球共占一个盒子,那么可以事先将b1, b2,…,bn-1这n-1个球放入m个盒子中,然后再将球bn 可以放入其中一个盒子中,方案数为mS2(n-1,m)。

苏格兰数学家斯特林(J. Stirling, 1692-1770) 首次发现这些数并说明了它们的重要性。

?

综合以上两种情况,可以得出第二类stirling数定理:

S2(n,m)=m S2(n-1,m)+ S2(n-1,m-1) (n>1,m>=1) 边界条件为: S2(n,0)=0 S2(n,1)=1,S2(n,n)=1 S2(n,k)=0 (k>n)

?

第二类 stirling 数在竞赛中较少出现,但在竞赛 中也有一些题目与其类似,甚至更为复杂。读者不 妨自己来试着建立其中的递推关系。
通过上面对五种典型的递推关系建立过程的探讨, 可知对待递推类的题目,要具体情况具体分析,通 过找到某状态与其前面状态的联系,建立相应的递 推关系。

?

3.递推关系的应用
递推关系的应用十分广泛,其中一个非常重要的应用就 是著名的杨辉三角(又称 “Pascal三角”。杨辉三角 是根据组合公式Cnr=Cn-1r+Cn-1r-1画出来的。很显然,组 合公式、杨辉三角都属于递推关系的范围。

在今天的信息学竞赛中,递推关系的应用也日趋广泛, 下面就让我们从近年来的两道竞赛题中体会递推关系的 应用。

【例13 】 蜜蜂爬行
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不 能反向爬行,如图所示。

试求出蜜蜂从蜂房a 爬到蜂房b 的可能路线数

?

分析:这是一道很典型的Fibonacci数列类题目,其中
的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂

房,不能反向爬行”的限制,决定了蜜蜂到 n 点的路
径只能是从 n-1 点或 n-2 点到达的,故: fn=fn-1+fn-2 (a+2<=n<=b), 边界条件为 fa=1,fa+1=1.

【 例14 】 分割平面
同一平面内的n(n<=500)条直线,已知有p(p>=2)条直线 相交于同一点,则这n条直线最多能将平面分割成多少 个不同的区域?
分析:直线的平面分割与封闭曲线的平面分割十分相似, 不同之处就在于线条的曲直以及是否存在共点的直线。 由于共点直线的特殊性,我们决定先考虑p条相交于一 点的直线,然后再考虑剩下的n-p条直线。

首先可以直接求出p条相交于一点的直线将平面划分成的 区域数为2*p个

然后在平面上已经有k(k>=p)条直线的基础上,加上一条 直线,最多可以与k条直线相交,而每次相交都会增加 一个区域,与最后一条直线相交后,由于直线可以无限 延伸,还会再增加一个区域。
所以 fm=fm-1+m(m>P) ,

边界条件在前面己经计算过了,是fp=2*p 。
虽然这题看上去有两个参数,但是在实际做题中会发现, 本题还是属于带一个参数的递推关系。

【 例15 】 平面分割空间问题
一个平面把空间分成独立的两个部分,两个平面把空间分 成4个部分。n个平面,最多能把整个空间分割成多少个 部分。
分析:立体空间的情况是陌生的,但是空间和平面的关系 与平面和直线的关系是相似的。平面把空间分割成两个 部分,直线也把平面分割成两个部分。于是得到了另一 个与例题相类似的问题:n条直线,最多能把整个平面 分割成多少个部分,如图所示。

?

一条直线,把平面分割为两个部分;增加一条直线,它 与第一条直线相交,被分为两段射线,每一段射线又把 所在的区域分成两部分;因此增加了2个部分。再增加 一条直线,它与前两条直线相交,被分为三段,每一 段又把所在区域分成两部分;共增加了3个部分。 由此类推,设前k-1条直线共把平面分为ak-1个部分。 加入第k条直线,与前k-1条直线相交,被分为k段,每 一段把所在区域分为两部分;总共增加了k部分;总共 有ak-1+ k个部分。于是得到了递推关系:

?

a1=2; ak=ak-1+k; 即 ak=1+k*(1+k)/2
于是直线分割平面的问题就解决了。

既然空间和平面,与平面和直线的关系相似,那么直接把 平面换成空间,把直线换成平面,就可以直接用以上的 过程来证明未知的问题了吗?
显然是不可以的,这种仅仅根据主观的相似性得出的机械 模仿是错误的。

?

但是如果仔细分析一下错误的原因,将会发现问题的关 键:线线相交得到的是交点,面面相交得到的是直线,k个 点把直线分成k+1个部分,而k条直线则不是简单的把平 面分成k+1个部分。事实上,k条直线最多把平面分成ak 个部分!

?

因此两个问题真正的相似之处在于,一个为了计算直线 把平面分割成几部分,先计算这条直线被点(线线交点) 分割成几部分,把二维的问题化为一维的问题;另一个 要计算平面把空间分割成几部分,先计算这个平面被线 (面面交线)分割成几部分,把三维的问题化为二维的 问题。而二维的问题是已经被解决了的,于是反过来, 三维的问题也解决了。

同样是利用数学归纳法: 一个平面把空间分割成两部分;设前k-1个平面共把空 间分割成 bk-1个部分。加入第k个平面后,与前k-1个平 面相交,共有k-1条交线。 k-1 条交线把这个平面分为 几块呢?这买际上就是刚刚解决过的回题: k-1条直线, 把平面分割成: ak-1=1+k*(1+k)/2 分别把所在原来空间一分为二,总共增加了ak-1个部分, 于是平面总共把空间分割成

个部分。于是得到了递推关系:

?

利用这一递推关系来编写程序,不难求出 bn , 而且即便对很大的 n ,程序的运算速度仍然是 很快的。(当然,也可以计算出 bn的通项公 式 :

二、递归法
设一个未知函数f,用其自身构成的已知函数g来定义: f(n)=g(n,f(n-1)) n>0 f(0)=a n=0 为了定义f(n) ,必须先定义f(n-1),为了定义 f(n-1), 又必须先定义f(n-2) … ,上述这种用自身的简单情况 来定义自己的方式称为递归定义。 一个递归定义必须是有确切含义的,也就是说,必须一步 比一步简单,最后是有终结的,决不能无限循环下去。 在 f(n)的定义中,当n为0时定义一个已知数a,是最简单 的情况,称为递归边界,它本身不再使用递归的定义。

与递推一样,每一个递归定义都有其边界条件。但 不同的是,递推是由边界条件出发,通过递推公式求 f(n)的值,从边界到求解的全过程十分清楚; 而递归则是从函数自身出发来达到边界条件。在通 往边界条件的递归调用过程中,系统用堆栈把每次调用 的中间结果保存在栈区,直至求出递归边界值f(0)=a。 然后返回调用函数。返回过程中,中间结果相继出栈恢 复, f(1)=g(1,a) f(2)=g(2,f(1)) 直到 f(n)=g(n,f(n-1)) 描述递归定义的函数或求解递归问题的过程称为递 归算法。一个递归算法,本质上是将较复杂的处理归结 为简单处理,直到最简单的处理。

从实际问题中抽象递归定义和边界条件的过 程是一种归纳,通过这种归纳方式能使一个蕴含 递归关系且结构复杂的程序简捷精炼,增加可读 性。特别是在难于找到从边界到解的全过程的情 况下,如果把问题推进一步,其结果仍维持原问 题的关系,则采用递归算法编程比较合适。 但递归算法也有致命的缺点,其执行的效率 比较低,尤其在边界条件设置不当的情况,极有 可能陷入死循环或者内存溢出的窘境。

递归算法适用的一般场合为: (1)数据的定义形式按递归定义。 这类递归问题可直接转化为递推算法,递归 边界作为递推的边界条件。 (2)数据之间的关系(即数据结构)按递归定义。如 树的遍历,图的搜索等。 (3)有些问题本身没有明显的递归结构,但使用递 归求解比其他方法更简单。如递归的分治策略。 对于(2)、(3),可利用堆栈结构将其转换为 非递归算法,但结构不如递归算法简单清晰,可 读性较差。

编写递归程序时应注意如下几个问题: (1)问题的递归定义,即如何用自身的简单情况定 义自己; (2)递归边界,即递归至哪个边界值后开始回溯; (3)参与递归运算的变量有哪些,其中哪些作为值 参,哪些作为局部变量。如果有全局变量参与递 归运算的话(初始值由主程序传入,受内存限制 不便作为值参),回溯过程中必须恢复其递归前 状态。

【 例16 】计算交点数
在平面上有 n 条直线,且无三线共点。问这些直 线能有多少种不同的交点数? 输入: n 输出:以下若干行列出所有相交方案。 其中每一行为某一方案的交点个数。 分析:我们将n条直线排成一个序列。直线2与直线1最 多有一个交点;直线3与直线1和直线2最多有2个交 点,…,直线n与其他n-1条直线最多有n-1个交点。 由此得出n条直线互不平行且无三线交于一点的最 多交点数中1+2+,…+(n-1)=n*(n-1)/2.



我们来具体分析 n=4 的情况 (1)四条直线全部平行,无交点,g[0]=1 (2)其中三条(n-1)直线平行,交点数为 (n-1)x1 + 0 = 3 , g[3]=1 (3)其中两条(n-2)直线平行,这两条直线与另外两条直线 之间的交点数为(n-2)x2=4而另外两条直线本身既可能平 行也可能相交,因此交点数分别为: 当平行时(n-2)x2+0=4 g[4]=1 当相交时(n-2)x2+1=5 g[5]=1 (4)四条直线互不平行,交点数为: 1+2+3=6 g[6]=1 即n=4时,有0、3、4、5、6 个不同的交点数

由此得出: m 条直线的交点方案 = r条平行线与(m-r)条直线交叉的交点数 + (m-r)条直线本身的交点方案 = (m-r)r + (m-r)条直线本身的交点数(1<=r<=m)
显然,计算不同交点数的问题是递归的

可以描述成如下递归算法:
//m是直线数,j是交点数
void cross(int m,int j) { if (m>0) //若直线存在,则递归计算所有的交叉情况 for(int r=m;r>=1;r--) cross(m-r,j+r*(m-r)); else //否则确定m条直线存在j个交点 g[j]=1; }

计算和输出 n 条直线的交点方案如下:
#include <iostream> using namespace std; const int MAX=10000; static int g[MAX]; void main() { int n,k,total=0; cin>>n; k=n*(n-1)/2; cross(n,0); for(int i=0;i<=k;i++) if(g[i]==1) { total++;cout<<i<<endl; } }

三、制定目标
有些问题看似棘手,主要是没有找到解决问题的 路子,或者说目标不明确。一旦建立了评判好坏的标 准(目标函数或者目标方案),求解问题的算法也就自 然而然地产生了。关键是建立标准。而这个标准是通 过对实际问题的分析与归纳得到的。因此,我们将之 划入归纳的范畴。

【 例17】 最优分解方案

把正整数n分解成若干个互不相等的自然数的和,且 使这些自然数的乘积最大。请你编写一个算法,由键盘 输入n, 求满足条件的分解方案。 输入:n(3<=n<=1000) 输出:乘积 分析:如何把正整数n分解成若干互不相等的自然数的和, 且使这些自然数的乘积最大呢?如果我们对这个问题不 探究解析方法而去盲目搜索所有分解方案的话,则代价 相当大。但是如果我们一旦耐心地对问题认真思考一番, 是不难得出其中隐含着的数学规律的。设:

由于 1<=a1< a2<…<an,因此s/n>1 。很明显,要使得乘
积 a1×a2× …×an最大,则必须使得项数n最大,且相邻 两数ai+1-ai的差最小,这就是解决问题的目标方案。

为了达到这个目标,我们不妨设a1=2(因为a1=1 时,a1在 乘式中无意义),先求出:

n=2+3+4+,…,+ak+ak+1

ak>=ak+1

这种分解方案的项数无疑最多。问题是要保证ak+1<=ak, ak+1要么为1,要么重复其中某一项,因此必须撤去。为 了保证撤去ak+1后的各个自然数依然互不相等,其和还 是等于n且乘积最大,我们将 ak+1尽量平均地加在后几 项。并尽可能使得相邻两数的差不超过2

①若ak+1=1,由于1x2x,… ,xak<2x3x,…,x(ak+1),因此 ak+1=1加到ak上; ②若1<ak+1<ak,我们从ak出发,依次向尾部ak+1个数加1; ③若ak+1=ak,则ak加上2,其余k-1个数依次加1; 当然,还必须考虑一个例外情况:当n=3或n=4 时,只能 分解出一个表达式:

3=1+2
4=1+3

mul = 1x2 =2
mul = 1x3 =3

由此可见,上述目标方案是分解自然数的依据。

有了这个目标方案,相应的算法也就可以设计出来了。

#include <iostream> using namespace std; const int MAX=1000; static int a[MAX]; void main() { int n,mul=1; cin>>n; if ((n==3)||(n==4)) mul=1*(n-1); //当n=3或4时,输出分解方案。 else

{ int k=1; a[k]=2; n=n-a[k]; //从2开始分解 while(n>a[k]) //分解直到a[k+1]<=a[k] { k++; a[k]=a[k-1]+1; n=n-a[k]; } if (n==1) { a[k]++; n--; //a[k+1]=1 } else { if (n==a[k]) //a[k+1]=a[k] { a[k]++; n--;} //1<a[k+1]<a[k] for(int i=0;i<=n-1;i++)a[k-i]++; } for(int i=1;i<=k;i++) mul=mul*a[i]; } cout<<mul; }

四、贪心法
和前面所讲的递推法相仿,贪心法也是从问题的 某一个初始解出发,向给定的目标推进。但不同的是, 推进的每一步不是依据某一固定的递推式,而是做一 个当时看似最佳的贪心选择,不断地将问题实例归纳 为更小的相似的子问题,并期望通过所做的局部最优 选择产生出一个全局最优解。对于贪心法,我们并不 陌生。例如求最小生成树、求单源最短路径使用的算
法策略实际上就是贪心法。

贪心法建议通过一系列步骤来构造问题的解,每一 步对目前构造的部分解做一个扩展,直到获得问题的完 整解为止。这个问题的核心是,所做的每一步选择都必 须满足以下条件:
? ?

可行的:即它必须满足问题的约束。 局部最优:它是当前步骤中所有可行选择中最佳的局部 选择 不可取消:即选择一旦做出,在算法的后面步骤中就无 法改变。 在每一步中,它要求“贪婪”地选择最佳操作,并 希望通过一系列局部的最佳选择,能够产生一个整个问 题的(全局的)最佳解。

?

那么如何证明按贪心选择得出的解是最优解呢? 有两种方法: (1)对贪心选择进行数学分析,从理论上证明是最优的。
(2)构造一个最优解,然后对该解进行修正,使其第一步 为一个贪心选择,证明总是存在一个以贪心选择开始的 求解方案,然后证明经过若干次贪心选择后可以得出一 个最优解。

第二种证明方法相对比较容易。

由于贪心选择的设计及其产生最优解的证明是对实际问题 分析归纳的结果.因此,我们将贪心法列为一种归纳策略。

【 例 18 】 活动选择
假设有一个需要使用某一资源的n个活动组成的集 合S={1,…,n}。该资源一次只能被一个活动所占用, 每一个活动有一个开始时间Si和结束时间Fi(Si<=Fi)。 若Si>=Fj或者Sj>=Fi,则活动i和活动j兼容。选择由 互相兼容的活动组成的最大集合。 输入:n S1 F1 … Sn Fn 输出:占用时间t 最大集合A中的活动序号

分析:我们使用尽可能逼近目标的贪心策略来选择活动, 即每一步总是选择这样一个活动来占用资源―它能够 使得余下的未调度时间最大化,使得兼容的活动尽可 能多。为了达到这个目的,我们将n个待选活动按结束 时间递增的顺序排列:
F1<=F2<=…<=Fn 递增序列中的活动1进入集合A。然后依次分析序列 中的活动2到活动n,将那些与A中活动兼容的活动送入 集合A。

例如 活动 1 2 3 4 5 6 7 8 9 10 11

开始时间 3 1 12 8 0 8 6 5 3 5 2

结束时间 5 4 14 12 6 11 10 7 8 9 13

#include <iostream> using namespace std; const int N=11; //活动序号 int no[N]={1,2,3,4,5,6,7,8,9,10,11}; //开始时间 int s[N]={3,1,12,8,0,8,6,5,3,5,2}; //结束时间 int f[N]={5,4,14,12,6,11,10,7,8,9,13};

void swap(int &x,int &y) { int temp=x; x=y; y=temp;} //选择排序 void sort() { for(int i=0;i<N-1;i++) { int min=i; for(int j=i+1;j<N;j++) if(f[min]>f[j]) min=j; swap(f[min],f[i]); swap(no[min],no[i]); swap(s[min],s[i]); } }

void main() { static int a[N]; //a是兼容集合 int t=0; //t是占用时间 sort(); //按结束时间递增的顺序排序 int k=0; int j=0; a[k]=no[0]; //初始活动表为NO[0] for(int i=1;i<N;i++) { //若递增序列中的活动i与A集合中的活动兼容 if(s[i]>=f[j]) { k++; a[k]=no[i]; t=f[i]; j=i; } } cout<<t<<endl; for(i=0;i<=k;i++) cout<<a[i]<<" "; }

贪心选择的过程 t=14 a={2,8,6,3}

我们使用第二种方法证明按照这个贪心选择的解一定是 最优的:

(1)构造一个最优解,然后对该解进行修正,使其第一步 为一个贪心选择,证明总是存在一个以贪心选择开始 的求解方案。
设最优解为a。第一个选中的活动为k(k不等于1)。如果 另一个解b开始于贪心选择活动1 (b=(a-{k})U{1})。 因为f1<=fk,所以b中的活动是兼容的。又因为b与a的 活动数相同,所以b也是最优的。由此证明总存在一个 以贪心选择开始的最优调度。

(2)证明经过若干次贪心选择后可以得出一个最优解 当我们作出了对活动1的贪心选择后,原问题就变成在活 动2至活动n中找与活动1兼容的那些活动的子问题。 也就是说,如果问题a为原问题的一个最优解,则a’=a-{1} 就是活动选择问题s’的一个最优解。为什么会这样呢?如 果我们能找到s的一个含有比a’更多活动的解b’则将活动1 加入了b’,就得到s的一个包含比a更多活动的解b,这就与a 的最优性相矛盾。所以在每一次贪心选择后,留下的是一 个与原问题具有相同形式的最优化问题.通过对所做选择 次数的归纳可以证明,对每一步进行贪心选择就可得到一 个最优解. 由此得出,按照这个贪心选择得出的解一定是最优的。

2801【例19】打包( Packaging )
某个工厂生产出的产品都要被打包放入正四棱柱的盒子 内。所有盒子的高度都为h,但底面的尺寸不同,可以 为1x1,2x2,3x3,4x4,5x5,或 6x6,如图所示。

这些盒子将被放入高度为h,底面尺寸为6x6的箱子里,送到 消费者手中。为了降低运送成本,工厂希望尽量减少箱 子的数量。如果有一个好的算法,能使箱子的数量降到 最低,这将给工厂节省不少资金。请你写一个这样的程 序。 输入:六个非负整数a1,a2,a3,a4,a5,a6。它们分别为底 面尺寸为1x1,2x2,3x3,4x4,5x5,6x6的盒子的个数。
输出:一个数b,即箱子的最少个数。

分析:让我们来看看可供选择的装箱方法:

(1)如果有6x6的盒子,则将它放入箱子,这个箱子就满了, 该过程直到6x6的盒子全部装箱为止;

(2)如果有5x5的盒子,则将它放入箱子,这个箱子还有空 余,可以放入尽可能多的1x1的盒子,这个过程的结束 条件是5x5的盒子全部装箱,并且1x1的盒子全部装箱或 者箱子全部装满;
(3)如果有4x4的盒子,箱子中的剩余空间可以放2x2的盒 子,如果还有剩余,则放1x1的盒子,这个过程直到4x4 的盒子全部装箱,并且剩余空间被充分利用;

……

简而言之就是每次找出最大的盒子放入当前的箱子中,直 到无法再放;再拿一个空箱继续这一过程,直到所有的 盒子都被装箱。解决这一类问题我们通常采用贪心算法。
下面我们使用第一种方法来证明对于打包问题,贪心法可 以得出最优解。设要装下a1个1x1的盒子,a2个2x2的盒 子,… … ,a6个6x6的盒子需要的箱子数为 f(a1,a2,a3,a4,a5,a6)个。由前面的分析可知:

(1)由每一个 6x6 的盒子都刚好放入一个6x6的箱子可得 等式:f(a1,a2,a3,a4,a5,a6)=f(a1,a2,a3,a4,a5,0)+a6

(2)己知放置每一个5x5的盒子都需要一个箱子,但每个箱 子放入一个5x5的盒子后还有6x6-5x5=11 个单位的空间, 而这些空间只能放1x1的盒子,最多放11个,可得等式: f(a1,a2,a3,a4,a5,0)=f(max{0,a1-11*a5},a2, a3,a4,0,0)+a5

(3)已知放置每一个4x4 的盒子都需要一个箱子,之后还 有 6x6-4x4=20个单位的空间。这些空间恰好可以放入

5个2x2的盒子,或20个1x1的盒子。根据尽可能先放大
盒子的贪心策略, 我们尽量先放2x2的盒子。放置a4个4x4的盒子需要 a4个箱子,剩余 5*a4个2x2的空间。

若a2>=5*a4,则这些空间全部用掉,否则剩下 的空间还可以“见缝插针”地放入1x1的盒子。 由此可得等式:

(4)已知每个箱子可以放4个3x3的盒子。这样4个4个放

完后,可能还剩余0,1,2,3个3x3的盒子。与放置 4x4
的盒子时同样的原理,还是先放2x2的盒子,再放1x1的 盒子。

在这4种情况下分别还能放 0,1,3,5个2x2的盒子。 剩余的空间再放入1x1的盒子。

(5)一个箱子可放9个2x2 的盒子,放完 2x2 的 盒子后,多余的空间 放 1x1 的盒子。等式 如下:

(6) 放置 1x1 的盒子时有关系式(图j):

这六个等式的顺序即为贪心策略。由此证明贪 心法可以求得最优解

int pack(int a1,int a2,int a3,int a4,int a5,int a6) { int c=a6; c=c+a5; //加上放入6x6,5X5的盒子数 a1=max(0,a1-11*a5); c=c+a4; if(a2>=5*a4) a2=a2-5*a4; else {a1=max(0,a1-(20*a4-4*a2)); a2=0;}

if (a3%4==0) c=c+a3/4; else c=c+a3/4+1; if (a3%4==3) { a1=max(0,a1-(9-4*min(1,a2))); a2=max(0,a2-1);} else if (a3%4==2) { a1=max(0,a1-(18-4*min(3,a2))); a2=max(0,a2-3);} else { a1=max(0,a1-(27-4*min(5,a2))); a2=max(0,a2-5);} //a3%4==1

if(a2%9==0) c=c+a2/9; else c=c+a2/9+1; if(a2%9!=0) a1=max(0,a1-(36-4*(a2%9))); if(a1%36==0) c=c+a1/36; else c=c+a1/36+1; return c; }

#include <iostream> using namespace std; inline int max(int a,int b) {return a>b?a:b;} inline int min(int a,int b) {return a<b?a:b;} void main() { int a1,a2,a3,a4,a5,a6; cin>>a1>>a2>>a3>>a4>>a5>>a6; cout<<pack(a1,a2,a3,a4,a5,a6); }

#include <iostream> //优化 #include <cmath> using namespace std; int main() { int c,a1,a2,a3,a4,a5,a6,x,y; int u[4]={0,5,3,1}; // 当放3*3产品时剩余放2*2数 while(cin>>a1>>a2>>a3>>a4>>a5>>a6) { if ((a1==0)&&(a2==0)&&(a3==0)&& (a4==0)&&(a5==0)&&(a6==0)) break; c=a6+a5+a4+ceil(a3/4.0);y=5*a4+u[a3%4]; if (a2>y) c+=ceil((a2-y)/9.0); x=36*c-36*a6-25*a5-16*a4-9*a3-4*a2; if(a1>x) c+=ceil((a1-x)/36.0); cout<<c<<endl; } return 0; }

贪心算法的基本要素
可以用贪心算法求解的问题一般具有两个重要的性质:贪
心选择性质和最优子结构性质

1.贪心选择性质:所求问题的整体最优解可以通过一系列
局部最优的选择,即贪心选择来达到。 贪心算法所做的贪心选择可以依赖于以往所做过的 选择,但决不依赖于将来所做的选择,也不依赖于子问 题的解。

贪心算法通常以自顶向下的方式进行,以迭代的方 式做出相继的贪心选择,每做一次贪心选择就将所求问 题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性 质,必须证明每一步所做的贪心选择最终导致问题的整 体最优解。 2.最优子结构性质:当一个问题的最优解包含其子问题的 最优解时,称此问题具有最优子结构性质。问题的最优 子结构性质是该问题可用动态规划算法或贪心算法求解 的关键特征。

本节作业
一、简要回答如下问题: ? 简述归纳过程步骤? ? 递推方法一般分析思路是什么? ? 递归算法适用的一般场合是什么? ? 简述贪心算法的基本要素

二、根据题意,建立如下问题的递推公式或 递归公式? (1) Fibonacci 数列 (2) Hanoi 塔问题 (3) 封闭曲线分割平面问题 (4) Catalan 数 (5) 第二类 stirling 数 【例13】 蜜蜂爬行 【例14】 直线分割平面 【例15】 平面分割空间问题

第四节、模拟策略
在自然界和日常生活中,许多现象具有不确定的 性质,有些问题甚至很难建立数学模型,或者很难

用计算机建立递推、递归、枚举、回溯等算法。在
这种情况下,一般采用模拟策略。 所谓模拟策略就是模拟某个过程,通过改变数学 模型的各种参数,进而观察变更这些参数所引起过 程状态的变化,由此展开算法设计。

模拟题没有固定的模式,一般形式有两种: (1) 随机模拟:题目给定或者隐含某一概率。设计者利用

随机函数和取整函数设定某一范围的随机值,将符合概
率的随机值作为参数。然后根据这一模拟的数学模型展 开算法设计。由于解题过程借助了计算机的伪随机数发 生器,其随机的意义要比实际问题中真实的随机变量稍 差一些,因此模拟效果有不确定的因素。

(2)过程模拟:题目不给出概率,要求编程者按照题意
设计数学模型的各种参数,观察变更这些参数所引起 过程状态的变化,由此展开算法设计。模拟效果完全 取决于过程模拟的真实性和算法的正确性,不含任何 不确定因素。

由于过程模拟的结果无二义性,因此竞赛大都采
用过程模拟。

模拟的解题方法一般有三种类型:

(1)直叙式模拟 (2)筛选法模拟 (3)构造法模拟

一、直叙式模拟
直叙式模拟,即按照试题要求展开模拟过程。
编程者要忠实于原题,认真审题,千万不要疏 漏任何条件,精心设计方便模拟的数据结构。 直叙式模拟的难度取决于模拟对象所包含的动 态变化的属性个数,动态属性愈多,则难度愈大。

【例 19】约瑟夫问题

有n只猴子,按顺时针方向围成一圈选大王(编号从 1到n),从第1号开始报数,一直数到m,数到m的猴 子退出圈外,剩下的猴子再接着从1开始报数。就这样, 直到圈内只剩下一只猴子时,这个猴子就是猴王,编程 求输入n,m后,输出最后猴王的编号。 Input:每行是用空格分开的两个整数,第一个是 n, 第二 个是 m ( 0 < m,n <=300)。最后一行是:0 0
Output:对于每行输入数据(最后一行除外),输出数据 也是一行,即最后猴王的编号

Sample Input 62 12 4 83 00
Sample Output 5 1 7

解题思路1:
用数组loop来存放n个数,相当于n个数排成的圈, 用整型变量nPtr指向当前数到的数组元素,相当于 人的手指,划掉一个数就将该数置0,在数数时,要 跳过为0的元素。当nPtr指向最后一个元素时再数下

一个时则指向数组的头一个元素。

#include<iostream.h> { int nCount=0; while(nCount<m) const int MAX=300; { while(loop[nPtr]==0) int loop[MAX]; nPtr=(nPtr+1)%n; void main() nCount++; { int n,m,i; nPtr=(nPtr+1)%n; } while (1) nPtr--; { cin>>n>>m; if(nPtr<0) nPtr=n-1; if (n==0) break; if (i==n-1) for(i=0;i<n;i++) cout<<loop[nPtr]; loop[i]=i+1; loop[nPtr]=0; } int nPtr=0; for(i=0;i<n;i++) } }

#include <iostream.h> 采用循环链表实现 采用循环链表实现如下 struct Monkey { int ID; Monkey *next; }; int main() { Monkey *link,*monkey,*lastMonkey; int n,m,count; cin>>n>>m; link=NULL; for(int i=0;i<n;i++) { monkey=new Monkey; monkey->ID=i+1; if (link==NULL) link=lastMonkey=monkey; else{ lastMonkey->next=monkey; lastMonkey=monkey;} } lastMonkey->next=link;

}

count=1; while(link!=NULL) { if(link->next==link) { cout<<link->ID; delete link; break;} if (count==m-1) { monkey=link->next; link->next=monkey->next; delete monkey; count=0; } link=link->next; count++; } return 0;

【例 20】 DAM 语言
有个机器执行一种DAM语言。该机器有一个栈,初始
时栈里只有一个元素x,随着DAM语言程序的执行,栈里 的元素会发生变化。DAM语言有三种指令:
? ? ?

D 指令:把栈顶元素复制一次加到栈顶。 A 指令:把栈顶元素取出,加到新的栈顶元素中。 M 指令:把栈顶元素取出,乘到新的栈顶元素中。

如果执行A或M指令的时候栈内只有一个元素,则机 栈顶元素应该是X的多项式,例如,程序 DADDMA 的执
用逗号隔开):

器会发出错误信息。如果程序无误,那么执行完毕以后,

行情况为(栈内元素按照从底到顶的顺序从左至右排列,

给出一段DAM程序,求出执行完毕后栈顶元素。 输入:输入仅一行,包含一个不空的字符串s,长度不超 过12,代表一段DAM程序。输入程序保证合法且不会导 致错误。 输出:仅输出一行,即栈顶多项式。须按照习惯写法降 幂输出,即等于1的系数不要打印,系数为0的项不打 印,第一项不打印正号。一次方不打印“^1”。

分析:本题是一道“直叙式模拟”题,即按照 DAM指令 的顺序模拟执行过程。在模拟的时候有些问题是需要 注意的:

(1)多项式的表示方式。有的选手或许会觉得本题没有说 明次数的上限,因此最好用链表做。其实完全没有必要。 由于指令不超过12条,而D指令和A、M指令总数应该相 等,因此最多有6条M指令,因此次数上限为26=64。我 们可以用数组来表示多项式,既方便又不会导致时间和 空间上的问题。
(2)本题也没有说明系数的最大值。稍微细心的选手会发 现:它最大可能为232, 未超过长整数的范围,不存在非 得用高精度的必要。

#include <iostream.h> #include <string.h> void main() { static int degree[13];//存储系数个数的栈 static long co[13][65];//存储多项式的栈 long tmp[65]; //系数序列 char s[13]; //DAM程序 int i,j; int top=1; //栈顶指针 degree[1]=1; co[1][1]=1;

cin>>s;

for(i=0;i<strlen(s);i++) { switch(s[i]) { case 'D': top++; degree[top]=degree[top-1]; for(j=0;j<=degree[top];j++) co[top][j]=co[top-1][j]; break;

case 'A': top--; if(degree[top]<=degree[top+1]) degree[top]=degree[top+1]; for(j=0;j<=degree[top];j++) co[top][j]=co[top][j]+co[top+1][j]; break;

case 'M': top--; for(j=0;j<65;j++) tmp[j]=0; int d=degree[top]+degree[top+1]; for(int a=0;a<=degree[top];a++) for(int b=0;b<=degree[top+1];b++) tmp[a+b]=tmp[a+b]+co[top][a]*co[top+1][b]; degree[top]=d; for(j=0;j<=d;j++) co[top][j]=tmp[j]; break; } }

//第一项不带+号 bool first=true; //降幂输出栈顶多项式 for(i=degree[top];i>=1;i--) if (co[top][i]!=0) { if (first) first=false; else cout<<'+'; if (co[top][i]!=1.0) cout<<co[top][i]; cout<<'x'; if (i>1) cout<<'^'<<i; } cout<<endl; }

二、筛选法模拟
模拟过程中可能产生的所有解组成一个筛。
筛选法模拟,即先从题意中找出约束条件,然后将

筛中的每一个可能解放到约束条件的过滤器上,一次一
次地将不符合条件的解过滤掉,最后沉淀在筛中的即为 问题的解。 筛选法模拟的结构和思路简明、清晰,但带有盲目 性,因此时间效率并不一定令人满意。筛选法模拟的关

键是找准约束条件,任何错误和疏漏都会导致模拟失败。

【 例21 】 蒙特卡洛法
计算定积分
其中 输入: a b d a0 a1…… ak(表示 f(X)= akxk + , … , +a1x + a0) 输出: S

分析:产生n(足够大)个均匀分布在长方形abcd上的随机
数点(xi,yi)。其中: yi:均匀分布在[0,d]上的随机数,即 yi=rand()%d; n个随机数点组成一个筛。约束条件的过滤器是某点 则该点从筛中过滤掉。

xi:均匀分布在[a,b]上的随机数,即 xi=a+rand()%(b-a);

(xi,yi)是否落在曲边梯形aefb外。如果是(yi>=f(xi)) ,

最后有m个随机数点留在筛中(这些随机数点落在曲边梯形
abfe内)。曲边梯形abfe面积应该为m和n的比值乘以长 方形abcd的面积:

按照定积分的几何定义,s即为定积分的值

#include <iostream.h> #include <stdlib.h> #include <math.h> const int MAX=100; //f(x)函数的最大次数 double amoncar(int a,int b,int d,double co[],int n) { int m=0; for(int i=0;i<n;i++) { int x=a+rand()%(b-a); int y=rand()%d; double f=0.0; for(int j=MAX;j>=0;j--) f=f+co[j]*pow(x,j); if (y<f) m++; }return m/n*(b-a)*d; }

void main() { int a,b,d,n; double co[MAX]; int i=0; cin>>a>>b>>d>>n; while(cin>>co[i++]); cout<<amoncar(a,b,d,co,n); } 在主程序中,输入随机点的个数n以及a,b,d等,调 用函数amoncar计算和输出定积分的值。
注意, n 愈大,定积分的值愈精确,速度愈慢。

三、构造法模拟

构造法模拟需要完整精确地构造出反映问题本质 的数学模型,根据该模型设计状态变化的参数,计算模 拟结果。 由于数学模型建立了客观事物间准确的运算关系, 因此其效率一般比较高。构造法模拟的关键是找到数学 模型。问题是,能产生正确结果的数学模型并不是惟一 的,从不同的思维角度看问题,可以得出不同的数学模 型,而模拟效率和编程复杂度往往因数学模型而异。即 便有数学模型,但解该模型的准确方法是否有现成算法、 编程复杂度如何,这些都是我们要考虑的问题。

本节作业与练习
一、简要回答如下问题: ? 模拟策略主要有哪两种形式? ? 模拟解题方法一般有三种类型?

二、给出下列问题的解题思路及算法实现 【例20】 DAM语言 【例21】 蒙特卡洛法


更多相关文档:

信息学奥林匹克竞赛培训教案

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...信息学奥林匹克竞赛培训教案_学习计划_计划/解决方案...利用计算机对所获取的信息进行记录、整理、加工、存储...

信息学奥林匹克竞赛指导心得

进入到这一层面的同学就需要和 指导教师一起来研讨关于竞赛的诸多问题了,例如程序算法,程序的调试,比赛 时的策略,比赛的心态等等环节。中学生信息学奥林匹克竞赛是...

信息学奥林匹克竞赛培训教案(校本课程)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...信息学奥林匹克竞赛培训教案(校本课程)_学科竞赛_高中...利用计算机对所获取的信息进行记录、整理、加工、存储...

信息学辅导总结

信息学奥林匹克竞赛辅导总结 2007~2008 学年度第二学期桂江一中 刘凤兰 本学期,辅导工作逐渐走上轨道,有条不絮地进行,并取得了历 史性的最好成绩,主要有以下几...

信息学奥林匹克竞赛培训说明

信息学奥林匹克竞赛培训说明信息学奥林匹克竞赛培训说明隐藏>> 信息学奥林匹克竞赛培训说明: 信息学奥林匹克竞赛培训说明: 1、教材:可两本选一本 、教材: 建议...

信息学奥林匹克竞赛辅导Pascal语言

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...信息学奥林匹克竞赛辅导Pascal语言_哲学/历史_人文...穷举策略 第七章 贪心算法 第八章 分治策略 Ⅳ ...

信息学奥林匹克竞赛培训教案

搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...信息学奥林匹克竞赛培训教案 (PASCAL 语言) 授课: ...利用计算机对所获取的信息进行记录、整理、加工、存储...

信息学竞赛辅导资料

第0 章 概述 0.1 关于信息学奥林匹克竞赛全国...PPT WMV、RM、QT ZIP、RAR HTM、ASP BMP、JPG、...算法基本设计方法 算法基本设计方法:列举法、归纳法...

基于新形势下信息学奥林匹克竞赛的策略研究与实践

龙源期刊网 http://www.qikan.com.cn 基于新形势下信息学奥林匹克竞赛策略研 究与实践 作者:崔国亮 来源:《中国信息技术教育》2015 年第 02 期 ● 以学生...
更多相关标签:
信息学奥林匹克竞赛 | 信息学奥林匹克竞赛题 | 信息学奥林匹克竞赛书 | 归纳是一种认知策略 | 逆向归纳策略例题 | 辅导班招生策略 | 初中物理竞赛辅导 | 五年级奥数竞赛辅导 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com