Posted on 2007-06-03 21:13
ZelluX 閱讀(287)
評論(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;
}