เศษส่วนที่ลดรูปแล้วใน C++

สมมติว่าเรามีจำนวนเต็ม n เราต้องหาเศษส่วนที่ลดรูปแล้วทั้งหมดระหว่าง 0 และ 1 (ไม่รวมขอบ) ที่ตัวส่วน ≤ n

ตัวอย่าง: n = 4 ผลลัพธ์: ["1/2","1/3","1/4","2/3","3/4"] (ไม่นับ "2/4" เพราะลดรูปได้เป็น "1/2")

วิธีแก้ปัญหา

1. วน denominator i = 2 ถึง n
2. วน numerator j = 1 ถึง i-1
3. คำนวณ gcd(i, j) ลดรูปได้ a = j/gcd, b = i/gcd
4. เก็บ "a/b" ใน set เพื่อไม่ซ้ำ
5. คืนค่า set เป็น vector

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

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<string> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 

class Solution { 
public: 
    vector<string> simplifiedFractions(int n) { 
        vector<string> ret; 
        for (int i = 2; i <= n; i++) { 
            for (int j = 1; j < i; j++) { 
                int c = __gcd(i, j); 
                int a = j / c; 
                int b = i / c; 
                ret.push_back(to_string(a) + "/" + to_string(b)); 
            } 
        } 
        set<string> s(ret.begin(), ret.end()); 
        return vector<string>(s.begin(), s.end()); 
    } 
}; 

int main(){ 
    Solution ob; 
    print_vector(ob.simplifiedFractions(4)); 
}

ข้อมูลนำเข้า

4

ผลลัพธ์

[1/2, 1/3, 1/4, 2/3, 3/4, ]