Как я мог проверить, является ли число полным квадратом?
Скорость не вызывает беспокойства, на данный момент, просто работая.
Проблема с тем, чтобы полагаться на любые вычисления с плавающей запятой (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, но вы можете сделать что-то вроде:
function isSquare(x) = x == floor(sqrt(x) + 0.5)^2
То есть взять число, найти квадратный корень, округлить его до ближайшего целого числа, возвести в квадрат и проверить, совпадает ли оно с исходным числом. (floor
и добавление 0.5
делается для предотвращения случаев, когда sqrt(4)
возвращает 1.9999999...
из-за математики с плавающей запятой, как заметил Майк Грэм.)
Если вам интересно, однажды было очень хорошее обсуждение Самого быстрого способа определить, является ли квадратный корень из целого числа целым числом.
Отредактировано для уточнения.
Поскольку вы никогда не можете полагаться на точные сравнения при работе с вычислениями с плавающей запятой (такими как эти способы вычисления квадратного корня), менее подверженной ошибкам реализация будет
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2
Представьте целое число
равно 9
. math.sqrt (9)
может быть 3.0
, но это также может быть что-то вроде 2.99999
или 3.00001
, поэтому результат возведен в квадрат. выкл. ненадежно. Зная, что int
принимает минимальное значение, увеличение значения с плавающей запятой на 0,5
в первую очередь означает, что мы получим искомое значение, если мы находимся в диапазоне, где float
по-прежнему имеет достаточно высокое разрешение, чтобы представлять числа, близкие к тому, которое мы ищем.
Воспользуйтесь методом Ньютона, чтобы быстро найти ближайший квадратный корень целого числа, затем возведите его в квадрат и посмотрите, является ли это вашим числом. См. isqrt .
Python ≥ 3.8 имеет math.isqrt
. Если вы используете старую версию Python, поищите реализацию « def isqrt (n)
» здесь .
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
Это ответ не относится к заданному вами вопросу, а относится к неявному вопросу, который я вижу в опубликованном вами коде, например, «как проверить, является ли что-то целым числом?»
Первый ответ, который вы обычно получите на этот вопрос это "Не надо!" И это правда, что в Python проверка типов обычно не является правильным занятием.
Однако для этих редких исключений вместо поиска десятичной точки в строковом представлении числа нужно использовать функцию isinstance :
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Конечно, это относится к переменная, а не значение. Если бы я хотел определить, является ли значение целым числом, я бы сделал следующее:
>>> x=5.0
>>> round(x) == x
True
Но, как все остальные подробно рассказали, есть проблемы с плавающей запятой, которые следует учитывать в большинстве неигровых примеры такого рода вещей.
Вы можете выполнить двоичный поиск округленного квадратного корня. Возведите результат в квадрат, чтобы увидеть, соответствует ли он исходному значению.
Вероятно, вам будет лучше с ответом FogleBirds - но будьте осторожны, поскольку арифметика с плавающей запятой является приблизительной, что может отбросить этот подход. В принципе, вы можете получить ложное срабатывание от большого целого числа, которое на единицу больше, чем полный квадрат, например, из-за потери точности.