找出最小的整数，该整数乘以已知的双精度数将产生一个整数 [英] Find the smallest integer that when multiplied by a known double, will produce an integer

问题描述

我有一个双输入 a。我的目标是找到一个整数 b，这样 a * b将产生一个整数，加上一些允许的误差。例如 100.227273 * 22 = 2205（+ 0.000006错误），我想找到的答案是 22。

I have a double input "a". My goal is to find an integer "b" such that "a * b" will produce an integer, plus some allowable amount of error. For example "100.227273 * 22 = 2205 (+ 0.000006 error)", where the answer I want to find is "22".

我已经研究过这篇文章，但我只部分了解最佳答案。我真的可以使用一些帮助来创建完成该任务的算法。我下面有一些适用于某些情况的代码，但不是全部。

I have already studdied this post, but I only partially understand the top answer. I could really use some help creating an algorithm that accomplishes this task. I have some code below that works for some cases, but not all.

    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，只是为了命名不定对。请帮助我弄清楚我的代码有什么问题，或者提供一个可以产生预期结果的代码示例。谢谢！

The code above works for many input cases, such as 0.3333, 0.5. An example of where it doesn't work is 0.75, or 0.101, just to name couple out of infinity. Please help me to figure out what is wrong with my code or provide a code example that will produce the desired result. Thank you!

推荐答案

以下是链接问题中所述方法的示例实现。如果迭代计算连续分数的新系数。这样做，它检查重构的数字是否达到所需的精度。如果是这样，它会返回重构分数的分母作为结果

Here is an example implementation of the method described in the linked question. If iteratively calculates new coefficients of the continued fraction. Doing so, it checks if the reconstructed number gives the desired accuracy. And if so, it returns the denominator of the reconstructed fraction as the result

// 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的乘数...

An example program that attempts to find the multiplier for Pi ...

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

}  

...给出以下输出：

... gives the following output:

3.14159265358979 * 113 = 354.999969855647

这篇关于找出最小的整数，该整数乘以已知的双精度数将产生一个整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！