परिमेय संख्याएँ - एक संख्या जिसे p/q के रूप में व्यक्त किया जाता है। दी गई शर्त कि p और q दोनों पूर्णांक होने चाहिए और q 0 के बराबर नहीं होना चाहिए।
धनात्मक परिमेय संख्याएँ वे संख्याएँ हैं जिनके अंतिम मान धनात्मक होते हैं। इसके लिए, या तो p और q दोनों धनात्मक होने चाहिए या p और q दोनों ऋणात्मक होने चाहिए।
इस समस्या में दी गई संख्या तक धनात्मक यादृच्छिक संख्याएँ उत्पन्न करनी हैं। हमें n तक परिमित संख्या में धनात्मक परिमेय संख्याएँ उत्पन्न करनी हैं यानी हम 1 से n के बीच परिमेय संख्याएँ खोजेंगे। इस एल्गोरिदम के लिए, हम उन यादृच्छिक संख्याओं को उत्पन्न करेंगे जहां 1 <= p <= n और 1 <= q <= n।
आइए अवधारणा को बेहतर ढंग से समझाने के लिए एक उदाहरण लेते हैं -
इनपुट : 3 आउटपुट : 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 generate(int n){ List 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 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
