给定一组长度为n的无序序列,将其存储在一维数组a[O..n-1]中。现采用如下方法找出其中的最大元素和最小元素:比较a[O]和a[n-1],若a[0]较大,则将二者的值进行交换;再比较a[1]和a[n-2],若a[1]较大,则交换二者的值;然后依次比较a[

admin2021-01-13  41

问题 给定一组长度为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个元素查找最大元素,从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是(64)。

选项 A、动态规划法
B、贪心法
C、分治法
D、回溯法

答案C

解析 本题考查算法设计基础知识。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,解题所需的计算时间往往也越少,从而也较容易处理。分治法的设计思想是:将一个难以直接解决的大问题分解成一些规模较小的相同问题,以便各个击破,分而治之。如果规模为n的问题可分解成k个子问题(1<k≤n),且这些子问题互相独立且与原问题相同。递归地求解这些问题,然后将各子问题的解合并得到原问题的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费指数级时间。动态规划算法,通常可按以下几个步骤进行:找出最优解的性质,并刻画其结构特征;递归地定义最优值;以自底向上的方式计算出最优值;根据计算最优值时得到的信息,构造一个最优解。回溯法有“通用的解题法”之称,用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。贪心法是一种不追求最优解,只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪心法不要回溯。
转载请注明原文地址:https://kaotiyun.com/show/wkCZ777K
0

相关试题推荐
最新回复(0)