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

จำนวนตรรกยะ − ตัวเลขที่แสดงในรูปของ p/q กำหนดเงื่อนไขว่า p และ q ควรเป็นจำนวนเต็ม และ q ไม่ควรเท่ากับ 0

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

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

มาดูตัวอย่างเพื่ออธิบายแนวคิดกันดีกว่า −

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

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

อัลกอริธึมที่ออกแบบมาสำหรับสิ่งนี้จะทำงานโดยใช้ชุดซึ่งเป็นโครงสร้างข้อมูลที่ดีที่สุดสำหรับการสร้างชุดค่าผสมที่จำเป็นอย่างเหมาะสมที่สุด เนื่องจากชุดสามารถจับคู่ได้และการแมปสามารถมีลำดับจาก 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/11/2 , 2/2 , 2/11/3 , 2/3 , 3/3 , 3/2 , 3/1

แม้ว่าจะมีค่าเช่น 1∕1, 2∕2, 3∕3 ที่ชี้ไปที่ค่าเดียวกัน เราจะกำจัดค่าเหล่านี้โดยใช้ตัวหารร่วมมากที่มากที่สุด

ตัวอย่าง

<ก่อน> นำเข้า java.util.ArrayList; นำเข้า java.util.List; คลาส PositiveRational { คลาสคงที่ส่วนตัว PositiveRationalNumber { ตัวเศษ int ส่วนตัว; ตัวหาร int ส่วนตัว; PositiveRationalNumber สาธารณะ (ตัวเศษ int ตัวส่วน int) { this.numerator =ตัวเศษ; this.denominator =ตัวหาร; } @แทนที่สตริงสาธารณะ toString(){ ถ้า (ตัวส่วน ==1) { ส่งคืน Integer.toString (ตัวเศษ); } อื่น { ส่งคืน Integer.toString (ตัวเศษ) + '/' + Integer.toString (ตัวส่วน); } } } คงที่ส่วนตัว int gcd (int num1, int num2) { int n1 =num1; int n2 =num2; ในขณะที่ (n1 !=n2) { if (n1> n2) n1 -=n2; อื่น n2 -=n1; } ส่งคืน n1; } รายการคงที่ส่วนตัว สร้าง (int n) { รายการ รายการ =ใหม่ ArrayList<>(); ถ้า (n> 1) { PositiveRationalNumber rational =ใหม่ PositiveRationalNumber (1, 1); list.add(เหตุผล); } for (int loop =1; loop <=n; loop++) { int jump =1; ถ้า (วน % 2 ==0) กระโดด =2; อื่นกระโดด =1; สำหรับ (แถว int =1; แถว <=ลูป - 1; แถว +=กระโดด) { ถ้า (gcd (แถว, ลูป) ==1) { PositiveRationalNumber rational =ใหม่ PositiveRationalNumber (แถว, ลูป); list.add(เหตุผล); } } for (int col =loop - 1; col>=1; col -=jump) { if (gcd(col, loop) ==1) { PositiveRationalNumber rational =new PositiveRationalNumber(loop, col); list.add(เหตุผล); } } } รายการส่งคืน; } โมฆะคงที่สาธารณะ main(String[] args){ Listrationals =สร้าง(5); System.out.println(rationals.stream(). map(PositiveRationalNumber::toString). ลด((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