在 Java 中生成正有理数的算法
javaobject oriented programmingprogramming
有理数 − 以 p/q 形式表示的数字。给定条件,p 和 q 都应该是整数,并且 q 不应该等于 0。
正有理数是最终值为正的数。为此,p 和 q 都应该是正数,或者 p 和 q 都应该是负数。
在此问题中,要生成不超过给定数字的正随机数。我们必须生成有限数量的正有理数,即我们将找到 1 到 n 之间的有理数。对于此算法,我们将生成随机数,其中 1 <= p <= n 且 1 <= q <= n。
让我们举一个例子来更好地阐述 − 的概念
输入:3 输出: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