Здравствуйте, 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, ...).
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>