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