Проверьте, является ли число полным квадратом
Как я мог проверить, является ли число полным квадратом?
Скорость не вызывает беспокойства, на данный момент, просто работая.
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, но вы можете сделать что-то вроде:
function isSquare(x) = x == floor(sqrt(x) + 0.5)^2
То есть взять число, найти квадратный корень, округлить его до ближайшего целого числа, возвести в квадрат и проверить, совпадает ли оно с исходным числом. (floor и добавление 0.5 делается для предотвращения случаев, когда sqrt(4) возвращает 1.9999999... из-за математики с плавающей запятой, как заметил Майк Грэм.)
Если вам интересно, однажды было очень хорошее обсуждение Самого быстрого способа определить, является ли квадратный корень из целого числа целым числом.
Отредактировано для уточнения.
- Решите, как долго будет номер.
- возьмите дельту 0,000000000000 ....... 000001
- посмотрите, если (sqrt (x)) ^ 2 - x больше / равно / меньше дельты, и решите на основе ошибки дельты.
Поскольку вы никогда не можете полагаться на точные сравнения при работе с вычислениями с плавающей запятой (такими как эти способы вычисления квадратного корня), менее подверженной ошибкам реализация будет
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 - но будьте осторожны, поскольку арифметика с плавающей запятой является приблизительной, что может отбросить этот подход. В принципе, вы можете получить ложное срабатывание от большого целого числа, которое на единицу больше, чем полный квадрат, например, из-за потери точности.