单项选择题

​已知斐波那契数列中第n个斐波那契数F（n）=F（n-1）+F（n-2），问能不能使用分治策略求第n个斐波那契数（）。

A.不能，因为它不可以用分、治、合三个步骤完成计算
B.不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）
C.能，因为它满足分治法的四个适应条件
D.能，因为它可以用分、治、合三个步骤完成计算

<上一题 目录 下一题>
热门 试题

单项选择题
分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T（n）的一个递归方程，然后解此方程可得T（n）的结果。T（n）的递归定义如下：关于该定义中k，n m，f（n）的解释准确的是（）。

A.k是常系数，n/m是规模为n的问题分为m个子问题，f（n）是将子问题的解合并为问题的解的时间复杂性
B.k是子问题个数，n/m是子问题的规模，f（n）是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和
C.k是子问题个数，n/m是子问题的规模，f（n）是规模为n的问题分解为子问题的时间复杂性
D.k是常系数；n/m是规模为n的问题分为m个子问题；f（n）是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和
单项选择题
‎分治法解决问题分为三步走，即分、治、合。下面列出了几种操作，请按分、治、合顺序选择正确的表述（）。（1）将各个子问题的解合并为原问题的解（2）将问题分解为各自独立的多个子问题（3）将多个子问题合并为原问题（4）求各个子问题的解（5）将问题分解为可重复的多个子问题

A.（2）（4）（1）
B.（2）（1）（3）
C.（5）（4）（1）
D.（5）（1）（3）
相关试题