C ++中的简化分数

假设我们有一个整数n，我们必须找到一个介于0和1（不包括）之间的所有简化分数的列表，以使分母<= n。在这里，分数可以是任何顺序。

因此，如果输入像n = 4，那么输出将是[“ 1/2”，“ 1/3”，“ 1/4”，“ 2/3”，“ 3/4”]为“ 2” / 4“不是简化的分数，因为它可以简化为” 1/2“。

为了解决这个问题，我们将遵循以下步骤-

• 定义数组ret

• 对于初始化i：= 2，当i <= n时，更新（将i增加1），执行-

• c：= i和j的gcd

• a：= j / c

• b：= i / c

• 在ret的末尾插入（a作为字符串连接，“ /”连接b作为字符串）

• 对于初始化j：= 1，当j <i时，更新（将j增加1），做-

• 返回存在于ret中的所有唯一元素的数组

例 

让我们看下面的实现以更好地理解-

#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));
}

输入值

4

输出结果

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