c# - 计算某些范围内的最大有理分数

Question

我正在尝试在只接受整数买价/卖价的市场上进行与精确汇率匹配的货币交易。我想以特定的汇率进行尽可能多的交易。这是一个玩具程序，不是真正的交易机器人，所以我使用的是 C#。

我需要一种算法，即使分子和分母可能很大(100000+)，也能在合理的时间内返回答案。

static bool CalcBiggestRationalFraction(float target_real, float epsilon, int numerator_max, int denominator_max, out int numerator, out int denominator)
{
    // target_real is the ratio we are tryig to achieve in our output fraction (numerator / denominator)
    // epsilon is the largest difference abs(target_real - (numerator / denominator)) we are willing to tolerate in the answer
    // numerator_max, denominator_max are the upper bounds on the numerator and the denominator in the answer
    //
    // in the case where there are multiple answers, we want to return the largest one
    //
    // in the case where an answer is found that is within epsilon, we return true and the answer.
    // in the case where an answer is not found that is within epsilon, we return false and the closest answer that we have found.
    //
    // ex: CalcBiggestRationalFraction(.5, .001, 4, 4, num, denom) returns (2/4) instead of (1/2).


}

在我思考之前，我问了一个类似的问题 (http://stackoverflow.com/questions/4385580/finding-the-closest-integer-fraction-to-a-given-random-real)实际上是在尝试完成，结果证明我正在尝试解决一个不同但相关的问题。

Answer 1

解决问题的规范方法是使用 continued fraction expansion .特别是，参见 this section .