题目描述
给定一个整数 N
,请你求出所有分母小于或等于 N
,大小在 [0,1]
范围内的最简分数,并按从小到大顺序依次输出。
例如,当 N=5
时,所有满足条件的分数按顺序依次为:
01,15,14,13,25,12,35,23,34,45,11
输入格式
共一行,包含一个整数 N
。
输出格式
按照从小到大的顺序,输出所有满足条件的分数。
每个分数占一行,格式为 a/b
,其中 a
为分子, b
为分母。
数据范围
1≤N≤160
样例
5
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
我不能理解y总的意图 但怎么样可以做对
不难发现这个数据最大才 160*160 所以可以枚举出全部的情况,再对其进行排序输出就好,用struct封装再采用double类型的值进行值大小的排序,最后按顺序输出就好
代码:
#include<bits/stdc++.h>
using namespace std;
struct Node{
int a,b;
double val;
bool operator<(const Node& b)const{
return val < b.val;
}
};
int n;
vector<Node> vec,ans;
map<Node,int> mp;
int main(){
cin>>n;
vec.push_back({0,1,0});
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
vec.push_back({j,i,(double)j/i});
for(auto it:vec){
int gcd=__gcd(it.a,it.b);
it.a/=gcd;
it.b/=gcd;
}
for(auto it:vec)mp[it]++;
for(auto [it,jt]:mp)ans.push_back(it);
sort(ans.begin(),ans.end());
for(auto it:ans)cout<<it.a<<"/"<<it.b<<endl;
return 0;
}