Python — проверьте, является ли число квадратом
Я уверен, что этот код работает. Но когда я делал тестовые примеры, например: test.expect( is_square( 4)) , он говорит, что это не то, что ожидалось.
Ваша функция фактически не работает, так как она немедленно возвращает False на первый найденный неквадратичный корень. Вместо этого вы захотите изменить свой код:
так что он возвращает false только после проверки всех возможных квадратных корней. Вы также можете посмотреть в math.sqrt() и float.is_integer() . Используя эти методы, ваша функция станет такой:
Имейте в виду, что этот метод не будет работать с очень большими числами, но ваш метод будет очень медленным с ними, поэтому вам придется выбирать, что использовать. Надеюсь, я помог!
Проверка, является ли число квадратом целого числа
Учитывая целое число, определите, является ли оно квадратным числом:
В математике квадратное число или идеальный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя.
Примеры: -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 , а вот для четырехзначных — уже наооброт. См. пример ниже сделанный на моем (далеко не самом новом) ноуте.
Особо важно это при всевозможных множественных применениях возведения в степень в программе, включая рекурсивные и т.д., т.е. при большом числе таких операций.
Проверить, является ли число полным квадратом
Учитывая положительное число, проверьте, является ли оно идеальным квадратом, не используя встроенную библиотечную функцию. Полный квадрат — это число, являющееся квадратом целого числа.
Input: n = 25
Output: true
Explanation: 25 is a perfect square since it can be written as 5×5.
Input: n = 20
Output: false
Explanation: 20 is not the product of an integer with itself.
1. Использование свойства Perfect Square
Каждый совершенный квадрат удовлетворяет тому свойству, что он представляет собой сумму нечетных чисел, начинающихся с единицы. Например,
Мы можем использовать это свойство, чтобы определить, является ли число n совершенный квадрат или нет. Идея состоит в том, чтобы многократно вычитать нечетные числа из n , начиная с 1, пока не станет 0 или отрицательным. Если значение достигает 0 в какой-то момент, мы можем сказать, что число является идеальным квадратом. Однако, если значение становится отрицательным, не достигая 0, число не может быть идеальным квадратом. Это показано ниже на C++, Java и Python.
Проверьте, является ли число полным квадратом
Как я мог проверить, является ли число полным квадратом?
Скорость не вызывает беспокойства, на данный момент, просто работая.
7 ответов
Проблема с тем, чтобы полагаться на любые вычисления с плавающей запятой ( math.sqrt(x) , или x**0.5 ) в том, что вы не можете быть уверены в их точности (для достаточно больших целых чисел x они не будут точными, и даже могут переполниться). К счастью (если не торопиться;-) существует множество чисто целочисленных подходов, таких как следующий.
Подсказка: он основан на «вавилонском алгоритме» для квадратного корня, смотрите википедию. Он работает для любого положительного числа, для которого у вас достаточно памяти для завершения вычислений;-).
Edit: давайте посмотрим пример.
это печатает, как надо (и за разумное время тоже;-):
Пожалуйста, прежде чем предлагать решения, основанные на промежуточных результатах с плавающей запятой, убедитесь, что они работают правильно на этом простом примере — это не так сложно (вам просто нужно несколько дополнительных проверок на случай, если вычисленный sqrt будет немного не таким), просто нужно немного внимательности.
А затем попробуйте с x**7 и найдите умный способ обойти проблему, которую вы получите,
вам придется становиться все умнее и умнее по мере роста чисел, конечно.
Если бы я спешил, конечно, я бы использовал gmpy — но тогда, я явно предвзят;-).
Да, я знаю, это настолько просто, что кажется жульничеством (немного похоже на то, как я отношусь к Python в целом;-) — никакой заумности, только идеальная прямота и простота (и, в случае с gmpy, чистая скорость;-)).