อัลกอริทึมสร้างจำนวนตรรกยะบวกใน Java

จำนวนตรรกยะ (Rational Numbers) − จำนวนที่แสดงในรูป p/q โดยที่ p และ q ต้องเป็นจำนวนเต็ม และ q ≠ 0

จำนวนตรรกยะบวก (Positive rational numbers) คือจำนวนที่มีค่าสุดท้ายเป็นบวก สำหรับนี้ p และ q ต้องเป็นบวกทั้งคู่ หรือเป็นลบทั้งคู่

ในโจทย์นี้ ต้องสร้างจำนวนสุ่มบวกจนถึงตัวเลขที่กำหนด ต้องสร้างจำนวนตรรกยะบวกจำนวนจำกัดถึง n คือ หาจำนวนตรรกยะระหว่าง 1 ถึง n โดยอัลกอริทึมนี้จะสร้างตัวเลขสุ่มที่ 1 ≤ p ≤ n และ 1 ≤ q ≤ n

ตัวอย่างเพื่ออธิบายแนวคิด:

Input : 3
Output : 1, ½, ⅓, 2, ⅔, 3/2, 3

คำอธิบาย − ในตัวอย่างนี้ พิจารณาค่าระหว่าง 1 ถึง 3 สำหรับ p และ q ทั้งคู่

อัลกอริทึมที่ออกแบบมานี้ทำงานโดยใช้เซต (sets) ซึ่งเป็นโครงสร้างข้อมูลที่ดีที่สุดสำหรับการสร้างการจับคู่ที่ต้องการอย่างเหมาะสม เนื่องจากเซตสามารถแมปได้ และการแมปสามารถเป็นออเดอร์ n ถึง n คือ ค่าแต่ละค่าในเซต 1 สามารถแมปกับค่าในเซต 2 ได้อย่างเหมาะสม สร้างการแมปที่สร้างคู่ที่ต้องการ สำหรับการสร้างคู่ที่ต้องการ เราใช้เซตสองเซตของค่าบวกและแมปค่าเพื่อหาคำตอบ

ตัวอย่าง:

(1,1), (1,2), (1,3)
(2,1), (2,2), (2,3)
(3,1), (3,2), (3,3)

จัดเรียงค่าเหล่านี้ในวิธีการเดินทางแบบ L उলटा (inverted L shape traversal):

(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 ที่ชี้ไปยังค่าเดียวกัน เราจะกำจัดค่าเหล่านี้โดยใช้ตัวหารร่วมมาก (greatest common divisor)

ตัวอย่างโค้ด

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