大榕树——让我们共成长!
大榕树 myDrs.org
您的位置:大榕树 \ 编程       |  Logo语言   |  Pascal语言   |  信息学奥赛   |  高考保送    |  HTML版本
|  Pascal语言>>算法与技巧>>解题策略的谋划         本站全文搜索: 友情提示:

解题策略的谋划
http://www.mydrs.org  8/11/2001  大榕树


1、降格思想:从对问题的特殊和简单状态的分析中归纳出问题的实质内涵或规律,从而得到问题的一般解法,也就是我们常说的"投石问路"或者叫做"尝试归纳"。这种通过特殊求得一般、通过实际求得抽象的思想在谋划策略的过程中是十分有效的,特别是当题目中所给的数据比较大或者很抽象而难以入手时,常用这种思想来谋划策略。

问题一:(台阶问题)一个人登上一个10级的台阶,可以一步登1级,也可以一步登2级。问:一共有几种登法?
这道题中的台阶数为10,虽然不是很大,但一时也很难入手。我们运用降格思想分析这个问题,先看几种简单的情形:
A、仅有1级台阶时,登法只有1种:一步1级。
B、有2级台阶时,登法有2种:一步2级;1级+1级(两步)。
C、有3级台阶时,登法有3种:1级+1级+1级;1级+2级;2级+1级。
  这里"1级+2级"表示先登1级再登2级;"2级+1级"表示先登2级再登1级,显然这两种登法是不同的。
D、有4级台阶时,登法有5种:
  1级+1级+1级+1级;
  1级+1级+2级;
  1级+2级+1级;
  2级+1级+1级;
  2级+2级。
E、有5级台阶时,登法有8种:
  1级+1级+1级+1级+1级;
  1级+1级+1级+2级;
  1级+1级+2级+1级;
  1级+2级+1级+1级;
  1级+2级+2级;
  2级+1级+1级+1级;
  2级+1级+2级;
  2级+2级+1级。
按照台阶数递增的次序把登法的种数排列如下:
1,2,3,5,8……
容易想到这是菲波那契数列的一部分,这就找到了问题的规律,同时也谋划出解决问题的策略:数学模型(规律)策略。容易得到后继数据是:13,21,34,55,89……,于是得到问题的解:10级台阶共有89种登法。
当然,关于找到的规律的正确性必须给出详细的证明,这里不再详述。应用这个例子无非是为了说明从简单出发考虑问题的优越性,同时指出,敏锐的洞察已有数据的能力对于谋划策略也是相当重要的。
2、升格思想:这种思想与第一种思想恰恰相反,它是把一些过于具体的问题抽象化,目的是忽略其中的一些次要因素,从而更好地把握其中的主要因素,通过解决一般问题从而解决具体问题。有时会发生这样的情况:由于问题中给出的数据过于具体,往往会形成一种思维定势,一直针对具体的数据进行分析,而忽视了问题中显而易见的东西。运用这一思想有利于突破思维定势,更快地找到解决问题的策略,其关键是在于对抽象问题的分析和推理。

我们把"台阶问题"抽象化,设有n级台阶,登台阶规则不变。对于登n级台阶的最后一步有两种情况:
(1)由第n-1级台阶跨一步(1级)到达第n级;
(2)由第n-2级台阶跨一步(2级)到达第n级。
  显然,以上的两类登法是不同的,n级台阶的总登法就是这两类登法的总和。我们用F(x)表示x级台阶的登法种数,则有: F(n)=F(n-1)+F(n-2)以及F(1)=1;F(2)=2。
这就迅速地得到了问题的数学模型,也就谋划出解决问题的策略:数学模型(规律)策略。
  从这个例子的分析中可以看出,对问题的抽象概括,寻求问题的一般解法,对于某些问题的解决是十分简便的。适当运用升格思想往往可以"一箭中的",迅速描述出问题的本质,从而得到解决问题的策略。
