如何在Java中优化这两个相互递归的函数？
如何在Java中优化这两个相互递归的函数？
提问于 2019-04-28 14:18:54
我必须编写方法，对这些相互递归的复合函数的输出进行求和并提供列表，但它们的执行总是与我当前的实现同步：
public static long fAnn(long n) {
if (n == 0) return 1;
else return n - fJohn(fAnn(n-1));
}
public static long fJohn(long n) {
if (n <= 0) return 0;
else return n - fAnn(fJohn(n-1));
}
public static List<Long> john(long n) {
List<Long> res = new ArrayList<Long>();
for (long i = 0; i < n; i++) {
res.add(fJohn(i));
}
return res;
}
public static long sumJohn(long n) {
long sum = 0;
for (long i = 0; i < n; i++) sum += fJohn(i);
return sum;
}
public static long sumAnn(long n) {
long sum = 0;
for (long i = 0; i < n; i++) sum += fAnn(i);
return sum;
}我考虑过将函数的最后一个值传递回函数，但我不太确定如何做到这一点。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-04-28 22:29:12
我采纳了@Tim北格莱森的建议，并决定学习更多关于动态编程的知识，以改进我对这个函数采用的天真递归方法，而不是首先在这里寻找答案。
下面是我想出的代码：
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Johnann {
private static Map<Long, Long> jMem;
private static Map<Long, Long> aMem;
public static long fAnn(long n) {
if (n < 2) {
aMem = new HashMap<Long, Long>();
aMem.put(n, (long)1);
return 1;
}
else if (aMem.keySet().contains(n)) {
return aMem.get(n);
}
else {
long res = n - fJohn(fAnn(n-1));
aMem.put(n, res);
return res;
}
}
public static long fJohn(long n) {
if (n < 2) {
jMem = new HashMap<Long, Long>();
jMem.put(n, (long)0);
return 0;
}
else if (jMem.keySet().contains(n)) {
return jMem.get(n);
}
else {
long res = n - fAnn(fJohn(n-1));
jMem.put(n, res);
return res;
}
}
public static List<Long> john(long n) {
List<Long> res = new ArrayList<Long>();
for (long i = 0; i < n; i++) {
res.add(fJohn(i));
}
return res;
}
public static List<Long> ann(long n) {
System.out.println(n);
List<Long> res = new ArrayList<Long>();
for (long i = 0; i < n; i++) {
res.add(fAnn(i));
}
return res;
}
public static long sumJohn(long n) {
if (n == 0) return 0;
else if (n < 2) return 1;
long sum = 0;
for (long i = 0; i < n; i++) sum += fJohn(i);
return sum;
}
public static long sumAnn(long n) {
if (n == 0) return 0;
else if (n < 2) return 1;
long sum = 0;
for (long i = 0; i < n; i++) sum += fAnn(i);
return sum;
}
}例如，我看到了使用ArrayList而不是映射的其他更好的实现：
import java.util.*;
public class Johnann {
private enum Person {JOHN, ANN}
private static List<Long> getListForName(Person person, long n) {
List<Long> ann = new ArrayList<>(Arrays.asList(1L));
List<Long> john = new ArrayList<>(Arrays.asList(0L));
for (int dayAnn = 1, dayJohn = 1; dayAnn < n || dayJohn < n; ) {
if (john.size() > ann.get(dayAnn - 1)) {
ann.add(dayAnn - john.get(Math.toIntExact(ann.get(dayAnn - 1))));
dayAnn++;
}
if (ann.size() > john.get(dayJohn - 1)) {
john.add(dayJohn - ann.get(Math.toIntExact(john.get(dayJohn - 1))));
dayJohn++;
}
}
return (person == Person.JOHN ? john : ann).subList(0, Math.toIntExact(n));
}
public static List<Long> john(long n) {
return getListForName(Person.JOHN, n);
}
public static List<Long> ann(long n) {
return getListForName(Person.ANN, n);
}
public static long sumJohn(long n) {
return john(n).stream().mapToLong(Long::longValue).sum();
}
public static long sumAnn(long n) {
return ann(n).stream().mapToLong(Long::longValue).sum();
}
}这可能要快得多，但我很高兴从这个问题中学到了很多关于动态编程和优化递归调用的知识。
Stack Overflow用户
发布于 2019-04-28 16:27:15
这个解决方案的问题是多次使用相同的参数执行方法。您可以使用名为回忆录的优化技术，而不是这样做。
维基百科：
在计算中，回忆化或回传是一种优化技术，主要用于通过存储昂贵函数调用的结果并在再次发生相同输入时返回缓存的结果来加速计算机程序。
实现可能如下所示。注意，这一次您需要创建一个类实例来使用这些方法，因为它们不再是静态的。
private Map<Long, Long> annCache = new HashMap<>();
private Map<Long, Long> johnCache = new HashMap<>();
long fAnn2(long n) {
return annCache.computeIfAbsent(n, x -> {
if (x == 0) return 1L;
else return x - fJohn2(fAnn2(x - 1));
});
}
long fJohn2(long n) {
return johnCache.computeIfAbsent(n, x -> {
if (x <= 0) return 0L;
else return x - fAnn2(fJohn2(x - 1));
});
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55891165
复制相关文章
相似问题
腾讯云开发者
