算法设计的基本方法实例

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

2、，将这三种情况用循环套起来，那就 是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-y只。可能的方案一共有34*21种，在这么多的方案中， 可能有一种或几种正好符合相等的条件。电脑怎样工作呢？计算机事实上就是将上述34*21种方案 全部过滤一

3、遍，找出符合百钱买百鸡条件的（也即上式），只要 符合，这就是我们要的输出结果。这就是列举法，将可能的情况一网打尽；不过在应用过程中， 我们最好还是做些优化，不然，要浪费好多没必要浪费的时间。使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、 系统化，从中找出规律。（2）归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关 系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能 对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证 明。例如，使用归纳法在如下特殊的命题中：冰是冷的。在击打球杆的时候弹子球移动。推断出普

4、遍的命题如：所有冰都是冷的，或：在太阳下没有冰。对于所有动作，都有相同和相反的重做动作。人们在归纳时往往加入自己的想法，而这恰恰帮助了人们的记忆。物理学研究方法之一。通过样本信息来推断总体信息的技术。要做出正确的归纳， 就要从总体中选出的样本，这个样本必须足够大而且具有代表性。比如在我们买葡萄的时候就用了归纳法，我们往往先尝一尝，如果都很甜， 就归纳出所有的葡萄都很甜的，就放心的买上一大串。归纳推理也可称为归纳方法.完全归纳推理，也叫完全归纳法.不完全归纳推理， 也叫不完全归纳法.归纳方法，还包括提高归纳前提对结论确证度的逻辑方法， 即求因果五法，求概率方法，统计方法，收集和整理经验材料的方法

5、等.递推递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。 其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结果。例如，裴波那契数列，是采用递推的方法解决问题的。1,1,2,3,5,8,13,21，。递推一猴子分食桃子五只猴子探得一堆桃子，猴子彼此青勺定隔天早起彳度再分食。 不遏，就在半夜裹，一蔓猴子偷偷起来，把桃子均分成五堆彳度， 畿现遢多一彳固，它吃掉逼桃子，业拿走了其中一堆。第二蔓猴子 醒来，又把桃子均分成五堆彳度，遢是多了一固，它也吃掉逼固桃 子，业拿走了其中一堆。第三蔓，第四蔓，第五蔓猴子都依次如

6、此分食桃子。那麽桃子敷最少雁言亥有几固呢？我仍列方程求解：言殳原有桃子x固，第一蔓猴子吃掉1固桃子，再拿走食余下桃子的五分之一，剩 下桃子数：第二蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩下桃子数：第三蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩下桃子数:第三蔓猴子吃掉1彳固桃子，再拿走食余下桃子的五分之一，剩 下桃子数:第四蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩 下桃子数:最彳菱一蔓猴子也吃掉1固桃子，再拿走余下桃子的五分之一 ；假言殳第五蔓猴子拿走的桃子敷是y固，则按题意可以列式得*保45-州+蜓化筒、整理，得256x_3125y + 2101 招，5沦 + 1卜312

7、5y=2101， 瓦 12y其中 12y+8 是整53(y+l)敷，所以二k是整敷。因舄53舆256互，因此y=255日寺 可满足要求。逼日寺x = 3121。原来冏题有照穿多解，上面求出的 只是满足倏件的最小正整敷解，也就是最少有桃子3121固。以上是解不定元，此外，有一固巧思妙想的解法，：假若我 仍借来4固桃子，逼檬桃子敷就可以速 5次平均分成5堆了， 所以桃子敷最少雁言亥是554=3121(固)。递归在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最 后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求 解，而只是当解决了最后的问题那些最简单的问题后

8、，再沿着原来分解的逆过程 逐步进行综合，这就是递归的方法。递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接 递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种 递归称为间接递归调用。题目：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数， 他说比第33个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后4问第一个人，他说是10岁。请问第五个人多大？ 51.程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数， 需知道第四人的岁数，依次类推，推到第一人(10岁)，再往回推。*/#include10int age(int n)int c;14if(n=1)return 10;17else TOC o 1-5 h z c = age(n-1)+2;return c;24int main()/int i;2829 printf(his age is :%dn,age(5);30/for(i=1;i6;i+)/printf(the %d man is :%dn,i,age(i);33return 0;（5）减半递推技术 减半递推即将问题的规模减半，然后，重复相同的递推操作。例如，一元二次方程的求解。（6）回溯法有些实际的问题很难归纳出一组简单的递推公式