给定一组长度为n无序序列，将其存储在一维数组a[O．n-1]中。现采用如下方法找出其中最大元素和最小元素：比较a[O]和a[n-1]，若a[0]较大，则将二者值进行交换；再比较a[1]和a[n-2]，若a[1]较大，则交换二者值；然后依次比较a[2]和a[n-3]、 a[3]和a[n-4]、…，使得每一对元素中较小者被交换到低下标端。重复上述方法，在数组前n/2个元素中查找最小元素，在后n/2个元素查找最大元素，从而得到整个序列最小元素和最大元素。上述方法采用算法设计策略是 ( ) 。
- A.动态规划法
- B.贪心法
- C.分治法
- D.回溯法
正确答案及解析
正确答案
解析
本题考查算法设计基础知识。任何一个可以用计算机求解问题所需计算时间都与其规模有关。问题规模越小，解题所需计算时间往往也越少，从而也较容易处理。分治法设计思想是：将一个难以直接解决大问题分解成一些规模较小相同问题，以便各个击破，分而治之。如果规模为n问题可分解成k个子问题(1大于k≤n)，且这些子问题互相独立且与原问题相同。递归地求解这些问题，然后将各子问题解合并得到原问题解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题解得到原问题解。与分治法不同是，适合于用动态规划法求解问题，经分解得到子问题往往不是独立。若用分治法来解这类问题，则分解得到子问题数目太多，以至于最后解决原问题需要耗费指数级时间。动态规划算法，通常可按以下几个步骤进行：找出最优解性质，并刻画其结构特征；递归地定义最优值；以自底向上方式计算出最优值；根据计算最优值时得到信息，构造一个最优解。回溯法有“通用解题法”之称，用它可以系统地搜索一个问题所有解或任一解。回溯法是一个既带有系统性又带有跳跃性搜索算法。它在包含问题所有解解空间树中，按照深度优先策略，从根结点出发搜索解空间树。贪心法是一种不追求最优解，只希望得到较为满意解方法。贪心法一般可以快速得到满意解，因为它省去了为找最优解要穷尽所有可能而必须耗费大量时间。贪心法常以当前情况为基础作最优选择，而不考虑各种可能整体情况，所以贪心法不要回溯。
