学步园

/*-------------------------------------------------------------------
* Purpose:
*         有如下分数式，求其第2008项，并求所有项中的最大项
*         1/2,3/5,4/7,6/10,8/13,9/15......
*         规律如下：
*         分母是分子+i
*         分子是其前i - 1项中出现的所有分子分母除过的最小数
* Time:
*         2012年3月18日 13:22:13
* Author:
*         lisency
--------------------------------------------------------------------*/
#include <iostream>
#include <deque>
#include <list>
#include <algorithm>

using namespace std;

class FractionalExpr
{
public:
    /**
    * 
    **/
    FractionalExpr()
    {
        init();
        return;
    }
    /**
    *  
    **/
    ~FractionalExpr()
    {
        return;
    }
    /**
     * 
     */
    void init()
    {
        offset = 0;
        max_denominator = 1;
        max_numerator = 0;
        used_int.clear();
    }
    /**
     * 得到下一个数
     */
    int get_next_int()
    {
        offset ++;
        offset = move(offset);
        return offset;
    }
    /**
     * 
     */
    int move(int off)
    {
        ListInt::iterator iter = used_int.begin();
        for (;iter != used_int.end();++iter)
        {
            if (off < *iter)
            {
                break;
            }
            off ++;
        }
        used_int.erase(used_int.begin(),iter);
        return off;
    }
    int add(int num)
    {
        ListInt::iterator iter = upper_bound(used_int.begin(),used_int.end(),num);
        used_int.insert(iter,num);
        return 0;
    }
    double operator[](int pos)
    {
        init();
        int denominator = 1;
        int numerator = 0;

        for (int i = 1;i <= pos;i++)
        {
            numerator = get_next_int();
            denominator = numerator + i;
            add(denominator);

            if (numerator * 1.0 / denominator > max_numerator * 1.0 / max_denominator)
            {
                max_numerator = numerator;
                max_denominator = denominator;
            }
        }
        cout << "第" << pos <<"项:" << numerator << "/" << denominator << endl;
        cout << "max:" << max_numerator << "/" << max_denominator << endl;
        return 0;
    }
protected:
    typedef deque<int> DeqInt;
    typedef list<int> ListInt;

    ListInt used_int;
    int offset;

    int max_denominator;
    int max_numerator;
private:
};
int main()
{
    FractionalExpr frac;
    frac[3];
    return 0;
}