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

Question

Я написал простую программу для расчета максимального числа раз, когда квадратный корень может быть вычислен по числу, входные данные представляют собой интервал от num1 до num2 например: если входное значение равно (1,20), ответ равен 2, поскольку квадратный корень из 16 равен 4, а квадратный корень из 4 равен 2.

 int max = 0;
    for (int i = num1; i <= num2; i++) {
        boolean loop = true;
        int count = 0;
        int current = i;
        if (i == 1) {
            count++;
        } else {
            while (loop) {
                double squareRoot = Math.sqrt(current);
                if (isCurrentNumberPerfectSquare(squareRoot)) {
                    count++;
                    current = (int) squareRoot;
                } else {
                    loop = false;
                }
            }
        }

        if (count > max) {
            max = count;
        }
    }
    return max;


static boolean isCurrentNumberPerfectSquare(double number) {
    return ((number - floor(number)) == 0);
}

Я получил ответ, но было интересно, можно ли это улучшить математическим путем? Есть предложения?

Answer 1

Редактировать 4: для более оптимального подхода проверьте мой другой ответ.Я просто оставляю это здесь, если кто-то хочет попытаться следовать моему мыслительному процессу;)

---

Редактировать 3: использовать простые числа неправильно, вместо этого используйте наименьший неидеальный квадрат. Пример [35,37]

Редактировать 2: Теперь, когда я думаю об этом, есть еще лучший подход, особенно если вы предполагаете, что num1 и num2 охватывают больший диапазон.

Начните с самого низкого простого числа «Неидеальный квадрат» и рассчитайте максимальный идеальный квадрат, который вписывается в ваш диапазон.

Если вы его нашли, все готово.Если нет, продолжите со следующего простого числа 'неидеальный квадрат'.

---

В качестве примера, который достаточно хорошо работает для небольших диапазонов:

Я думаю, вы можетеулучшить внешнюю петлю.Нет необходимости проверять каждое число.

Если вы знаете наименьший идеальный квадрат, вы можете просто перейти к следующему идеальному квадрату в последовательности.

Например: [16, 26]

16 -> 4 -> 2 ==> 2 perfect squares
No neeed to test 17 to 24
25 -> 5 ==> 1 perfect square

и так далее ...

@ Chrisvin Jem Ваше предположение неверно, см. Пример выше

Редактировать: Добавлен некоторый код

    static int countPerfectSquares(int current) {

       int count = 0;

       while (true) {
            double squareRoot = Math.sqrt(current);
            if (isCurrentNumberPerfectSquare(squareRoot)) {
                count++;
                current = (int) squareRoot;
            } else {
               return count;
            }
        }
    }

    static boolean isCurrentNumberPerfectSquare(double number) {
        return ((number - Math.floor(number)) == 0);
    }

    static int numPerfectSquares(int num1, int num2) {

        int max = 0;
        if (num1 == 1) {
            max = 1;
        }

        int sqr = Math.max(2, (int) Math.floor(Math.sqrt(num1)));

        int current = (int) Math.pow(sqr, 2);
        if (current < num1) {
            current = (int) Math.pow(++sqr, 2);
        }

        while (current <= num2) {
            max = Math.max(countPerfectSquares(current), max);
            current = (int) Math.pow(++sqr, 2);
        }

        return max;
    }

Answer 2

Во избежание путаницы здесь мой окончательный ответ на эту тему. Сочетание обоих ранее упомянутых подходов.

То, что ищет «Парамесвар», - это самый большой совершенный квадрат, образованный самой низкой базой.

Step 1 -
To get that calculate the largest possible perfect square based on your num2 value.
If it is outside your range, you have no perfect square within.

Step 2 -
If it is within your range, you have to check all perfect square formed by a lower base value with a higher number of times.

Step 3 -
If you find one that is within your range, replace your result with the new result and proceed to check lower values. (go back to Step 2)

Step 4 -
Once the value you check is <= 2 you have already found the answer.

Вот несколько примеров реализации:

    static class Result {
        int base;
        int times;
    }

    static boolean isCurrentNumberPerfectSquare(double number) {
        return ((number - Math.floor(number)) == 0);
    }

    private static int perfectSquare(int base, int times) {

        int value = base;
        for (int i = times; i > 0; i--) {
            value = (int) Math.pow(base, 2);
        }
        return value;
    }

    private static Result calculatePerfectSquare(int perfectSquare) {

        Result result = new Result();
        result.base = (int) Math.sqrt(perfectSquare);
        result.times = 1;

        while (result.base > 2 && isCurrentNumberPerfectSquare(Math.sqrt(result.base))) {
            result.base = (int) Math.sqrt(result.base);
            result.times += 1;
        }

        System.out.println(perfectSquare + " -> " + result.base + " ^ " + result.times);
        return result;
    }

    static int maxPerfectSquares(int num1, int num2) {

        int largestPerfectSqr = (int) Math.pow(Math.floor(Math.sqrt(num2)), 2);
        if (largestPerfectSqr < num1) {
            return 0;
        }

        Result result = calculatePerfectSquare(largestPerfectSqr);

        int currentValue = result.base;

        while (currentValue > 2) {

            // check lower based values
            currentValue--;

            int newValue = perfectSquare(currentValue, result.times + 1);
            if (newValue >= num1 && newValue < num2) {

                result = calculatePerfectSquare(newValue);
                currentValue = result.base;
            }
        }

        return result.times;
    }

Answer 3

Редактировать - Мое предположение неверно.Обратитесь к ответу, предоставленному «вторым».

---

Вы можете удалить внешний цикл, num2 может быть непосредственно использован для определения числа с максимальным количеством рекурсивных квадратных корней.

requiredNumber = square (floor (sqrt (num2))));

Вам просто нужно проверить, существует ли обязательный Number в диапазоне [num1, num2] после его нахождения.

Таким образом, код рефакторинга будет выглядеть примерно так:

int requiredNumber = Math.pow(floor(Math.sqrt(num2)),2);
int numberOfTimes=0;
if(requiredNumber>=num1) {
    if (requiredNumber == 1) {
        numberOfTimes=1;
    } else{
        while (isCurrentNumberPerfectSquare(requiredNumber)) {
            numberOfTimes++;
        } 
    }
}