用Java生成正有理数的算法
有理数-以p/q形式表示的数字。给定p和q都应为整数且q不等于0的条件。
正有理数是那些最终值为正的数。为此，p和q都应为正，或者p和q均应为负。
在这个问题中，要生成最多给定数的正随机数。我们必须生成有限数量的正有理数到n，即我们将找到1到n之间的有理数。对于此算法，我们将生成随机数，其中1<=p<=n和1<=q<=n。
让我们以一个例子更好地阐述这个概念-
Input : 3 Output : 1, ½ , ⅓ , 2 , ⅔ , 3/2 , 3 .
解释-在此示例中，我们将考虑p和q介于1到3之间的值。
为此设计的算法将使用集合来工作，这些集合是用于最佳生成所需组合的最佳数据结构。由于可以映射集合，并且映射的顺序可以为n到n，即set1中的每个值都可以与set2中的值正确映射，从而创建可以生成所需对的映射。为了生成所需的对，我们将使用正值集并映射这些值以获得解。
让我们举个例子
(1,1) , (1,2) , (1,3) (2,1) , (2,2) , (2,3) (3,1) , (3,2) , (3,3)
让我们以倒L形遍历方法重新排列这些值-
(1,1) (1,2) , (2,2) , (2,1) (1,3) , (2,3) , (3,3) , (3,2) , (3,1)
这些是我们在生成正有理算法示例中使用的值。为了更好地理解我们已经产生了完全相同的值，只需将替换为∕即可得到这些值-
1/1 1/2 , 2/2 , 2/1 1/3 , 2/3 , 3/3 , 3/2 , 3/1
尽管存在诸如1∕1、2∕2、3∕3之类的值，它们指向相同的值。我们将使用最大公约数消除这些值。
示例
import java.util.ArrayList;
import java.util.List;
class PositiveRational {
private static class PositiveRationalNumber {
private int numerator;
private int denominator;
public PositiveRationalNumber(int numerator, int denominator){
this.numerator = numerator;
this.denominator = denominator;
}
@Override
public String toString(){
if (denominator == 1) {
return Integer.toString(numerator);
} else {
return Integer.toString(numerator) + '/' +
Integer.toString(denominator);
}
}
}
private static int gcd(int num1, int num2){
int n1 = num1;
int n2 = num2;
while (n1 != n2) {
if (n1 > n2)
n1 -= n2;
else
n2 -= n1;
}
return n1;
}
private static List<PositiveRationalNumber> generate(int n){
List<PositiveRationalNumber> list = new ArrayList<>();
if (n > 1) {
PositiveRationalNumber rational = new PositiveRationalNumber(1, 1);
list.add(rational);
}
for (int loop = 1; loop <= n; loop++) {
int jump = 1;
if (loop % 2 == 0)
jump = 2;
else
jump = 1;
for (int row = 1; row <= loop - 1; row += jump) {
if (gcd(row, loop) == 1) {
PositiveRationalNumber rational = new PositiveRationalNumber(row, loop);
list.add(rational);
}
}
for (int col = loop - 1; col >= 1; col -= jump) {
if (gcd(col, loop) == 1) {
PositiveRationalNumber rational = new PositiveRationalNumber(loop, col);
list.add(rational);
}
}
}
return list;
}
public static void main(String[] args){
List<PositiveRationalNumber>rationals = generate(5);
System.out.println(rationals.stream().
map(PositiveRationalNumber::toString).
reduce((x, y) -> x + ", " + y).get());
}
}输出结果
1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 3/4, 4/3, 4, 1/5, 2/5, 3/5, 4/5, 5/4, 5/3, 5/2, 5