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