ভগ্নাংশ (Rational Numbers) − p/q রূপে প্রকাশিত একটি সংখ্যা। শর্ত হলো p এবং q উভয়ই পূর্ণসংখ্যা হতে হবে এবং q শূন্যের সমান নয়।
ধনাত্মক ভগ্নাংশ হলো যেসব সংখ্যার চূড়ান্ত মান ধনাত্মক। এর জন্য p এবং q উভয়ই ধনাত্মক হতে হবে অথবা উভয়ই ঋণাত্মক।
এই সমস্যায় একটি দেওয়া সংখ্যা পর্যন্ত ধনাত্মক র্যান্ডম সংখ্যা জেনারেট করতে হবে। আমাদের n পর্যন্ত সীমিত সংখ্যক ধনাত্মক ভগ্নাংশ খুঁজে বের করতে হবে অর্থাৎ ১ থেকে n এর মধ্যে ভগ্নাংশ খুঁজে বের করব। এই অ্যালগরিদমে আমরা ১ ≤ p ≤ n এবং ১ ≤ q ≤ n এর মধ্যে র্যান্ডম সংখ্যা জেনারেট করব।
উদাহরণ:
Input : 3 Output : 1, ½, ⅓, 2, ⅔, 3/2, 3
ব্যাখ্যা − এই উদাহরণে, p এবং q উভয়ের জন্য ১ থেকে ৩ এর মান বিবেচনা করা হয়েছে।
এই অ্যালগরিদম সেট ব্যবহার করে কাজ করে যা প্রয়োজনীয় কম্বিনেশন বাস্তবায়নের জন্য সেরা ডেটা স্ট্রাকচার। সেটগুলো ম্যাপ করা যায় এবং ম্যাপিং হতে পারে n থেকে n অর্ডারের অর্থাৎ সেট১-এর প্রতিটি মান সেট২-এর মানগুলোর সাথে সঠিকভাবে ম্যাপ করা যায় যাতে প্রয়োজনীয় জোড়া তৈরি করা যায়। প্রয়োজনীয় জোড়া জেনারেট করতে আমরা দুটি ধনাত্মক মানের সেট ব্যবহার করব এবং মানগুলোর ম্যাপিং করব সমাধান পেতে।
একটি উদাহরণ নিই:
(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 এর মতো মান আছে যেগুলো একই মান নির্দেশ করে। আমরা এই মানগুলো সবচেয়ে বড় সাধারণ ভাজক (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 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
