如何在 Java 中的 GCD 函数中应用记忆？

Question

我必须计算许多数字对的gcd，所以为了优化我打算应用记忆我的职能。

一对class：

class Pair{
     private long a;
     private long b;
    
    Pair(long a,long b){
        this.a = a;
        this.b = b;
    }
}

我的哈希图（这是一个静态变量）

public static Map<Pair, Long> hashmap = new HashMap<>();

我的 gcd 函数：

public static long gcd(long a,long b) {
        
        if(hashmap.containsKey(new Pair(a,b))) {
            return hashmap.get(new Pair(a,b));
        }
        
        if(hashmap.containsKey(new Pair(b,a))) {
            return hashmap.get(new Pair(b,a));
        }
        
        if(a == 0) {
            return b;
        }
        
        long GCD = gcd(b%a,a);
        
        if(hashmap.containsKey(new Pair(a,b)) || hashmap.containsKey(new Pair(b,a))) {
            return GCD;
        }
        
        hashmap.put(new Pair(a,b),GCD);
        return GCD;
        
    }

但是，当我打印哈希映射的键和值时，它包含重复项。这意味着我的函数无法应用记忆，而是将对放入哈希图中。

Answer 1

我可以看到您的代码中需要进行一些更正。

您没有为 Pair class 定义 hashCode。您可以使用描述的方法 here 为一对 long 实现 hashCode。
您没有equals方法。你可以只写 this.a == other.a && this.b == other.b 作为相等的条件。 other 是 Pair.
的实例
这条语句：

if(hashmap.containsKey(new Pair(a,b)) || hashmap.containsKey(new Pair(b,a))) { return GCD; }

不需要。在调用递归 gcd
之前你已经检查过了
实际上，键是 Pair(a,b) 还是 Pair(b,a) 并不重要，equals 和 hashCode 应该 return 相同，因此您不需要不需要检查

if(hashmap.containsKey(new Pair(b,a))) { return hashmap.get(new Pair(b,a)); }

如何在 Java 中的 GCD 函数中应用记忆？

How to apply memoization in a GCD function in Java?

java

algorithm

memoization

dynamic-programming