Số hữu tỷ − Số biểu diễn dạng p/q. Điều kiện p, q đều là số nguyên và q ≠ 0.
Số hữu tỷ dương là số có giá trị cuối cùng dương. Điều này xảy ra khi p, q cùng dấu (cả hai dương hoặc cả hai âm).
Bài toán: tạo số hữu tỷ dương ngẫu nhiên đến số cho trước. Tìm số hữu tỷ dương hữu hạn đến n (1 đến n). Thuật toán tạo số ngẫu nhiên với 1 ≤ p ≤ n và 1 ≤ q ≤ n.
Ví dụ minh họa:
Input : 3 Output : 1, ½ , ⅓ , 2 , ⅔ , 3/2 , 3 .
Giải thích − Xét giá trị 1 đến 3 cho p và q.
Thuật toán dùng sets (tập hợp) - cấu trúc dữ liệu tối ưu để sinh tổ hợp. Sets có thể map ánh xạ bậc n đến n, mỗi giá trị set1 map với set2 tạo cặp cần thiết. Dùng 2 tập giá trị dương và map để lấy giải pháp.
Ví dụ:
(1,1) , (1,2) , (1,3) (2,1) , (2,2) , (2,3) (3,1) , (3,2) , (3,3)
Sắp xếp lại theo phương pháp duyệt hình L ngược:
(1,1) (1,2) , (2,2) , (2,1) (1,3) , (2,3) , (3,3) , (3,2) , (3,1)
Thay dấu phẩy bằng ∕:
1/1 1/2 , 2/2 , 2/1 1/3 , 2/3 , 3/3 , 3/2 , 3/1
Loại bỏ giá trị trùng (1/1, 2/2, 3/3) bằng greatest common divisor (GCD).
Ví dụ
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()); } }
Kết quả
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