算法设计的基本方法实例.doc

算法设计的基本方法实例算法设计的基本方法 为用计算机解决实际问题而设计的算法，即是计算机算法。通常的算法设计有如下几种：（1）列举法列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或“有哪些可能”等问题。例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采用列举法进行解决。示例：百钱买百鸡公鸡3元每只，母鸡5元每只，小鸡1元3只，一百元钱买一百只鸡。请求出公鸡，母鸡和小鸡的数目。编程简析我们做最极端的假设，公鸡可能是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-y只。可能的方案一共有34*21种，在这么多的方案中，可能有一种或几种正好符合相等的条件。电脑怎样工作呢？计算机事实上就是将上述34*21种方案全部过滤一遍，找出符合百钱买百鸡条件的（也即上式），只要符合，这就是我们要的输出结果。这就是列举法，将可能的情况一网打尽；不过在应用过程中，我们最好还是做些优化，不然，要浪费好多没必要浪费的时间。使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。（2）归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。例如，使用归纳法在如下特殊的命题中：冰是冷的。在击打球杆的时候弹子球移动。推断出普遍的命题如：所有冰都是冷的，或： 在太阳下没有冰。对于所有动作，都有相同和相反的重做动作。人们在归纳时往往加入自己的想法，而这恰恰帮助了人们的记忆。物理学研究方法之一。通过样本信息来推断总体信息的技术。要做出正确的归纳，就要从总体中选出的样本，这个样本必须足够大而且具有代表性。比如在我们买葡萄的时候就用了归纳法，我们往往先尝一尝，如果都很甜，就归纳出所有的葡萄都很甜的，就放心的买上一大串。归纳推理也可称为归纳方法.完全归纳推理，也叫完全归纳法.不完全归纳推理，也叫不完全归纳法.归纳方法，还包括提高归纳前提对结论确证度的逻辑方法，即求因果五法，求概率方法，统计方法，收集和整理经验材料的方法等.（3）递推递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结果。例如，裴波那契数列，是采用递推的方法解决问题的。 1,1,2,3,5,8,13,21，。递推猴子分食桃子五只猴子採得一堆桃子，猴子彼此約定隔天早起後再分食。不過，就在半夜裏，一隻猴子偷偷起來，把桃子均分成五堆後，發現還多一個，它吃掉這桃子，並拿走了其中一堆。第二隻猴子醒來，又把桃子均分成五堆後，還是多了一個，它也吃掉這個桃子，並拿走了其中一堆。第三隻，第四隻，第五隻猴子都依次如此分食桃子。那麼桃子數最少應該有几個呢？我們列方程求解：設原有桃子x個，第一隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：第二隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：第三隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数：第三隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数： 第四隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子数： 最後一隻猴子也吃掉1個桃子，再拿走餘下桃子的五分之一假設第五隻猴子拿走的桃子數是y個，則按題意可以列式得 經過化簡、整理，得 256x3125y=2101 ，其中 12y+8 是整數，所以 是整數。因為53與256互質，因此 y=255 時可滿足要求。這時 x = 3121。原來問題有無窮多解，上面求出的只是滿足條件的最小正整數解，也就是說最少有桃子3121個。以上是解不定元，此外，有一個巧思妙想的解法，：假若我們借來4個桃子，這樣桃子數就可以連續5次平均分成5堆了，所以桃子數最少應該是554=3121(個)。（4）递归在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。题目：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3 3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后4问第一个人，他说是10岁。请问第五个人多大？56 1.程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道7 第四人的岁数，依次类推，推到第一人（10岁），再往回推。8 */9 #include1011 int age(int n)12 13 int c;1415 if(n=1)16 return 10;1718 else19 20 c = age(n-1)+2;21 return c;22 23 2425 int main()26 27 /int i;2829 printf(his age is :%dn,age(5);3031 /for(i=1;i6;i+)32 /printf(the %d man is :%dn,i,age(i);3334 return 0;35 （5）减半递推技术减半递推即将问题的规模减半，然后，重复相同的递推操作。例如，一元二次方程的求解。（6）回溯法有些实际的问题很难归纳出一组简单的递推公