同一个问题，其动态规划算法的效率一定比分治设计的算法高

题目

同一个问题，其动态规划算法的效率一定比分治设计的算法高

相似考题

1.矩阵连乘问题的算法可由什么设计实现()A.分支界限算法B.动态规划算法C.贪心算法D.回溯算法

2.问题的最优子结构性质是该问题不可用动态规划算法或贪心算法求解的关键特征。()此题为判断题(对，错)。

3.以下的算法设计方法中，( )以获取问题最优解为目标。A．回溯方法B．分治法C．动态规划D．递推

4.●若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用 (26) 算法，因为 (27) 。(26) A．先递归后递推B．先递推后递归C．递归D．递推(27) A．递推的效率比递归高B．递归宜于问题分解C．递归的效率比递推高

更多“同一个问题，其动态规划算法的效率一定比分治设计的算法高”相关问题

  • 第1题：

    分治法也许是使用最广泛的算法设计方法，以下关于分治法的结论中正确的是(54)。

    A．分治法能解决动态规划方法所能解决的任何问题

    B．分治法找到的问题的解一定是最优解

    C．用分治法能求出任何问题的解

    D．分治法只能把大问题简单分解成一些较小的问题


    正确答案：D
    解析：分治法(DivideandConquer)是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解决这些子问题，然后把各子问题的解合并得到原问题的解。ABC选项中的“任何”、“一定”词汇违反常识，从逻辑上可判明其错误。

  • 第2题：

    关于动态规划的描述，不正确的是（ ）。

    A.动态规划是解决多阶段决策过程最优化解的一种常用算法思想
    B.动态规划的实质是分治思想和解决冗余，与分治法和回溯法类似
    C.在处理离散型问题时，动态规划比线性规划效果更好
    D.一个保准的动态规划算法包括划分阶段和选择状态两个步骤

    答案：B
    解析：
    动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而比喵计算重复的子问题，以解决最优化问题的算法策略。于分治法和回溯发类似是错误的。

  • 第3题：

    蜗牛爬井问题不属于（）类型算法解决的问题。

    • A、迭代问题
    • B、递归问题
    • C、分治问题
    • D、穷举问题

    正确答案:B,C,D

  • 第4题：

    分治算法设计技术（）

    • A、一般由三个步骤组成：问题划分、递归求解、合并解
    • B、一定是用递归技术来实现
    • C、将问题划分为k个规模相等的子问题
    • D、划分代价很小而合并代价很大

    正确答案:A

  • 第5题：

    某一问题可用动态规划算法求解的显著特征是（）。


    正确答案:该问题具有最优子结构性质

  • 第6题：

    矩阵连乘问题的算法可由（）设计实现。

    • A、分支界限算法
    • B、动态规划算法
    • C、贪心算法
    • D、回溯算法

    正确答案:B

  • 第7题：

    动态规划算法有一个变形方法（）。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。


    正确答案:备忘录方法

  • 第8题：

    应用Johnson法则的流水作业调度采用的算法是（）

    • A、贪心算法
    • B、分支限界法
    • C、分治法
    • D、动态规划算法

    正确答案:D

  • 第9题：

    问答题
    写出设计动态规划算法的主要步骤。

    正确答案： ①问题具有最优子结构性质；
    ②构造最优值的递归关系表达式；
    ③最优值的算法描述；
    ④构造最优解；
    解析： 暂无解析

  • 第10题：

    单选题
    若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用__（1）__算法，因为__（2）__。空白（2）处应选择（）
    A

    递推的效率比递归高

    B

    递归宜于问题分解

    C

    递归的效率比递推高

    D

    递推宜于问题分解


    正确答案： B
    解析： 暂无解析

  • 第11题：

    单选题
    应用Johnson法则的流水作业调度采用的算法是（）
    A

    贪心算法

    B

    分支限界法

    C

    分治法

    D

    动态规划算法


    正确答案： D
    解析： 暂无解析

  • 第12题：

    填空题
    0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。

    正确答案： O(n*2n),O(min{nc,2n})
    解析： 暂无解析

  • 第13题：

    ●分治算法设计技术 (63)。

    (63)

    A．一般由三个步骤组成：问题划分、递归求解、合并解

    B．一定是用递归技术来实现

    C．将问题划分为k个规模相等的子问题

    D．划分代价很小而合并代价很大


    正确答案：A

  • 第14题：

    0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。


    正确答案: O(n*2n)；O(min{nc,2n})

  • 第15题：

    请叙述动态规划算法与贪心算法的异同。


    正确答案: 共同点：
    都需要最优子结构性质，
    都用来求有优化问题。
    不同点：
    动态规划：每一步作一个选择—依赖于子问题的解。
    贪心方法：每一步作一个选择—不依赖于子问题的解。
    动态规划方法的条件：子问题的重叠性质。
    可用贪心方法的条件：最优子结构性质；贪心选择性质。
    动态规划：自底向上求解；
    贪心方法：自顶向下求解。
    可用贪心法时，动态规划方法可能不适用；
    可用动态规划方法时，贪心法可能不适用。

  • 第16题：

    对于同一个问题可采用不同的算法去解决，但不同的算法通常具有相同的效率。


    正确答案:错误

  • 第17题：

    问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。


    正确答案:最优子结构性质

  • 第18题：

    一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。

    • A、重叠子问题
    • B、最优子结构性质
    • C、贪心选择性质
    • D、定义最优解

    正确答案:B

  • 第19题：

    写出设计动态规划算法的主要步骤。


    正确答案: ①问题具有最优子结构性质；
    ②构造最优值的递归关系表达式；
    ③最优值的算法描述；
    ④构造最优解；

  • 第20题：

    填空题
    问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。

    正确答案： 最优子结构性质
    解析： 暂无解析

  • 第21题：

    填空题
    某一问题可用动态规划算法求解的显著特征是（）。

    正确答案： 该问题具有最优子结构性质
    解析： 暂无解析

  • 第22题：

    判断题
    对于同一个问题可采用不同的算法去解决，但不同的算法通常具有相同的效率。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第23题：

    单选题
    矩阵连乘问题的算法可由（）设计实现。
    A

    分支界限算法

    B

    动态规划算法

    C

    贪心算法

    D

    回溯算法


    正确答案： A
    解析： 暂无解析

  • 第24题：

    单选题
    分治算法设计技术（）
    A

    一般由三个步骤组成：问题划分、递归求解、合并解

    B

    一定是用递归技术来实现

    C

    将问题划分为k个规模相等的子问题

    D

    划分代价很小而合并代价很大


    正确答案： D
    解析： 分治算法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。分治算法产生的子问题往往是原问题的较小模式。一般来说，分治算法分为三个步骤：将原问题分解成一系列子问题；递归求解各个子问题；将子问题的解合并成原问题的解。

相关内容