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

算法设计的基本方法实例算法设计的基本方法为用计算机解决实际问题而设计的算法，即是计算机算法 通常的算法设计有如下几种：(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 個，則按題意可以列式得256經過化簡、整理，得 256x－3125y=2101 ，其中 12y+8 是整53（y+l）數，所以 是整數。

因為53與256互質，因此y=255時可滿足要求這時x = 3121原來問題有無窮多解，上面求出的 只是滿足條件的最小正整數解，也就是說最少有桃子 3121 個以上是解不定元，此外，有一個巧思妙想的解法，：假若我 們借來 4 個桃子，這樣桃子數就可以連續 5 次平均分成 5 堆了 所以桃子數最少應該是 55－4=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 {13int c;1415if(n==1)16return 10;1718else19{20c = age(n-1)+2;21return c;22}23 }2425 int main()26 {27//int i;2829printf("his age is :%d\n",age(5));3031//for(i=1;i<6;i++)32//printf("the %d man is :%d\n",i,age(i));3334return 0;35 }5）减半递推技术 减半递推即将问题的规模减半，然后，重复相同的递推操作例如，一元二次方程的求解6）回溯法有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用 无限的列举对于这类问题，只能采用试探的方法，通过对问题的分析，找出解 决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解， 如果不成功，再逐步回退，换别的路线进行试探这种方法，即称为回溯法。

如人工智能中的机器人下棋（八皇后问题）。