3、分格思想:把整个问题划分为几个相联系的子问题或几个连续的解题步骤,再一一设法解决,最后综合各个部分的解就可以得到整个问题的解。作为一种思维方法,在分析问题的时候恰当运用,对于谋划解题策略是很有效的。划分问题的方法有很多种,最基本的原则是把难以描述的问题化为易于描述的问题,把不易求解的化为易求解的。
  仍是看上面的"台阶问题",由登10级台阶所用的步数不同,可以划分为如下的几种情况:
A、共要登10步(全部都是每步登1级):有1种登法;
B、共要登9步(只有某一步登2级,其余每步登1级):有C19=9种登法;
C、共要登8步(只有某两步每步登2级):有C28=28种登法;
D、共要登7步(只有某三步每步登2级):有C37=35种登法;
E、共要登6步(只有某四步每步登2级):有C46=15种登法;
F、共要登5步(全部都是每步登2级):有C55=1种登法;
因此总共的登法有1+9+28+35+15+1=89种。

  通过上面的对问题划分的过程以及计算的结果的分析,我们可以得到以下的两种策略:
(1)分治策略,直接仿照上面的划分过程由计算机加以实现。
(2)数学模型(规律)策略,从中归纳出:对于n级台阶的登法有
 种。
通过上面的例子可以看出:分格思想关键在一个"分"字,也就是如何划分问题,划分中应注意两点:
1、划分必须根据统一的标准,不重复,不遗漏;
2、划分必须具有启发性,即对于谋划问题的策略有一定的启发作用。
4、变格思想:通过转换问题某些信息,从而转化问题的形式,达到化显为隐、化繁为简、化难为易、化未知为已知的目的,通过解决等效问题来解决原问题。
再看上面的"台阶问题",我们运用变格思想对问题进行转化,考虑人在台阶上的位置变化,比如:人处于第1台阶上时,若一步登1级就可以到达第2级台阶;若一步登2级就可以到达第3级台阶。我们用点表示每一级台阶,用边表示台阶之间可以"一步到达"的关系,就可以得到下面的图:
  于是,问题就转化为:在图6中,求从点0到点10的所有路径总数。这是一个为我们所熟悉的图论问题,可以用穷举策略解决,当然这种策略相对于前面所谋划的那些策略而言没有什么优势,但毕竟也是解决问题的策略之一。
  如果说变格思想在上面的这个例子中的运用相对于其它思想没有什么优势的话,那么回想一下在解决"最佳航空路线问题"时,我们把它转化为"最短路径问题"、"最小费用流问题"就都是变格思想成功运用的例子了。
运用变格思想的关键就是要"变"得巧妙,这种思想对于探索新问题,特别是未知问题是很有效的。
以上所说的这些策略的具体算法在计算机上都是很容易实现的,具体的程序就不再给出了。

作 者:黄高峰
来 源:清华大学
共有2246位读者阅读过此文

  • 上篇文章《战略游戏》解题报告
  • 下篇文章解题策略源于问题

  • 发送邮件
    保存页面 打印文章 HTML版本 发表评论

    □- 近期热门文章 □- 相关文章
    1. NOIP2006竞赛大纲 [8306]
    2. 七类高中生具有保送资格 [5910]
    3. NOI2006获奖选手名单 [4955]
    4. 关于举办NOIP2006模拟赛的通告 [4106]
    5. Turbo Pascal各语句运行速... [3594]
    6. Turbo王者归来新Delphi免费... [3181]
    7. IOI2006我国4名选手全部获得金... [2945]
    8. 关于APIO2007与IOI2007... [2763]
    9. noip倒计时 by 枯叶蝴蝶 [2683]
    10. 朱泽园:思想上的金牌更重要 [2168]
    解题策略源于问题
    解题策略的谋划
     

    关于本站 | 合作伙伴 | 联系方式
    大榕树 版权所有 ©1999-2006 www.myDrs.org 闽ICP备05000721号