เศษส่วนที่ไม่ซ้ำใน C++

สมมติว่าเรามีรายการเศษส่วนโดยที่เศษส่วนแต่ละส่วนมี [ตัวเศษ ตัวส่วน] (ตัวเศษ / ตัวส่วน) เรามีรายการเศษส่วนใหม่ โดยให้ตัวเลขที่เป็นเศษส่วนคือ −

• ในเงื่อนไขที่ลดลงมากที่สุด (20 / 14 กลายเป็น 10 / 7)

• เศษส่วนที่ซ้ำกัน (หลังจากลด) จะถูกลบออก

• เรียงลำดับจากน้อยไปมากตามมูลค่าที่แท้จริง

• หากตัวเลขเป็นลบ เครื่องหมาย '-' จะเป็นตัวเศษ

ดังนั้น หากอินพุตเป็น {{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}} ผลลัพธ์จะออกมา เป็น [[-1, 2],[2, 1],[7, 3],[5, 1]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งชุด s

• n :=ขนาดของวี

• สร้างอาร์เรย์ r

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • c :=gcd ของ |v[i, 0]| และ |v[i, 1]|

  • v[i, 0] :=v[i, 0] / c

  • v[i, 1] :=v[i, 1] / c

  • แทรก {v[i, 0], v[i, 1]} ที่ส่วนท้ายของ r

• จัดเรียงอาร์เรย์ r ตามค่าของพวกมัน

• สร้างอาร์เรย์ ret

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ r อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้า ret ไม่ว่างและองค์ประกอบสุดท้ายของ ret เหมือนกับ r[i] ดังนั้น −

    • ใส่ r[i] ต่อท้าย ret

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;void print_vector(vector> v) { cout <<"["; สำหรับ (int i =0; i &a, vector &b){ double aa =(double)a[0] / (double) เอ[1]; ดับเบิ้ลบี =(ดับเบิ้ล)b[0] / (ดับเบิ้ล)b[1]; กลับ aa > แก้ (vector>&v) { set > s; int n =v.size(); เวกเตอร์ <เวกเตอร์ > r; สำหรับ(int i =0; i > ย้อนกลับ; for(int i =0; i > v ={{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{- 6, 12}}; โซลูชัน ob; print_vector(ob.solve(v));}

อินพุต

ผลลัพธ์

[[-1, 2, ],[2, 1, ],[7, 3, ],[5, 1, ],]