Найдите наименьшее целое число, которое при умножении на известное двойное число даст целое число - PullRequest
Новая
       53

Найдите наименьшее целое число, которое при умножении на известное двойное число даст целое число

0 голосов
/ 29 марта 2019

У меня двойной ввод "а". Моя цель - найти целое число «b», такое, что «a * b» даст целое число плюс некоторое допустимое количество ошибок. Например, «100.227273 * 22 = 2205 (+ 0,000006 ошибка)», где я хочу найти ответ «22».

Я уже изучил этот пост , но я только частично понимаю верхний ответ. Я мог бы действительно использовать некоторую помощь при создании алгоритма, который выполняет эту задачу. У меня есть код ниже, который работает для некоторых случаев, но не для всех. 

    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, просто чтобы назвать пару из бесконечности. Пожалуйста, помогите мне выяснить, что не так с моим кодом, или приведите пример кода, который даст желаемый результат. Спасибо!

1 Ответ

2 голосов
/ 29 марта 2019

Вот пример реализации метода, описанного в связанном вопросе.Если итеративно вычислять новые коэффициенты продолженной дроби.При этом он проверяет, дает ли восстановленное число желаемую точность.И если это так, он возвращает знаменатель восстановленной дроби как результат 

// 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
...