Phân số duy nhất trong C ++

Giả sử chúng ta có một danh sách các phân số trong đó mỗi phân số chứa [tử số, mẫu số] (tử số / mẫu số). Chúng tôi đã tìm thấy một danh sách mới các phân số sao cho các số trong phân số là -

• Trong các điều khoản giảm nhất của họ. (20/14 trở thành 10/7).

• Mọi phân số trùng lặp (sau khi giảm) sẽ bị loại bỏ.

• Được sắp xếp theo thứ tự tăng dần theo giá trị thực của chúng.

• Nếu số âm, dấu '-' sẽ ở cùng tử số.

Vì vậy, nếu đầu vào giống như {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {- 6, 12}}, thì đầu ra sẽ là [[-1, 2], [2, 1], [7, 3], [5, 1]]

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

• Xác định một bộ s

• n:=kích thước của v

• tạo một mảng r

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

  • c:=gcd của | v [i, 0] | và | v [i, 1] |

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

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

  • chèn {v [i, 0], v [i, 1]} vào cuối r

• sắp xếp mảng r dựa trên các giá trị của chúng

• tạo một mảng ret

• để khởi tạo i:=0, khi tôi

  • nếu ret không trống và phần tử cuối cùng của ret giống với r [i], thì -

    • chèn r [i] vào cuối ret

• trả lại ret

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << "[";
      for (int j = 0; j < v[i].size(); j++) {
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   static bool cmp(vector <int>& a, vector <int>& b){
      double aa = (double)a[0] / (double)a[1];
      double bb = (double)b[0] / (double)b[1];
      return aa < bb;
   }
   vector<vector<int>> solve(vector<vector<int>>& v) {
      set < vector <int> > s;
      int n = v.size();
      vector < vector <int> > r;
      for(int i = 0; i < n; i++){
         int c = __gcd(abs(v[i][0]), abs(v[i][1]));
         v[i][0] /= c;
         v[i][1] /= c;
         r.push_back({v[i][0], v[i][1]});
      }
      sort(r.begin(), r.end(), cmp);
      vector < vector <int> > ret;
      for(int i = 0; i < r.size(); i++){
         if(!ret.empty() && ret.back() == r[i]) continue;
         ret.push_back(r[i]);
      }
      return ret;
   }
};
int main(){
   vector<vector<int>> v = {{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-
   6, 12}};
   Solution ob;
   print_vector(ob.solve(v));
}

Đầu vào

{{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}}

Đầu ra

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