Python — проверьте, является ли число квадратом
Я написал функцию, которая возвращает, является ли числовой ввод квадратом или нет.
Я уверен, что этот код работает. Но когда я выполнил тестовые примеры, например: test.expect( is_square( 4)) , он говорит, что значение не то, что ожидалось.
Вам следует протестировать свой код с помощью операторов print , прежде чем вы будете уверены, что ваш код работает.
13 ответов
Поскольку math.sqrt () возвращает число с плавающей запятой, мы можем преобразовать его в строку, отделив ее от «.» и проверьте, равна ли часть справа (десятичная дробь) 0.
import math def is_square(n): x= str(math.sqrt(n)).split(".")[1] #getting the floating part as a string. return True if(x=="0") else False Чтобы проверить, является ли число квадратом, вы можете использовать такой код:
import math number = 16 if math.sqrt(number).is_interger: print "Square" else: print "Not square" import math import — это модуль math .
if math.sqrt(number).is_interger: проверяет, является ли квадратный корень из number целым числом. Если так, это будет print Square . В противном случае это будет print Not square .
def myfunct(num): for i in range(0,num): if i*i==num: return 'square' else: return 'not square' Хотя этот код может ответить на вопрос, предоставление дополнительного контекста относительно как и почему он решает проблему, улучшило бы долгосрочную ценность ответа.
Самое простое рабочее решение, но не для большого количества.
def squaretest(num): sqlist=[] i=1 while i**2 В Python 3.8+ используйте это:
def is_square(n): root = math.isqrt(n) return n == root * root def is_square(n): tmp = int(n ** 0.5) return n == tmp * tmp print(is_square(81), is_square(67108864 ** 2 + 1)) # True False Чтобы придерживаться целочисленных алгоритмов, вы можете посмотреть на реализацию двоичного поиска для нахождения квадратного корня:
Вы можете просто использовать simpy module import it as,
from sympy.ntheory.primetest import is_square И вы можете проверить это число:
Он вернет логическое значение
Так и должно быть, но эта библиотечная функция, в дополнение к ее загадочному и нелогичному местоположению (она не должна быть в «приметесте»), является ужасным вирусом: помимо бесконечных int() и as_int() преобразований, он проходит через sympy.core.power.integer_nthroot , который, несмотря на свое имя, использует арифметику с плавающей запятой в isqrt_small_python , вызываемую sqrtrem_python . и посмотрите на код там.
Я думаю, что лучше всего использовать только «встроенную» целочисленную арифметику:
def issquare(n): return math.isqrt(n)**2==n (Квадраты x**2 априори вычисляются более эффективно, чем произведения x*x. )
Согласно моим таймингам, это (по крайней мере до ~ 10^8) быстрее, чем sympy.numtheory.primetest.is_square .
(Я использую другое имя, чтобы было легче сравнивать их.) Последний сначала использует некоторые модульные проверки, которые должны значительно ускорить его, но у него так много накладных расходов на преобразование и тестирование ( int , as_int , квадраты становятся n-ми степенями с n = 2, целые числа преобразуется из «маленьких» в целые числа с высокой точностью и обратно. ), что все преимущество теряется. После множества тестов он примерно делает вышеописанное, используя ntheory.nthroot, что опять-таки является излишеством: предназначено для любого n-го корня, квадратный корень — это всего лишь один частный случай, и noting оптимизирован для этого случая. Некоторые подпрограммы даже выполняют очень странные арифметические операции с плавающей запятой, включая умножение на 1.0000000001 и тому подобные ужасы. Однажды я получил следующее ужасное сообщение об ошибке: (Исходный вывод содержит полный путь "C:\Users\Username\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\" вместо каждого ". " ниже. )
File ". \sympy\ntheory\primetest.py", line 112, in is_square return integer_nthroot(n, 2)[1] File ". \sympy\core\power.py", line 86, in integer_nthroot return _integer_nthroot_python(y, n) File ". \sympy\core\power.py", line 94, in _integer_nthroot_python x, rem = mpmath_sqrtrem(y) File ". \mpmath\libmp\libintmath.py", line 284, in sqrtrem_python y = isqrt_small_python(x) File ". \mpmath\libmp\libintmath.py", line 217, in isqrt_small_python r = int(x**0.5 * 1.00000000000001) + 1 KeyboardInterrupt Это дает хорошее представление о бездне, в которую безнадежно тонет sympy is_square .
Python - проверьте, является ли число квадратом
Я уверен, что этот код работает. Но когда я делал тестовые примеры, например: test.expect( is_square( 4)) , он говорит, что это не то, что ожидалось.
Ваша функция фактически не работает, так как она немедленно возвращает False на первый найденный неквадратичный корень. Вместо этого вы захотите изменить свой код:
def is_square(n):
if n return False
else:
for i in range(int(n/2)+1):
if (i*i)==n:
return True
return False
так что он возвращает false только после проверки всех возможных квадратных корней. Вы также можете посмотреть в math.sqrt() и float.is_integer() . Используя эти методы, ваша функция станет такой:
from math import sqrtdef is_square(n):
return sqrt(n).is_integer()
Имейте в виду, что этот метод не будет работать с очень большими числами, но ваш метод будет очень медленным с ними, поэтому вам придется выбирать, что использовать. Надеюсь, я помог!
Чтобы придерживаться целочисленных алгоритмов, вы можете посмотреть на реализацию бинарного поиска для поиска квадратного корня:
def is_square(n):
if n < 0:
return False
if n == 0:
return True
x, y = 1, n
while x + 1 < y:
mid = (x+y)//2
if mid**2 < n:
x = mid
else:
y = mid
return n == x**2 or n == (x+1)**2
Основная идея философии Python - написать простой код. Чтобы проверить, является ли число идеальным квадратом:
def is_square(n):
return n**0.5 == int(n**0.5)
Проверьте, является ли число полным квадратом
Как я мог проверить, является ли число полным квадратом?
Скорость не вызывает беспокойства, на данный момент, просто работая.
7 ответов
Проблема с тем, чтобы полагаться на любые вычисления с плавающей запятой ( math.sqrt(x) , или x**0.5 ) в том, что вы не можете быть уверены в их точности (для достаточно больших целых чисел x они не будут точными, и даже могут переполниться). К счастью (если не торопиться;-) существует множество чисто целочисленных подходов, таких как следующий.
def is_square(apositiveint): x = apositiveint // 2 seen = set([x]) while x * x != apositiveint: x = (x + (apositiveint // x)) // 2 if x in seen: return False seen.add(x) return True for i in range(110, 130): print i, is_square(i) Подсказка: он основан на "вавилонском алгоритме" для квадратного корня, смотрите википедию. Он работает для любого положительного числа, для которого у вас достаточно памяти для завершения вычислений;-).
Edit: давайте посмотрим пример.
x = 12345678987654321234567 ** 2 for i in range(x, x+2): print i, is_square(i) это печатает, как надо (и за разумное время тоже;-):
152415789666209426002111556165263283035677489 True 152415789666209426002111556165263283035677490 False Пожалуйста, прежде чем предлагать решения, основанные на промежуточных результатах с плавающей запятой, убедитесь, что они работают правильно на этом простом примере - это не так сложно (вам просто нужно несколько дополнительных проверок на случай, если вычисленный sqrt будет немного не таким), просто нужно немного внимательности.
А затем попробуйте с x**7 и найдите умный способ обойти проблему, которую вы получите,
OverflowError: long int too large to convert to float вам придется становиться все умнее и умнее по мере роста чисел, конечно.
Если бы я спешил, конечно, я бы использовал gmpy - но тогда, я явно предвзят;-).
>>> import gmpy >>> gmpy.is_square(x**7) 1 >>> gmpy.is_square(x**7 + 1) 0 Да, я знаю, это настолько просто, что кажется жульничеством (немного похоже на то, как я отношусь к Python в целом;-) -- никакой заумности, только идеальная прямота и простота (и, в случае с gmpy, чистая скорость;-)).
Python - Проверьте, является ли число квадратом
Я уверен, что этот код работает. Но когда я сделал тестовые примеры, пример: test.expect( is_square( 4)) , это говорит о том, что значение не то, что ожидалось.
14 ответов
Ваша функция на самом деле не работает, так как она немедленно вернет False при первом найденном неквадратном корне. Вместо этого вы захотите изменить свой код так:
так что он возвращает false только после того, как все возможные квадратные корни были проверены. Вы также можете посмотреть в math.sqrt() а также float.is_integer() , Используя эти методы, ваша функция станет такой:
from math import sqrt def is_square(n): return sqrt(n).is_integer() Имейте в виду, что этот метод не будет работать с очень большими числами, но ваш метод будет очень медленным с ними, поэтому вам придется выбирать, какой использовать. Надеюсь, я помог!
Чтобы придерживаться целочисленных алгоритмов, вы можете взглянуть на реализацию двоичного поиска для нахождения квадратного корня:
Основная идея философии Python - написать простой код. Чтобы проверить, является ли число идеальным квадратом:
def is_square(n): return n**0.5 == int(n**0.5) При включении поплавка вы можете найти корень числа.
В Python 3.8+ используйте это:
def is_square(n): root = math.isqrt(n) return n == root * root Вы можете просто использовать simpy module import it as,
from sympy.ntheory.primetest import is_square и вы можете проверить такой номер:
Он вернет логическое значение
Я думаю, что лучше всего использовать только «встроенную» целочисленную арифметику:
def issquare(n): return math.isqrt(n)**2==n (Квадраты x**2 априори вычисляются более эффективно, чем произведения x*x. )
Согласно моим таймингам, это (по крайней мере, до ~ 10 ^ 8) быстрее, чем sympy.numtheory.primetest.is_square .
(Я использую другое имя, чтобы было проще сравнивать их.) Последний сначала использует некоторые модульные проверки, которые должны значительно ускорить его, но у него так много накладных расходов на преобразование и тестирование ( int , as_int , квадраты становятся n-ми степенями с n=2, целые числа преобразуются из «маленьких» в целые с множественной точностью и обратно, . ), что все преимущество теряется. После множества тестов он примерно делает вышеописанное, используя ntheory.nthroot, что опять-таки является излишеством: предназначено для любого n-го корня, квадратный корень — это всего лишь один частный случай, и noting оптимизирован для этого случая. Некоторые подпрограммы там даже выполняют очень странные арифметические операции с плавающей запятой, включая умножение на 1.0000000001 и тому подобные ужасы. Однажды я получил следующее ужасное сообщение об ошибке: (исходный вывод имеет полный путь "C:\Users\Username\AppData\Local\Packages\PythonSoftwareFoundation.Python.3.9_qbz5n2kfra8p0\LocalCache\local-packages\Python39\site-packages\" вместо каждого ". " ниже. )
File ". \sympy\ntheory\primetest.py", line 112, in is_square return integer_nthroot(n, 2)[1] File ". \sympy\core\power.py", line 86, in integer_nthroot return _integer_nthroot_python(y, n) File ". \sympy\core\power.py", line 94, in _integer_nthroot_python x, rem = mpmath_sqrtrem(y) File ". \mpmath\libmp\libintmath.py", line 284, in sqrtrem_python y = isqrt_small_python(x) File ". \mpmath\libmp\libintmath.py", line 217, in isqrt_small_python r = int(x**0.5 * 1.00000000000001) + 1 KeyboardInterrupt Это дает хорошее представление о бездне, в которую sympy безнадежно тонет.