找到最小的整数，当乘以一个已知的 double 时，将产生一个整数

Question

我有一个双输入 "a"。我的目标是找到一个整数 "b" 使得 "a * b" 将产生一个整数，加上一些允许的误差量。例如“100.227273 * 22 = 2205 (+ 0.000006 error)”，我想找到的答案是“22”。

我已经研究过this post，但我只了解部分最佳答案。我真的需要一些帮助来创建完成此任务的算法。我在下面有一些代码适用于某些情况，但不是全部。

    private int FindSmallestMultiplier(double input)
    {
        int numerator = 1;
        int temp;
        double output = input;
        double invert = input;
        int denominator = 1;
        List<int> whole = new List<int>();
        double dec = input;
        int i = -1;
        while (Math.Abs(Math.Round(numerator * input)-numerator*input) > 0.001)
        {
            i = i + 1;
            //seperate out the whole and decimal portions of the input
            whole.Add(Convert.ToInt32(Math.Floor(invert)));
            dec = output - whole[i];
            //get the decimal portion of the input, and invert
            invert =  1 / dec;

            //create nested fraction to determine how far off from a whole integer we are
            denominator = 1;
            numerator = 1;
            for(int j = whole.Count-1; j >= 0; j--)
            {
                temp = whole[j] * denominator + numerator;
                numerator = denominator;
                denominator = temp;
            }
        }
        return numerator;
    }

上面的代码适用于许多输入情况，例如 0.3333、0.5。它不起作用的一个例子是 0.75 或 0.101，仅举出无穷大的一对。请帮我弄清楚我的代码有什么问题，或者提供一个可以产生预期结果的代码示例。谢谢！

Answer 1

这是链接问题中描述的方法的示例实现。 If 迭代计算连分数的新系数。这样做，它会检查重建的数字是否提供了所需的准确性。如果是这样，它 returns 重构分数的分母作为结果

// Reconstructs a fraction from a continued fraction with the given coefficients
static Tuple<int, int> ReconstructContinuedFraction(List<int> coefficients)
{
    int numerator = coefficients.Last();
    int denominator = 1;

    for(int i = coefficients.Count - 2; i >= 0; --i)
    {
        //swap numerator and denominator (= invert number)
        var temp = numerator;
        numerator = denominator;
        denominator = temp;

        numerator += denominator * coefficients[i];
    }
    return new Tuple<int, int>(numerator, denominator);
}

static int FindSmallestMultiplier(double input, double error)
{
    double remainingToRepresent = input;
    List<int> coefficients = new List<int>();
    while (true)
    {
        //calculate the next coefficient
        var integer = (int)Math.Floor(remainingToRepresent);                
        remainingToRepresent -= integer;
        remainingToRepresent = 1 / remainingToRepresent;
        coefficients.Add(integer);

        //check if we reached the desired accuracy
        var reconstructed = ReconstructContinuedFraction(coefficients);

        var multipliedInput = input * reconstructed.Item2;
        var multipliedInputRounded = Math.Round(multipliedInput);
        if (Math.Abs(multipliedInput - multipliedInputRounded) < error)
            return reconstructed.Item2;
    }
}

试图找到 Pi 的乘数的示例程序...

public static void Main()
{
    var number = Math.PI;
    var multiplier = FindSmallestMultiplier(number, 0.001);
    Console.WriteLine(number + " * " + multiplier + " = " + number * multiplier);

}

... 给出以下输出：

3.14159265358979 * 113 = 354.999969855647

找到最小的整数，当乘以一个已知的 double 时，将产生一个整数

Find the smallest integer that when multiplied by a known double, will produce an integer

c#

algorithm

math

fractions