Приближённое сокращение дроби.

У меня возник вопрос, который не могу решить сам.
Суть такова, есть несократимая дробь (числитель/знаменатель), нужно сделать так, что бы числитель и знаменатель был не более чем заданное число и при этом, итоговое дробное число было как можно ближе к изначальному. На данный момент я целочисленно делю и числитель и знаменатель на 2 до тех пор(сокращая дробь по возможости), пока не будет достигнута нужная разрядность, но подозреваю, что это не самое точное решение. Если есть какие-то уже известные методики, то приветствуется любая информация.

Насколько данная операция критична по времени?
Насколько велики исходные значения числителя и знаменателя?

Цитата KIA @ 16.03.16, 05:39

У меня возник вопрос, который не могу решить сам.
Суть такова, есть несократимая дробь (числитель/знаменатель), нужно сделать так, что бы числитель и знаменатель был не более чем заданное число и при этом, итоговое дробное число было как можно ближе к изначальному. На данный момент я целочисленно делю и числитель и знаменатель на 2 до тех пор(сокращая дробь по возможости), пока не будет достигнута нужная разрядность, но подозреваю, что это не самое точное решение. Если есть какие-то уже известные методики, то приветствуется любая информация.

Не все дроби могут удовлетворять "заданному числу". Ибо может получится дробь 0/число.
Ну а методу я бы изобрел следующую, на примере ...

Пусть дано:
 
Дробь - 17/33
"Заданное число" - 3
 
int(17/3)=5
int(33/3)=11 <--- выбираем большее (11>5)
 
int(17/11)       1
------------ =  ----
int(33/11)       3

Или я не так понял задачу?

Добавлено 16.03.16, 06:53

Цитата JoeUser @ 16.03.16, 06:50

пока не будет достигнута нужная разрядность

Если все же "заданное число" - это разрядность, тогда используем для "первого деления" степень основания системы исчисления.

Воспользуйся аналогом двоичного поиска, только вместо середины отрезка бери медианту.

Добавлено 16.03.16, 06:55

Цитата JoeUser @ 16.03.16, 06:50

Ну а методу я бы изобрел следующую, на примере ...

И на твоём же примере это не работает К 17/33 ближе 2/3, а не 1/3.

Цитата JoeUser @ 16.03.16, 06:50

методу я бы изобрел следующую, на примере ...

Ну и сбойнула твоя метода - 2/3 ближе к исходнику.

Разделить числитель и знаменатель на число K (не обязательно целое) и округлить. K подбираем так, чтобы новые числитель и знаменатель удовлетворяли ограничению.

Цитата

Дробь - 17/33

"Заданное число" - 3

K=11 получим 2(1,5454545454545454545454545454545)/3

Сообщение отредактировано: Pavlovsky - 16.03.16, 07:03

OpenGL, Akina, да - согласен, неувязочка Точность хромает.

Цитата JoeUser @ 16.03.16, 07:02

Точность хромает.

Да в озвученных тобой условиях правильным ответом вообще является 1/2. То, что в результате значения числителя и знаменателя ограничены заданным значением, не запрещает им быть меньше этого предела.

Цитата Pavlovsky @ 16.03.16, 07:01

Разделить числитель и знаменатель на число K (не обязательно целое) и округлить. K подбираем так, чтобы новые числитель и знаменатель удовлетворяли ограничению.

Это не будет работать если числитель или знаменатель требуемого числа будут строго меньше ограничения. Например, для 2/7 и ограничения 6 ответ 1/4, а твоим алгоритмом - 1/3.

Добавлено 16.03.16, 07:14

Цитата Akina @ 16.03.16, 07:10

Да в озвученных тобой условиях правильным ответом вообще является 1/2.

Ха. А я-то и не заметил этого

KIA
Цепные дроби решают твою задачу оптимальным образом:

Цитата

подходящая дробь Pn/Qn является наилучшим приближением для x среди всех дробей, знаменатель которых не превосходит Qn;

Добавлено 16.03.16, 08:12
P.S. Только тебе надо уйти от начального рационального числа в сторону на небольшую величину, чтобы получить вещественное число, которое будешь приближать. То есть вместо m/n надо приближать m/n + eps, где eps подбирать экспериментально. Иначе цепная дробь быстро выродится, если число рациональное.

Цитата OpenGL @ 16.03.16, 07:13

Например, для 2/7 и ограничения 6 ответ 1/4, а твоим алгоритмом - 1/3.

1/3 (отклонение 1/21) на совсем чуть-чуть хуже чем 1/4 (отклонение 1/28).

Цитата Pavlovsky @ 16.03.16, 08:33

1/3 (отклонение 1/21) на совсем чуть-чуть хуже чем 1/4 (отклонение 1/28).

Это "чуть-чуть" можно довести до большой величины. Собственно, пример JoeUser это как раз иллюстрирует.

А где у нас топикстартер? или ему уже всё по барабану?

Цитата OpenGL @ 16.03.16, 08:52

Это "чуть-чуть" можно довести до большой величины.

Чем больше значение ограничения, чуть-чуть превратится совсем в мизерные значения.

Народ, а как вам такое:



Если я ниче не напутал с арифметикой, то останется только умножить числитель и знаменатель на нужную степень десятки, и отсечь дробную часть. Точность конечно теряется, но на пятом знаке после запятой. Че скажите, или опять шило?