埃及分数

#include<iostream>
using namespace std;

class fra                                       //分数结构
{
public:
    fra();
    fra(int,int);
    ~fra(){}
    void show();
    int x();
    int y();
    bool check();
    fra operator + (fra&);
    fra operator ++ ();
    fra operator - (fra&);
    fra operator / (int);
    fra& operator = (fra&);
    bool operator == (fra&);
    bool operator > (fra&);
    bool operator >= (fra&);
private:
    int xx;
    int yy;
};
static fra F[10];                                //保存埃及分数
static int N;                                    //埃及分数长度
static int end;                                  //埃及分数末尾
int main()
{
    bool find(fra,fra,int);
    int i=0,n,a,b;
    cin>>a>>b;
    fra A(1,1),T(a,b);
    for(n=1;n<15;n++)
    {
        N=end=n;
        if(find(A,T,n))
            break;
    }
    T.show();
    cout<<"=";
    for(i=1;i<=n;i++)
    {
        F[i].show();
        if(i!=n)
            cout<<"+";
    }
}
bool find(fra A,fra T,int i)            //埃及分数最佳方案核心
{
    if(i==1)
    {
        if(A==T)
            return false;
        if(T.check()&&T>F[end])
        {
            N=end;
            F[N]=T;
            N--;
            return true;
        }
        return false;
    }
    fra B,C,D;
    B=T/i;
    D=++A;
    while(true)
    {
        if(D>=B&&T>D)
        {
            C=T-D;
            if(find(D,C,i-1))            //递归，找到一组方案
            {
                F[N]=D;
                while(++D>=B)
                {
                    C=T-D;
                    if(find(D,C,i-1))    //递归，找到最佳方案
                        F[N]=D;
                }
                N--;
                return true;
            }
        }
        ++D;
        if(B>D)
            return false;
    }
}
int gcd(int x,int y)                                    //最大公约数
{
    int temp;
    x=x<0?-x:x;
    y=y<0?-y:y;
    while(y%x!=0)
    {
        temp=x;
        x=y%x;
        y=temp;
    }
    return x;
}
/*fra类 成员函数*/
void fra::show()
{
    cout<<xx<<"/"<<yy;
}
int fra::x()
{
    return xx;
}
int fra::y()
{
    return yy;
}
bool fra::check()
{
    if(xx==1)
        return true;
    return false;
}
fra::fra()
{
    xx=0;
    yy=1;
}
fra::fra(int x=1,int y=2)
{
    int temp=gcd(x,y);
    if(y<0)
    {
        y=-y;
        x=-x;
    }
    xx=x/temp;
    yy=y/temp;
}
fra fra::operator + (fra& t)
{
    return fra(xx*t.yy+yy*t.xx,yy*t.yy);
}
fra fra::operator ++ ()
{
    return fra(xx,++yy);
}
fra fra::operator - (fra& t)
{
    return fra(xx*t.yy-yy*t.xx,yy*t.yy);
}
fra fra::operator / (int n)
{
    return fra(xx,yy*n);
}
fra& fra::operator = (fra& t)
{
    xx=t.xx;
    yy=t.yy;
    return *this;
}
bool fra::operator == (fra& t)
{
    if(xx==t.xx&&yy==t.yy)
        return true;
    return false;
}
bool fra::operator > (fra& t)
{
    if(xx*t.yy>yy*t.xx)
        return true;
    return false;
}
bool fra::operator >= (fra& t)
{
    if(xx*t.yy>=yy*t.xx)
        return true;
    return false;
}