Posted on 2007-06-03 21:13
ZelluX 阅读(285)
评论(0) 编辑 收藏 所属分类:
Algorithm
官方的一个很赞的做法,Divide and Conquer,核心部分:
void
genfrac(int n1, int d1, int n2, int d2)


{

if(d1+d2 > n) /**//* cut off recursion */
return;

genfrac(n1,d1, n1+n2,d1+d2);
fprintf(fout, "%d/%d\n", n1+n2, d1+d2);
genfrac(n1+n2,d1+d2, n2,d2);
}

最朴素的做法

/**//*
PROG: frac1
ID: 06301031
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;


class Fraction
{
int gcd(int x, int y);
public:
int numerator;
int denominator;
Fraction(int pa, int pb);
bool reductable();
};

bool compareFrac(const Fraction& f1, const Fraction& f2);

int main()
{
ifstream fin("frac1.in");
ofstream fout("frac1.out");
int n;
fin >> n;
vector<Fraction> fracs;
int i, j;
fracs.push_back(Fraction(0, 1));

for (i = 1; i <= n; i++)
{

for (j = 1; j <= i; j++)
{
Fraction frac(j, i);

if (!frac.reductable())
{
fracs.push_back(frac);
}
}
}

sort(fracs.begin(), fracs.end(), compareFrac);
vector<Fraction>::iterator iter;

for (iter = fracs.begin(); iter != fracs.end(); iter++)
{
fout << iter->numerator << '/' << iter->denominator << endl;
}
return 0;
}


Fraction::Fraction(int pa, int pb)
{
numerator = pa;
denominator = pb;
}


bool Fraction::reductable()
{
return (gcd(numerator, denominator) != 1);
}


int Fraction::gcd(int x, int y)
{
if (x < y) swap(x, y);
if (x % y == 0) return y;
return gcd(y, x % y);
}


bool compareFrac(const Fraction& f1, const Fraction& f2)
{
return (long)f1.numerator * (long)f2.denominator < (long)f1.denominator * (long)f2.numerator;
}