USACO2.1 Ordered Fractions(frac1)
1300 ワード
i,jはそれぞれ求めた分数の分子分母であり、i:0~nとj:i~nを組み合わせて遍歴し、現在の分数が要求を満たしているか否かを検出し、満足すればi/jの値float aを求め、map>に>を組み合わせて格納し、a値で組み合わせてソートする.そしてi/jを順番に出力するだけでよい.
/*
ID:jzzlee1
PROG:frac1
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<cmath>
#include<map>
#include<utility>
#include<cstring>
using namespace std;
ifstream fin("frac1.in");
ofstream fout("frac1.out");
bool check(int i,int j) //
{
if(i==0)
{
if(j==1)
return 1;
else
return 0;
}
for(int k=2;k<=i;++k)
if(i%k==0&&j%k==0)
return 0;
return 1;
}
int main()
{
int i,j,n;float a;
//cin>>n;
fin>>n;
map<float,pair<int,int> > map1;
map<float,pair<int,int> >::iterator iter;
for(i=0;i<=n;++i)
for(j=i;j<=n;++j)
{
if(check(i,j))
{
a=(float)i/(float)j;
map1.insert(make_pair(a,make_pair(i,j)));
}
}
for(iter=map1.begin();iter!=map1.end();++iter)
{
//cout<<(iter->second).first<<"/"<<(iter->second).second<<endl;
fout<<(iter->second).first<<"/"<<(iter->second).second<<endl;
}
return 0;
}