可以用时间复杂度O(n)递归地计算Lucas数吗？
我有一个作业作业来计算卢卡斯的数字。如何使我的算法O(n)仍然保持递归？
这就是他给出的暗示：
当考虑到这个问题时，我想我会保留我的主for循环，并使它在计算出的一个数字之前存储这两个数字，但这将是迭代的。
这是我现在的代码：
lucas(n) {
return 2 if n = 0;
return 1 if n = 1;
return lucas(n - 1) + lucas(n - 2);
}
main(String args[]) {
for (int i = 0; i<=10; i++)
print(lucas(i*5));
}(代码的编写方式类似于抄袭行为。)
回答 3
Stack Overflow用户
发布于 2022-01-31 20:53:23
因为这是家庭作业，所以我不会将解决方案作为代码发布，但我希望我能够显示到它的路径。
给定的提示使用带有两个值的向量--在Java中，我们可以使用数组(因为方法不能只返回两个值)。该方法需要n的值。
int[] calc(int n) {
// TODO
}公式Gn = M X Gn-1 - M是给定的矩阵，Gn = [An , Bn] (An = Ln和Bn = Ln-1)我们可以重写为
[An , Bn] = [[1,1] [1,0]] X [An-1 , Bn-1]或
An = 1*An-1 + 1*Bn-1 = An-1 + Bn-1和
Bn = 1*An-1 + 0*Bn-1 = An-1
该方法将使用n-1调用自己，除非是n == 0，以获得[An-1,Bn-1]，然后使用上述公式计算输出数组[An,Bn]。
对于n=0，初始数组应该是[2,-1] (也就是提示中的G0 )。
(由于Gn只依赖于Gn-1，所以纯递归解决方案是O(n) --与通常计算卢卡斯数的方法不同，Ln依赖于Ln-1和Ln-2)
我完全忽略了第二个提示，并使用了上面的int[] -但是不要忘记考虑一个int是否能够表示L500
(有了这个提示就意味着它不会)
Stack Overflow用户
发布于 2022-01-31 20:11:01
我认为这个问题的记忆解将是O(n)，因为n的每个解只需计算一次。
“诀窍”是将lucas(n)的结果存储在映射中，以便在恒定时间O(1)中检索先前计算的结果，并计算一次新值。
(完全解决方案只需要在地图中值不存在的情况下计算)
public class MemoizedLucas {
private static Map<Integer, Integer> results = new HashMap<>();
/**
* @param args
*/
public static void main(String[] args) {
// add base cases to map
results.put(0, 2);
results.put(1, 1);
// compute lucas number
lucas(10);
System.out.println(results);
}
// The lucas function will be called at most 2*n times - O(2*n) is still considered liner time.
public static int lucas(int n) {
Integer result = results.get(n);
if (result != null) return result; // return value if in map
int a = lucas(n - 1);
int b = lucas (n - 2);
results.put(n , a + b);
return results.get(n);
}
}如果打印出来，这个程序输出的序列的前10个数字是：
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123
Stack Overflow用户
发布于 2022-01-31 20:24:00
提示是定义一个递归G函数，并接受G结果的两个Lucas值。lucas函数可以定义为对G的调用。
如你所见，G是O(N)。
int lucas(int n) { return g(n)[0]; }
int[] g(int n) { ... recursiveG ... }https://stackoverflow.com/questions/70931947
复制相似问题
腾讯云开发者
