单项选择题

已知斐波那契数列中第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）

多项选择题

‌关于算法的正确性，下面哪些说法是正确的？（）

A.对于问题的一个实例，如果算法不能获得正确的结果，就证明算法是不正确的
B.若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果
C.对于问题的一个实例，如果算法能够获得正确的结果，就证明算法是正确的
D.若算法是正确的，则算法一定能结束（运行时间是有限的）

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

相关考题

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