算法教学问题的探讨
来源:用户上传
作者:石少俭 徐乙富
摘要：算法是计算机程序员必备的技术之一。大学的计算机算法课一般讲授经典的算法，主要是分治算法、动态规划算法、贪心算法等。算法就是解决问题的方法。
关键词：算法;分治算法;动态规划算法;贪心算法
中图分类号：TP319 文献标识码：A
文章编号：1009-3044（2019）27-0164-02
1引言
算法，晦涩难懂，却又是IT领域最受重视的素养之一。可以说，算法能力往往决定了一个程序员能够走多远。国内外各大名企非常喜欢在面试环节考核求职者的算法编程，这也成为无数准程序员们过不去的一道“坎”。
大学的计算机算法课一般讲授经典的算法，主要是分治算法、动态规划算法、贪心算法等。对算法的定义，一般都是给出了计算机算法的特性，但作为算法的定义不太合适。可以用算法就是解决问题的方法作为算法的定义。下面通过几个例子来解释这个定义。
2算法的一般问题
1）分苹果问题：有n个苹果，两个人分。规定：两人依次取，每次最多取1～m个，最后取到苹果者获胜，给出具体的获胜策略。
这是一个运筹学方面的例子。解题思路：从最后结果向前倒推。具体实例n=10，m=3。
一个人如果想获胜，倒数第二次取后，需要给对方剩4个苹果。以此倒推，结论是先取者获胜。一般的情况下结论是整除问题。设n=a（m+1）+b，a是偶数，b=O后取者获胜Ib≠0，先取者获胜。a是奇数，b=0后取者获胜Ib≠0，先取者获胜。算法就是给出了解题的方法。
2）已知A={1，2，3，4，5，6，7，8，9，10}，求A的所有子集的元素之和。
3分治法的问题
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
已知有n个硬币，其中有可能有一个是伪造的，并且已知伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。问题1：用最少次数确定是否存在伪币？问题2：如存在伪币，用最少次数确定之。
解题思路：用分治法的思路。
问题1确定是否存在伪币：n为偶数，把硬币分成数量相等的2份，用仪器一次即可确定是否存在伪币;n为奇数，把n-1个硬币分成数量相等的2份，用仪器一次即可确定是否存在伪币。如果存在伪币，则结束，如果不确定，从这n-1个硬币中取一个与原来剩余的1个硬币，用仪器一次即可确定是否存在伪币。所以问题1至多2次即可确定是否存在伪币。
问题2存在伪币：把2个硬币的情况作为可解决的小问题，在一个小问题中，只用1次即可确定伪币，总的比较次数为log2n。实际上這个问题中，可以通过1次比较确定伪币的个数可以是3个，所以，最少的比较次数为log3n。
4动态规划算法的问题
动态规划算法基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划算法的重点是找到求解问题个子问题的递归方程。
背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。1.物品允许拆分;2.物品不允许拆分。问应如何选择背包中物品的总价值最大？
5贪心算法的例子
顾名思义，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的，如果不是整体最优的，说明这个问题不适合用贪心算法来解决。
最优合并问题：给定k个排好序的序列s1，s2，……，sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。对于给定的k个待合并序列，计算最多比较次数和最少比较次数。
解题思路：用贪心算法解题，贪心策略：最少比较次数和最多比较次数分别为每次选最小（大）的序列合并，2个长度分别为m和n的序列需要m+n-1次比较。对于问题的一个实例，4个排好序的序列4，5，11，12的最多比较次数和最少比较次数分别为：
最多比较次数=（12+11-1）+（（12+11）+5-1）+（（（12+11+5）+4-1）=80
最少比较次数=（4+5-1）+（（4+5）+11-1）+（（4+5）+11）+12-1）=58
6总结
给出某高校计算机研究生初试一道题。顺序表中共存放n个整数。设计一个算法调整这些整数在顺序表中的位置，使得原表中所有能够被5整除的整数放在表的后半段，其他的整数放在表的前半段。要求用尽量少的时间与空间，并给出算法的时间复杂度和空间复杂度。
解题思路：该题只是要求所有能够被5整除的整数放在表的后半段，其他的整数放在表的前半段，没要求整数需要保持原来的顺序。可以用快速排序的思想来解决。设两个指针，一个指针从表头开始向后扫描，找到第一个能够被5整除的整数;一个指针从表尾开始向前扫描，找到第一个不能被5整除的整数。两个指针对应的整数对调。然后两个指针继续扫描，直到都扫描到一个整数为止。此算法的时间复杂度为0（n）和空间复杂度0（1）。
通过上面的讨论，可以对算法的概念更加明确，加深学生对算法的理解，提高了学生学习算法积极性。
转载注明来源:https://www.xzbu.com/8/view-15040400.htm
