Я собираюсь реализовать приближение дроби Фарея для преобразования пользовательского ввода с ограниченной точностью в возможно повторяющиеся рациональные числа.
http://mathworld.wolfram.com/FareySequence.html
Я могу легко найти ближайшую фракцию Фэри в последовательности, и я могу найти Fn путем рекурсивного поиска фракций-посредников путем построения дерева Штерна-Броко.
http://mathworld.wolfram.com/Stern-BrocotTree.html
Однако, метод, который я придумал для нахождения дробей в последовательности Fn, кажется очень неэффективным:
(Псевдо)
For int i = 0 to fractions.count -2
{
if fractions[i].denominator + fractions[i+1].denominator < n
{
insert new fraction(
numerator = fractions[i].numerator + fractions[i+1].numerator
,denominator = fractions[i].denominator + fractions[i+1].denominator)
//note that fraction will reduce itself
addedAnElement = true
}
}
if addedAnElement
repeat
Я почти всегда буду определять последовательность Fn, где n = 10 ^ m, где m> 1
Так что, возможно, было бы лучше создать последовательность один раз и кэшировать ее ... но все равно кажется, что должен быть лучший способ ее получения.
EDIT:
Этот документ имеет многообещающий алгоритм:
http://www.math.harvard.edu/~corina/publications/farey.pdf
Я постараюсь реализовать.
Проблема в том, что их «наиболее эффективный» алгоритм требует знания двух предыдущих элементов. Я знаю, что первый элемент любой последовательности равен 1 / n, но поиск второго элемента кажется сложной задачей ...
EDIT2:
Я не уверен, как я упустил это из виду:
Дано F0 = 1 / n
Если x> 2, то
F1 = 1 / (n-1)
Поэтому для всех n> 2 первые две дроби всегда будут
1 / n, 1 / (n-1) и я могу реализовать решение от Патраску.
Итак, теперь мы, ответ на этот вопрос, должны доказать, что это решение является или не является оптимальным с помощью тестов.