国家集训队2000论文集 张力论文

《国家集训队2000论文集 张力论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、作者：张力1999.12.5类比思想在解题中的应用第13页共13页类比思想在解题中的应用【关键字】思想；类比；相似性；对应。【摘要】：类比，是一种试图建立未知的问题与已知的问题之间的联系，从而利用已知的解题方法去解决新的问题的思路。本文首先通过分析具体的例子，指出类比解题不仅仅是注意到了表面上的相似性，更是建立了已知问题和未知问题之间的对应关系。然后，本文将通过另一个例子，论述表面相似性与内在的对应之间的关系，并且指出利用类比解题的过程是从表面相似性上升到一一对应的过程。引：解题，从熟悉的地方开始面对一

2、个新的问题应该如何着手去分析解决呢？从熟悉的地方开始着手。这是生活中人们常常采用的方法：希望面对的难题与以前解决过的某个问题是相同的，或者至少类似的；由此就可以获得值得借鉴的经验。面对一个陌生的问题，试图把它和某个熟悉的问题联系起来，借助熟悉的知识和熟悉的方法来解决新问题，是自然的想法。这种寻找未知问题和已知问题之间联系的思想，可以称为类比。更确切的说，“如果两个系统的各自的各部分之间，存在某种一致的关系的话，则称两个系统是可以类比的。Page:1”引自参考书目i（《数学与猜想》）第二章。如何理解定义中

3、所说的“一致的关系”呢？如果只简单的把“存在某种一致的关系”理解成一种含糊的相似性。那么类比就完全归结为人的主观的感觉，这种主观上的“似曾相识”是不能够作为分析问题、解决问题的依据的。然而类比的思想的确被广泛的应用于解决各种问题，说明类比的本质是另一种比表面上的相似性更可靠和更有说服力的“一致关系”。事实上，类比是建立在两个问题之间的一种一一对应的映射关系。本文的第一部分，正是试图阐述这一本质上的“一致关系”。作者：张力1999.12.5类比思想在解题中的应用第13页共13页然而两个问题之间的本质联系并

4、不是那么容易得到的。人们在对问题的最初的分析中，注意到的往往还是表面上（甚至只是文字上）的相似性。希望直接得到两个问题之间相互对应和相互转化的关系是不现实的。因此，最初观察到的表面上的相似性虽然有些不可靠，但是至少它能够为分析问题指出方向，由此尝试着建立问题之间的对应关系。正如本文第二部分将要阐述的，利用类比解题的过程是从模糊到清晰，从表面到本质的分析过程。接下来的两个部分，就将探讨类比过程中，表面的相似和本质的对应之间的关系。类比的本质，一一对应的关系类比作为一种分析问题的思想方法，目的是希望将不熟悉

5、的知识转化为熟悉的知识，将未知的问题转化为已知的问题。如何实现这一转化，取决于如何对两个问题进行类比。如果仅考虑到两个问题表面上的相似性，那么很可能会机械的模仿已知问题的解决方法，来解决新问题。这种想法缺乏严谨可靠的支持，难以保证在实际解题中能够成功。即使成功了，也是知其然而不知其所以然，没有发现问题之间本质的联系，往往得不到最好的解决方法。而当类比过程中两个问题之间存在一种对应关系，未知问题中的所有描述对象和操作，在已知问题中都有与之一一对应的内容，那么整个未知的问题就可以通过这种一一对应的映射关系，

6、转化为已知的问题，也就可以应用已知问题的解决方法来解决它。下面的例子就是如此。【“整数拆分”与“因数分解”】整数拆分：将一个正整数n，拆分为一组小于n的正整数的和（不考虑这组正整数排列的先后次序）。求总共有多少组可能的拆分。问题来自参考书目ii（《算法设计》）4.2.4。这是一道众所周知的组合计数问题。解决的方法有两种：①利用递归的枚举解题模型。(对应程序名DIVIDE1.PAS)将问题描述为：求满足等式的所有正整数组（a1，a2，a3，a4……，am）的总数。为此，可以采用递归枚举的方法逐个确定每一个

7、ai从而求出所有的解，并统计总数。设D(k,n)为将n拆分成一组不小于k的正整数的和的解的数目。例如，a1可以选取1…[n/2]之间的任意整数，剩下的n-a1可以拆分成不小于a1的若干个整数的和。于是对于a1，有；而对a2，有作者：张力1999.12.5类比思想在解题中的应用第13页共13页由此不难得出问题的递归求解式;问题的解等价于(减一以除去n=n的拆分方案)。由于原问题只要给出解的总数，而这一算法在计算过程中求出了所有的解，所以枚举算法的效率在n较大的时候是很低的。①母函数解题模型。(对应程序名D

8、IVIDE2.PAS)设拆分的这组正整数中1出现的次数为x1，2出现的次数为x2，等等，那么问题可以描述为：求不定方程的整数解的总数。于是就可以利用构造母函数，来求不定方程的整数解的个数。方法如下：利用母函数计算不定方程整数解的总数的一般方法，请参见参考书目iii（《组合数学及其在计算机科学中的应用》）。拆分中不选取1可以表示为x0=1，取一个1表示为x，取两个1为x*x=x2，取k个1为xk。由加法原理得到选取1的所有方案为；不选取2可以