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