我正在编写一个简单的程序,内容如下:给定两个数M和N,p范围在[M,N]之间,q范围在[1,p-1]之间,找到p/q的所有不可约分数。
我的想法是用暴力方法枚举p,q的所有可能值。并使用HashSet来避免重复的分数。但是,一些情况下contains函数无法按照预期工作。
我的代码如下:
你可以看到分数2/1被重复了。有人能帮我解决这个问题并告诉我如何修复吗?非常感谢。
我的代码如下:
import java.util.HashSet;
import java.util.Set;
public class Fraction {
private int p;
private int q;
Fraction(int p, int q) {
this.p = p;
this.q = q;
}
public static int getGCD(int a, int b) {
if (b == 0)
return a;
else
return getGCD(b, a % b);
}
public static Fraction reduce(Fraction f) {
int c = getGCD(f.p, f.q);
return new Fraction(f.p / c, f.q / c);
}
public static HashSet<Fraction> getAll(int m, int n) {
HashSet<Fraction> res = new HashSet<Fraction>();
for (int p = m; p <= n; p++)
for (int q = 1; q < p; q++) {
Fraction f = new Fraction(p,q);
Fraction fr = reduce(f);
if (!res.contains(fr))
res.add(fr);
}
return res;
}
public static void print(Fraction f) {
System.out.println(f.p + "/" + f.q);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
HashSet<Fraction> res = getAll(2, 4);
for (Fraction f : res)
print(f);
}
}
以下是程序的输出结果
4/3
3/1
4/1
2/1
3/2
2/1
你可以看到分数2/1被重复了。有人能帮我解决这个问题并告诉我如何修复吗?非常感谢。