Цепные дроби, например журнал Квант №1 1970

Доброе время суток!
Долго и безрезультатно искал более-менее оптимальный алгоритм решения следующей проблемы:
есть число double, необходимо перевести его десятичную дробь, причем максимальное количество знаков в знаменателе зафиксировано.
То есть пусть у нас реальное значение = 0.337792642140468 (это приблизительно значение дроби 101/299).
Если кол-во знаков задано равным 1, то результат должен быть 1/3
2 — 25/74
3 и более — 101/299

Подскажите пожалуйста как решаеться такая задача без полного перебора.
Заранее спасибо

Здравствуйте, Mystic, Вы писали:

M>Цепные дроби, например журнал Квант №1 1970

Большое спасибо

Здравствуйте, _skv_, Вы писали:

__>Доброе время суток!
__>Долго и безрезультатно искал более-менее оптимальный алгоритм решения следующей проблемы:
__>есть число double, необходимо перевести его десятичную дробь, причем максимальное количество знаков в знаменателе зафиксировано.
__>То есть пусть у нас реальное значение = 0.337792642140468 (это приблизительно значение дроби 101/299).
__>Если кол-во знаков задано равным 1, то результат должен быть 1/3
__>2 — 25/74
__>3 и более — 101/299

#include <cfloat>
#include <iostream>
#include <cmath>

int main()
{
    int Max = 100; // 10^2
    double x0 = 0.337792642140468;
    int p0 = 0;
    int q0 = 1;
    int p = 0;
    int q = 1;
    while (p < Max && q < Max)
    {
        double x = double(p) / double(q);
        if (std::fabs(x0 - x) < std::fabs(x0 - double(p0) / double(q0)))
        {
            p0 = p;
            q0 = q;
        }
        if (x < x0)
            ++p;
        else
            ++q;
    }
    std::cout << p0 << "/" << q0 << std::endl;
    return 0;
}

__>Подскажите пожалуйста как решаеться такая задача без полного перебора.
Сложность O(Max), где Max — максимально допустимое значение числителя и знаменателя (10, 100, 1000, ...).