資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Java生成正有理數演算法
有理數 - 可以表示為p/q形式的數，其中p和q都是整數，且q不等於0。
正有理數是指最終值為正數的有理數。為此，p和q必須都為正數或都為負數。
本問題旨在生成不超過給定數字n的正隨機數。我們需要生成有限數量的正有理數到n，即我們將在1到n之間找到有理數。對於此演算法，我們將生成隨機數，其中1 <= p <= n且1 <= q <= n。
讓我們舉個例子來更好地闡述這個概念：
Input : 3 Output : 1, ½ , ⅓ , 2 , ⅔ , 3/2 , 3 .
說明 - 在此示例中，我們將考慮p和q的值在1到3之間。
為此設計的演算法將使用集合，集合是生成所需組合的最佳資料結構。因為集合可以對映，並且對映可以是n到n的順序，即集合1中的每個值都可以與集合2中的值正確對映，從而建立可以生成所需對的對映。為了生成所需的對，我們將使用兩個正值集合並將這些值對映以獲得解。
讓我們舉個例子：
(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
更新於：2019年10月16日
715 次瀏覽
廣告