C++의 단순화된 분수

정수 n이 있다고 가정하고 분모 <=n이 되도록 0과 1(배타적) 사이의 모든 단순화된 분수 목록을 찾아야 합니다. 여기서 분수는 임의의 순서가 될 수 있습니다.

따라서 입력이 n =4와 같으면 출력은 ["1/2","1/3","1/4","2/3","3/4"]가 "2"가 됩니다. /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, ]