Проверка, является ли число квадратом целого числа
Учитывая целое число, определите, является ли оно квадратным числом:
В математике квадратное число или идеальный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя.
Примеры: -1: False, 0: True, 25 True | CodeWars
Первый вариант решения проходит все тесты, но не проходит по времени:
Второй вариант не проходит 3 теста (на 3, 26 и секретный):
Почему второй вариант не проходит данные тесты?
Нужен вариант, который занимает мало времени (не попадёт под ошибку Execution Timed Out (12000 ms) , а также не используются библиотеки.
Нет смысла делать цикл до n . Это примерно 100500 лишних операций в среднем. Если n равно 10001, то получится 9900 лишних итераций, ведь квадрат любого числа больше 100 уже больше 10000, так зачем их проверять. Нужно делать цикл до квадратного корня из n
Прибавление 1 позволяет убрать первую проверку на 0. Так что мы эту проверку лучше заменим на проверку отрицательных чисел:
Простейшее быстрое решение для любого целого числа — двоичный поиск для получения целой части квадратного корня и прямая проверка что его квадрат равен исходному числу:
Приведу, как ответ, так как часто сам сталкиваюсь с таким в задачах, а в комментариях именно этого способа не вижу. Хотя, если у вас случай именно для простого возведения в степень, то здесь вариант ниже не поможет. А вот в ряде схожих случаев будет просто необходим. Спасибо @CrazyElf за очень ценный комментарий к первому варианту ответа.
Использование оператора возведения в степень ** и деления по модулю % (а они часто используются вместе, при хэшировании, например) обычно затратно по времени при больших числах. В этом случае лучше использовать встроенную функцию pow .
К примеру, в случае возведения трехзначного числа в трехзначную степень ** ещё работает быстрее, чем pow , а вот для четырехзначных — уже наооброт. См. пример ниже сделанный на моем (далеко не самом новом) ноуте.
Особо важно это при всевозможных множественных применениях возведения в степень в программе, включая рекурсивные и т.д., т.е. при большом числе таких операций.
Проверьте, является ли число полным квадратом
Как я мог проверить, является ли число полным квадратом?
Скорость не вызывает беспокойства, на данный момент, просто работая.
7 ответов
Проблема с тем, чтобы полагаться на любые вычисления с плавающей запятой ( math.sqrt(x) , или x**0.5 ) в том, что вы не можете быть уверены в их точности (для достаточно больших целых чисел x они не будут точными, и даже могут переполниться). К счастью (если не торопиться;-) существует множество чисто целочисленных подходов, таких как следующий.
Подсказка: он основан на «вавилонском алгоритме» для квадратного корня, смотрите википедию. Он работает для любого положительного числа, для которого у вас достаточно памяти для завершения вычислений;-).
Edit: давайте посмотрим пример.
это печатает, как надо (и за разумное время тоже;-):
Пожалуйста, прежде чем предлагать решения, основанные на промежуточных результатах с плавающей запятой, убедитесь, что они работают правильно на этом простом примере — это не так сложно (вам просто нужно несколько дополнительных проверок на случай, если вычисленный sqrt будет немного не таким), просто нужно немного внимательности.
А затем попробуйте с x**7 и найдите умный способ обойти проблему, которую вы получите,
вам придется становиться все умнее и умнее по мере роста чисел, конечно.
Если бы я спешил, конечно, я бы использовал gmpy — но тогда, я явно предвзят;-).
Да, я знаю, это настолько просто, что кажется жульничеством (немного похоже на то, как я отношусь к Python в целом;-) — никакой заумности, только идеальная прямота и простота (и, в случае с gmpy, чистая скорость;-)).
Python — проверьте, является ли число квадратом
Я уверен, что этот код работает. Но когда я делал тестовые примеры, например: test.expect( is_square( 4)) , он говорит, что это не то, что ожидалось.
Ваша функция фактически не работает, так как она немедленно возвращает False на первый найденный неквадратичный корень. Вместо этого вы захотите изменить свой код:
так что он возвращает false только после проверки всех возможных квадратных корней. Вы также можете посмотреть в math.sqrt() и float.is_integer() . Используя эти методы, ваша функция станет такой:
Имейте в виду, что этот метод не будет работать с очень большими числами, но ваш метод будет очень медленным с ними, поэтому вам придется выбирать, что использовать. Надеюсь, я помог!
Python-сообщество
Написал функцию, но проблема в том, что при извлечении квадратного корня из числа, результат принимает вид “2.0” и проверка функцией isinstance показывает, что это число не целое. Не пойму как решить проблему с этой точкой?
#2 Июнь 18, 2022 16:22:21
Функция, проверяющая является ли число квадратом целого числа
Онлайн
#3 Июнь 19, 2022 07:53:33
Функция, проверяющая является ли число квадратом целого числа
Никак вы ее не решите. Результат извлечения корня это действительное число. В целое оно превратится только округлением. Но округлить можно любое действительное число.
Вам надо полностью менять алгоритм. воспользуйтесь тем что произведение целых целое число.