Số hợp lý - Một số được biểu diễn dưới dạng p / q. Với điều kiện p và q đều phải là số nguyên và q không được bằng 0.
Số hữu tỉ dương là những số có giá trị cuối cùng là số dương. Đối với điều này, cả hai p và q phải dương hoặc p và q cả hai đều phải âm.
Trong bài toán này để tạo ra các số ngẫu nhiên dương lên đến một số nhất định. Chúng ta phải tạo ra một số hữu hạn các số hữu tỉ dương đến n tức là chúng ta sẽ tìm thấy các số hữu tỉ từ 1 đến n. Đối với thuật toán này, chúng tôi sẽ tạo các số ngẫu nhiên trong đó 1 <=p <=n và 1 <=q <=n.
Hãy lấy một ví dụ để hiểu rõ hơn về khái niệm này -
Input : 3 Output : 1, ½ , ⅓ , 2 , ⅔ , 3/2 , 3 .
Giải thích - Trong ví dụ này, chúng tôi sẽ xem xét các giá trị từ 1 đến 3 cho cả p và q.
Thuật toán được thiết kế cho điều này sẽ hoạt động bằng cách sử dụng các tập hợp là cấu trúc dữ liệu tốt nhất để tạo ra các kết hợp cần thiết một cách tối ưu. Vì các tập hợp có thể được ánh xạ và ánh xạ có thể có thứ tự từ n đến n tức là mỗi giá trị trong set1 có thể được ánh xạ đúng với các giá trị trong set2 tạo ra một ánh xạ có thể tạo ra các cặp được yêu cầu. Để tạo các cặp bắt buộc, chúng tôi sẽ sử dụng các tập hợp các giá trị dương và ánh xạ các giá trị để có được các giải pháp.
Hãy lấy một ví dụ,
(1,1) , (1,2) , (1,3) (2,1) , (2,2) , (2,3) (3,1) , (3,2) , (3,3)
Hãy sắp xếp lại các giá trị này theo phương pháp duyệt hình chữ L ngược -
(1,1) (1,2) , (2,2) , (2,1) (1,3) , (2,3) , (3,3) , (3,2) , (3,1)
Đây là những giá trị mà chúng tôi đã sử dụng để tạo ra các ví dụ thuật toán hợp lý dương. Để hiểu rõ hơn rằng chúng tôi đã mang lại các giá trị giống hệt nhau, chỉ cần thay thế, bằng ∕ để nhận các giá trị này -
1/1 1/2 , 2/2 , 2/1 1/3 , 2/3 , 3/3 , 3/2 , 3/1
Mặc dù có các giá trị như 1∕1, 2∕2, 3∕3 trỏ đến cùng một giá trị. Chúng tôi sẽ loại bỏ những giá trị này bằng cách sử dụng ước số chung lớn nhất.
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());
}
} Đầu ra
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