我正在学习数据结构和算法,这是一个我坚持的问题.
我必须通过将值存储到内存中来提高递归调用的性能.
但问题是非改进版本似乎比这更快.
有人可以帮我吗？
Syracuse数字是由以下规则定义的正整数序列：
syra(1)≡1
syra(n)≡nsyra(n / 2),如果n mod 2 == 0
syra(n)≡nsyra((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>();
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的维基百科文章.
另外,我认为你误用了计数器变量,你在第一次计算值时增加它(),但是当你在地图中找到一个值时,你会累积它(=).这对我来说似乎不对,我怀疑它是否给出了预期的结果.