计算某些界限内的最大有效分数

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

解决问题的规范方法是继续进行分数扩展.特别是,请参阅此部分.