我正在学习数据结构和算法，这是我要坚持的一个问题。
我必须通过将值存储到内存中来提高递归调用的性能。
但是问题在于，未经改进的版本似乎比这要快。
有人可以帮我吗？
锡拉库扎数字是由以下规则定义的正整数序列:
syra(1)≡1
syra(n)≡n + syra(n/2)，如果n mod 2 == 0
syra(n)≡n + syra((n * 3)+1)，否则
import java.util.HashMap;
import java.util.Map;
public class SyraLengthsEfficient {
int counter = 0;
public int syraLength(long n) {
if (n < 1) {
throw new IllegalArgumentException();
}
if (n < 500 && map.containsKey(n)) {
counter += map.get(n);
return map.get(n);
} else if (n == 1) {
counter++;
return 1;
} else if (n % 2 == 0) {
counter++;
return syraLength(n / 2);
} else {
counter++;
return syraLength(n * 3 + 1);
}
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public int lengths(int n) {
if (n < 1) {
throw new IllegalArgumentException();
}
for (int i = 1; i <= n; i++) {
syraLength(i);
if (i < 500 && !map.containsKey(i)) {
map.put(i, counter);
}
}
return counter;
}
public static void main(String[] args) {
System.out.println(new SyraLengthsEfficient().lengths(5000000));
}
}
这是我写的普通版本:
public class SyraLengths{
int total=1;
public int syraLength(long n) {
if (n < 1)
throw new IllegalArgumentException();
if (n == 1) {
int temp=total;
total=1;
return temp;
}
else if (n % 2 == 0) {
total++;
return syraLength(n / 2);
}
else {
total++;
return syraLength(n * 3 + 1);
}
}
public int lengths(int n){
if(n<1){
throw new IllegalArgumentException();
}
int total=0;
for(int i=1;i<=n;i++){
total+=syraLength(i);
}
return total;
}
public static void main(String[] args){
System.out.println(new SyraLengths().lengths(5000000));
}
}
编辑
它比非增强版本慢。
import java.util.HashMap;
import java.util.Map;
public class SyraLengthsEfficient {
private Map<Long, Long> map = new HashMap<Long, Long>();
public long syraLength(long n, long count) {
if (n < 1)
throw new IllegalArgumentException();
if (!map.containsKey(n)) {
if (n == 1) {
count++;
map.put(n, count);
} else if (n % 2 == 0) {
count++;
map.put(n, count + syraLength(n / 2, 0));
} else {
count++;
map.put(n, count + syraLength(3 * n + 1, 0));
}
}
return map.get(n);
}
public int lengths(int n) {
if (n < 1) {
throw new IllegalArgumentException();
}
int total = 0;
for (int i = 1; i <= n; i++) {
// long temp = syraLength(i, 0);
// System.out.println(i + " : " + temp);
total += syraLength(i, 0);
}
return total;
}
public static void main(String[] args) {
System.out.println(new SyraLengthsEfficient().lengths(50000000));
}
}
最终解决方案(学校自动评分系统将其标记为正确)
public class SyraLengthsEfficient {
private int[] values = new int[10 * 1024 * 1024];
public int syraLength(long n, int count) {
if (n <= values.length && values[(int) (n - 1)] != 0) {
return count + values[(int) (n - 1)];
} else if (n == 1) {
count++;
values[(int) (n - 1)] = 1;
return count;
} else if (n % 2 == 0) {
count++;
if (n <= values.length) {
values[(int) (n - 1)] = count + syraLength(n / 2, 0);
return values[(int) (n - 1)];
} else {
return count + syraLength(n / 2, 0);
}
} else {
count++;
if (n <= values.length) {
values[(int) (n - 1)] = count + syraLength(n * 3 + 1, 0);
return values[(int) (n - 1)];
} else {
return count + syraLength(n * 3 + 1, 0);
}
}
}
public int lengths(int n) {
if (n < 1) {
throw new IllegalArgumentException();
}
int total = 0;
for (int i = 1; i <= n; i++) {
total += syraLength(i, 0);
}
return total;
}
public static void main(String[] args) {
SyraLengthsEfficient s = new SyraLengthsEfficient();
System.out.println(s.lengths(50000000));
}
}
最佳答案
忘记那些说由于使用Map而导致代码效率低下的答案，这不是它运行缓慢的原因-这是您将计算所得的数字缓存限制为n < 500的事实。取消该限制后，一切就会开始快速运行。这是一个概念证明供您填写详细信息:
private Map<Long, Long> map = new HashMap<Long, Long>();
public long syraLength(long n) {
if (!map.containsKey(n)) {
if (n == 1)
map.put(n, 1L);
else if (n % 2 == 0)
map.put(n, n + syraLength(n/2));
else
map.put(n, n + syraLength(3*n+1));
}
return map.get(n);
}
如果您想了解有关程序中发生的一切以及为什么这么快的更多信息，请看一下有关Memoization的维基百科文章。
另外，我认为您正在滥用
counter变量，在首次计算值时将其递增(++)，但是在 map 中找到值时会对其进行累加(+=)。这对我来说似乎不正确，我怀疑它能否达到预期的结果。