Phân số đơn giản trong C ++

Giả sử chúng ta có một số nguyên n, chúng ta phải tìm một danh sách tất cả các phân số đơn giản từ 0 đến 1 (loại trừ) sao cho mẫu số <=n. Ở đây, các phân số có thể theo thứ tự bất kỳ.

Vì vậy, nếu đầu vào là n =4, thì đầu ra sẽ là ["1/2", "1/3", "1/4", "2/3", "3/4"] là "2 / 4 "không phải là một phân số được đơn giản hóa vì nó có thể được đơn giản hóa thành" 1/2 ".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định ret mảng

• để khởi tạo i:=2, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • để khởi tạo j:=1, khi j

    • c:=gcd của tôi và j

    • a:=j / c

    • b:=i / c

    • insert (a as string concatenate "/" concatenate b as string) vào cuối ret

• trả về một mảng tất cả các phần tử duy nhất có trong ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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());
   }
};
main(){
   Solution ob;
   print_vector(ob.simplifiedFractions(4));
}

Đầu vào

4

Đầu ra

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