算法设计的基本方法实例

《算法设计的基本方法实例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计的基本方法实例算法设计的基本方法为用计算机解决实际问题而设计的算法，即是计算机算法。通常的算法设计有如下几种：（1）列举法列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或“有哪些可能”等问题。例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采用列举法进行解决。示例：百钱买百鸡公鸡3元每只，母鸡5元每只，小鸡1元3只，一百元钱买一百只鸡。请求出公鸡，母鸡和小鸡的数目。编程简析我们做最

2、极端的假设，公鸡可能是0-100，母鸡也可能是0-100，小鸡还可能是0-100，将这三种情况用循环套起来，那就是1000000种情况。这就是列举法。为了将题目再简化一下，我们还可以对上述题目进行一下优化处理：假设公鸡数为x,母鸡数为y，则小鸡数是100-x-y，也就有了下面的方程式：3*x+5*y+(100-x-y)/3=100从这个方程式中，我们不难看出大体的情况：公鸡最多有33只，最少是没有，即x的范围是0-33；母鸡最多20只，最少0只，即母鸡的范围是0-20；有了公鸡母鸡，小鸡数自然就是100-x

3、-y只。可能的方案一共有34*21种，在这么多的方案中，可能有一种或几种正好符合相等的条件。电脑怎样工作呢？计算机事实上就是将上述34*21种方案全部过滤一遍，找出符合百钱买百鸡条件的（也即上式），只要符合，这就是我们要的输出结果。这就是列举法，将可能的情况一网打尽；不过在应用过程中，我们最好还是做些优化，不然，要浪费好多没必要浪费的时间。使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。（2）归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一

4、般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。例如，使用归纳法在如下特殊的命题中：冰是冷的。在击打球杆的时候弹子球移动。推断出普遍的命题如：所有冰都是冷的，或：在太阳下没有冰。对于所有动作，都有相同和相反的重做动作。人们在归纳时往往加入自己的想法，而这恰恰帮助了人们的记忆。物理学研究方法之一。通过样本信息来推断总体信息的技术。要做出正确的归纳，就要从总体中选出的样本，这个样本必须足够大而且具有代表性。比如

5、在我们买葡萄的时候就用了归纳法，我们往往先尝一尝，如果都很甜，就归纳出所有的葡萄都很甜的，就放心的买上一大串。归纳推理也可称为归纳方法.完全归纳推理，也叫完全归纳法.不完全归纳推理，也叫不完全归纳法.归纳方法，还包括提高归纳前提对结论确证度的逻辑方法，即求因果五法，求概率方法，统计方法，收集和整理经验材料的方法等.（3）递推递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结

6、果。例如，裴波那契数列，是采用递推的方法解决问题的。1,1,2,3,5,8,13,21，。。。。。。。递推——猴子分食桃子五只猴子採得一堆桃子，猴子彼此約定隔天早起後再分食。不過，就在半夜裏，一隻猴子偷偷起來，把桃子均分成五堆後，發現還多一個，它吃掉這桃子，並拿走了其中一堆。第二隻猴子醒來，又把桃子均分成五堆後，還是多了一個，它也吃掉這個桃子，並拿走了其中一堆。第三隻，第四隻，第五隻猴子都依次如此分食桃子。那麼桃子數最少應該有几個呢？我們列方程求解：設原有桃子x個，第一隻猴子吃掉1個桃子，再拿走餘下桃子的五

7、分之一，剩下桃子数：第二隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：第三隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：第三隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：第四隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：最後一隻猴子也吃掉1個桃子，再拿走餘下桃子的五分之一﹔假設第五隻猴子拿走的桃子數是y個，則按題意可以列式得經過化簡、整理，得 256x－3125y=2101 ，其中12y+8是整數，所以是整數。因為53與256互質，因此y=255時可滿足要求。

8、這時x=3121。原來問題有無窮多解，上面求出的只是滿足條件的最小正整數解，也就是說最少有桃子3121個。以上是解不定元，此外，有一個巧思妙想的解法，：假若我們借來4個桃子，這樣桃子數就可以連續5次平均分成5堆了，所以桃子數最少應該是55－4=3121(個)。（4）递归在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而