C++の簡略化された分数

整数nがあるとすると、分母<=nとなるように、0から1（排他的）までのすべての簡略化された分数のリストを見つける必要があります。ここでは、分数は任意の順序にすることができます。

したがって、入力がn =4の場合、出力は["1/2"、 "1/3"、 "1/4"、 "2/3"、"3/4"]のようになります。 / 4 "は、" 1/2 "に簡略化できるため、簡略化された分数ではありません。

これを解決するには、次の手順に従います-

• 配列retを定義する

• 初期化i：=2の場合、i <=nの場合、更新（iを1増やします）、実行-

  • 初期化j：=1の場合、j

    • c：=iとjのgcd

    • a：=j / c

    • b：=i / c

    • retの最後に（a as string concatenate "/" concatenate b as string）を挿入します

• 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, ]