Диапазон целых чисел содержит по крайней мере один полный квадрат?

1. получить квадратный корень из меньшего числа и округлить его
2. получить квадратный корень из большего числа и округлить его в меньшую сторону
3. , если 1 меньше или равно 2, будет быть точным квадратом

Если вы согласитесь вычислять два квадратных корня, из-за его монотонности у вас есть это неравенство, которое эквивалентно вашему исходному:

sqrt(a) <= n < sqrt(b)

таким образом, если floor (sqrt (a))! = Floor (sqrt ( b)) , floor (sqrt (b)) - 1 гарантированно будет таким n .

Найдите интеграл от sqrt(a) и sqrt(b), скажем sa и sb.

Если sa² = a, то выведите yes.

Если sb² = b и sa = sb-1, то выведите "нет".

Если sa < sb, то выведите "да".

Иначе выведите "нет".

Вы можете оптимизировать вышесказанное, чтобы избавиться от вычисления sqrt(b) (аналогично ответу JDunkerly).

Или вы хотите избежать вычисления квадратных корней из a и b?

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

Вы начинаете с угадывания n, n = 1 и вычисляете n²

Рассмотрим, что если a <= n < b, то можно остановиться.

Если n < a < b, вы удваиваете угаданное n. если a < b < n, то приближаете его к среднему значению текущей + предыдущей догадки.

Это займет O(logb) времени.

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

Получите квадратный корень из меньшего числа. Если это целое число, то все готово. В противном случае округлите число и возведите в квадрат. Если это меньше, чем b, значит, это правда.

Таким способом вам нужно вычислить только один квадратный корень.

Чтобы избежать проблемы, когда a равно b, вы должны сначала проверить это. Поскольку этот случай всегда ложный.

Почему вы надеетесь полностью избежать использования квадратных корней? Еще до того, как вы подошли к наиболее эффективному способу решения этой проблемы, вы видели методы, требующие всего 2 квадратных корня. Это делается за O (1) раз, поэтому мне кажется, что любое улучшение, которое вы могли бы надеяться сделать, потребовало бы больше времени, чтобы подумать, чем оно КОГДА-ЛИБО сэкономило бы ваше вычислительное время. Я не прав?

Один из способов - использовать метод Ньютона для нахождения целочисленного квадратного корня для b . Затем вы можете проверить, попадает ли это число в диапазон. Я сомневаюсь, что это быстрее, чем простой вызов функции извлечения квадратного корня, но, безусловно, интереснее:

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}