贴一个暴力的代码,写的比较复杂
注意一下最简分数判断,避免输出重复的,只需要计算下gcd=1就行了
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII; //分子 分母
int n;
vector<pair<double, PII> > id;
int main(){
cin >> n;
for(int i = 2; i <= n; i ++ ) //外层枚举分母
for(int j = 1; j <= i - 1; j ++ ) //内层枚举分子
{
double c = (double)j / i;
id.push_back({c, {j, i}});
}
sort(id.begin(), id.end()); //按照分子分母的值 进行排序
auto it = unique(id.begin(), id.end(), [](const pair<double, PII>& a, const pair<double, PII>& b){
return a.first == b.first;
});
id.erase(it, id.end());
cout << "0/1" << endl;
for(int i = 0; i < id.size(); i ++ )
{
cout << id[i].second.first << '/' << id[i].second.second << endl;
}
cout << "1/1" << endl;
return 0;
}