Занимательная математика

[spamsink]

Даны два различных положительных рациональных числа a/b и с/d; a/b < c/d.

Каков алгоритм нахождения числа m/n, такого, что a/b < m/n < c/d, и n минимально?

This entry was originally posted at https://spamsink.dreamwidth.org/1145147.html. Please comment there using OpenID.

Comments

[qehgt]

https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_within_an_interval

[spamsink]

Надо было мне скринить комментарии, а теперь чего уж...

[alexanderr]

особенно интересен частный случай, когда a/b=355/113, c/d=22/7

[alexanderr]

333/106 ?? или можно лучше?

[vitus_wagner]

Ну, во-первых, диапазон между 355/113 и 22/7 не интересен совершенно.
Во-вторых, 333/106 туда не попадает.
Вот диапазон между 333/106 и 355/113 - это и правда интересно.

[spamsink]

Делов-то.
333/106 = [3; 7, 15] = [3, 7, 15, +∞] ≈ 3.14151
355/113 = [3; 7, 16] = [3; 7, 15, 1] ≈ 3.14159

Итого, имеем [3; 7, 15, 2] = 688/219 ≈ 3.14155

[e2pii1]

Перебрать все n начиная с n=1