Sprawdź, czy liczba jest idealnym kwadratem

Odpowiedzi:

117

Problem z poleganiem na dowolnym obliczeniu zmiennoprzecinkowym ( math.sqrt(x)lub x**0.5) polega na tym, że nie można być naprawdę pewnym, że jest dokładny (dla wystarczająco dużych liczb całkowitych xnie będzie, a może nawet przepełnienie). Na szczęście (jeśli się nie spieszy ;-) istnieje wiele podejść czystych liczb całkowitych, takich jak następujące ...:

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)

Wskazówka: jest oparty na „algorytmie babilońskim” dla pierwiastka kwadratowego, patrz wikipedia . To robi pracy w dowolnym liczbę dodatnią, dla których masz wystarczająco dużo pamięci do obliczeń, aby przejść do końca ;-).

Edycja : zobaczmy przykład ...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

to drukuje zgodnie z życzeniem (i też w rozsądnym czasie ;-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

Proszę, zanim zaproponujesz rozwiązania oparte na pośrednich wynikach zmiennoprzecinkowych, upewnij się, że działają one poprawnie na tym prostym przykładzie - nie jest to takie trudne (potrzebujesz tylko kilku dodatkowych kontroli na wypadek, gdyby obliczony sqrt był trochę wyłączony), po prostu bierze trochę troski.

A potem spróbuj x**7i znajdź sprytny sposób na obejście problemu,

OverflowError: long int too large to convert to float

oczywiście będziesz musiał stawać się coraz bardziej sprytny w miarę wzrostu liczby.

Gdybym był w pośpiechu, oczywiście, będę używać gmpy - ale potem, jestem wyraźnie tendencyjne ;-).

>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0

Tak, wiem, to po prostu takie proste, że czuję się jak oszukiwanie (trochę tak, jak ogólnie czuję do Pythona ;-) - w ogóle nie ma sprytu, po prostu idealna bezpośredniość i prostota (aw przypadku gmpy, czysta szybkość ; -) ...

Alex Martelli
źródło
Powiedz, co chcesz o autorze, gmpy brzmi jak świetne narzędzie do tego zadania.
Mike Graham
3
Metoda babilońska działa dobrze, ale musisz mieć specjalne przypadki dla 0 i 1, aby uniknąć dzielenia przez zero.
mpenkov
2
Nawiasem mówiąc, set([x])={x}
Oscar Mederos
6
Czy to nie jest setzabójstwo? Czy język babiloński nie zbiega się po prostu do tego int(sqrt(x)), gdzie musimy tylko sprawdzić, czy prev != next?
Tomasz Gandor
1
„Wiem, to po prostu takie proste, że czuję się jak zdrada (trochę tak, jak ogólnie czuję się w stosunku do Pythona”. Bardzo prawda;)
Arulx Z
38

Użyj metody Newtona, aby szybko wyzerować najbliższy pierwiastek kwadratowy z liczby całkowitej, a następnie podnieść go do kwadratu i sprawdzić, czy to twoja liczba. Zobacz isqrt .

Python ≥ 3,8 ma math.isqrt. Jeśli używasz starszej wersji Pythona, poszukaj def isqrt(n)implementacji " " tutaj .

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2
Prezydent James K. Polk
źródło
20

Ponieważ nigdy nie możesz polegać na dokładnych porównaniach, gdy mamy do czynienia z obliczeniami zmiennoprzecinkowymi (takimi jak te sposoby obliczania pierwiastka kwadratowego), implementacja mniej podatna na błędy byłaby

import math

def is_square(integer):
    root = math.sqrt(integer)
    return integer == int(root + 0.5) ** 2

Wyobraź sobie, że integerjest 9. math.sqrt(9)może być 3.0, ale może to być coś w rodzaju 2.99999lub 3.00001, więc natychmiastowe podniesienie wyniku do kwadratu nie jest wiarygodne. Wiedząc, że intprzyjmuje wartość minimalną, zwiększając wartość zmiennoprzecinkową, 0.5najpierw otrzymamy wartość, której szukamy, jeśli znajdujemy się w zakresie, w którym floatnadal ma wystarczająco dobrą rozdzielczość, aby przedstawić liczby zbliżone do tej, której szukamy .

Mike Graham
źródło
5
Byłoby nieco lepiej, if int(root + 0.5) ** 2 == integer:gdyby intdziałał tak, jak floorw przypadku liczb, na których nam zależy.
David Johnstone,
@David Johnstone, zmieniłem ten post, aby użyć tej implementacji, która, zgadzam się, jest ładniejsza niż stary sposób, jaki miałem. W każdym razie niektóre inne techniki, o których wspominają inni, są jeszcze lepsze i bardziej niezawodne.
Mike Graham
Rozumiem, że FP jest przybliżona, ale czy math.sqrt(9)naprawdę może być kiedykolwiek 2.99999? Python floatodwzorowuje na C double, ale myślę, że nawet 16-bitowy typ FP ma większą precyzję, więc może gdybyś miał kompilator C, który używał 8-bitowego FP („minifloats”) jako swojego doubletypu? Przypuszczam, że jest to technicznie możliwe, ale wydaje mi się mało prawdopodobne, aby tak było na każdym komputerze z Pythonem.
Ken
@Ken, powiedziałem „coś w rodzaju”, aby wskazać, że doszedłem do podstawowej koncepcji; nie ma gwarancji, że otrzymana wartość nie będzie nieco mniejsza niż dokładna wartość. Nie mogę sobie wyobrazić, że math.sqrt(9)powróci 2.99999w jakimkolwiek konkretnym systemie, ale rzeczywisty wynik jest zależny od systemu i nie można oczekiwać, że będzie dokładny.
Mike Graham
1
Ta funkcja jest nieprawidłowa w przypadku dużego kwadratu, takiego jak 152415789666209426002111556165263283035677489.
Acumenus
12

Jeśli jesteś zainteresowany, mam czysto matematyczną odpowiedź na podobne pytanie w matematycznej wymianie stosów: „Wykrywanie doskonałych kwadratów szybciej niż przez wyodrębnianie pierwiastka kwadratowego” .

Moja własna implementacja isSquare (n) może nie być najlepsza, ale mi się podoba. Zajęło mi kilka miesięcy nauki teorii matematyki, obliczeń cyfrowych i programowania w Pythonie, porównywanie się z innymi autorami itp., Aby naprawdę kliknąć tę metodę. Podoba mi się jednak jego prostota i skuteczność. Nie widziałem lepszego. Powiedz mi co myślisz.

def isSquare(n):
    ## Trivial checks
    if type(n) != int:  ## integer
        return False
    if n < 0:      ## positivity
        return False
    if n == 0:      ## 0 pass
        return True

    ## Reduction by powers of 4 with bit-logic
    while n&3 == 0:    
        n=n>>2

    ## Simple bit-logic test. All perfect squares, in binary,
    ## end in 001, when powers of 4 are factored out.
    if n&7 != 1:
        return False

    if n==1:
        return True  ## is power of 4, or even power of 2


    ## Simple modulo equivalency test
    c = n%10
    if c in {3, 7}:
        return False  ## Not 1,4,5,6,9 in mod 10
    if n % 7 in {3, 5, 6}:
        return False  ## Not 1,2,4 mod 7
    if n % 9 in {2,3,5,6,8}:
        return False  
    if n % 13 in {2,5,6,7,8,11}:
        return False  

    ## Other patterns
    if c == 5:  ## if it ends in a 5
        if (n//10)%10 != 2:
            return False    ## then it must end in 25
        if (n//100)%10 not in {0,2,6}: 
            return False    ## and in 025, 225, or 625
        if (n//100)%10 == 6:
            if (n//1000)%10 not in {0,5}:
                return False    ## that is, 0625 or 5625
    else:
        if (n//10)%4 != 0:
            return False    ## (4k)*10 + (1,9)


    ## Babylonian Algorithm. Finding the integer square root.
    ## Root extraction.
    s = (len(str(n))-1) // 2
    x = (10**s) * 4

    A = {x, n}
    while x * x != n:
        x = (x + (n // x)) >> 1
        if x in A:
            return False
        A.add(x)
    return True

Całkiem proste. Najpierw sprawdza, czy mamy liczbę całkowitą, a do tego dodatnią. W przeciwnym razie nie ma sensu. Pozwala 0 prześlizgnąć się jako True (konieczny lub następny blok to nieskończona pętla).

Następny blok kodu systematycznie usuwa potęgi 4 w bardzo szybkim pod-algorytmie wykorzystującym przesunięcie bitów i operacje logiki bitowej. Ostatecznie nie znajdujemy isSquare naszego pierwotnego n, ale k <n, który został przeskalowany potęgami 4, jeśli to możliwe. Zmniejsza to rozmiar liczby, z którą pracujemy i naprawdę przyspiesza metodę babilońską, ale także przyspiesza inne kontrole.

Trzeci blok kodu wykonuje prosty test logiki bitowej. Dwójkowo najmniej znaczące cyfry dowolnego doskonałego kwadratu to 001. Zawsze. Poza zerami wiodącymi wynikającymi zresztą z potęg 4, które zostały już uwzględnione. Jeśli nie przejdzie testu, od razu wiesz, że to nie jest kwadrat. Jeśli to minie, nie możesz być pewien.

Ponadto, jeśli otrzymamy 1 dla wartości testowej, wtedy liczba testowa była pierwotnie potęgą 4, w tym być może 1.

Podobnie jak trzeci blok, czwarty testuje wartość jednomiejscową w systemie dziesiętnym przy użyciu prostego operatora modułu i ma tendencję do wychwytywania wartości, które prześlizgnęły się przez poprzedni test. Również test mod 7, mod 8, mod 9 i mod 13.

Piąty blok kodu sprawdza niektóre z dobrze znanych doskonałych wzorców kwadratowych. Liczby kończące się na 1 lub 9 są poprzedzone wielokrotnością czterech. A liczby kończące się na 5 muszą kończyć się na 5625, 0625, 225 lub 025. Dodałem inne, ale zdałem sobie sprawę, że są one zbędne lub nigdy nie zostały użyte.

Wreszcie, szósty blok kodu bardzo przypomina to, co odpowiada najpopularniejszy odpowiadający - Alex Martelli -. Zasadniczo znajduje pierwiastek kwadratowy za pomocą starożytnego algorytmu babilońskiego, ale ogranicza go do wartości całkowitych, ignorując zmiennoprzecinkowe. Sporządzono zarówno ze względu na szybkość, jak i rozszerzenie wielkości wartości, które można testować. Użyłem zestawów zamiast list, ponieważ zajmuje to znacznie mniej czasu, użyłem przesunięć bitowych zamiast dzielenia przez dwa i sprytnie wybrałem początkową wartość początkową znacznie wydajniej.

Nawiasem mówiąc, przetestowałem zalecany numer testu Alexa Martellego, a także kilka liczb o wiele rzędów wielkości większych, takich jak:

x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
    print(i, isSquare(i))

wydrukował następujące wyniki:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

I zrobiło to w 0,33 sekundy.

Moim zdaniem mój algorytm działa tak samo jak algorytm Alexa Martellego, ze wszystkimi jego zaletami, ale ma dodatkową zaletę wysoce wydajnych odrzutów prostych testów, które oszczędzają dużo czasu, nie wspominając o zmniejszeniu rozmiaru liczb testowych o potęgi 4, co poprawia szybkość, wydajność, dokładność i rozmiar liczb, które można testować. Prawdopodobnie szczególnie prawdziwe w implementacjach innych niż Python.

Około 99% wszystkich liczb całkowitych jest odrzucanych jako niekwadratowe, zanim babilońskie wyodrębnianie pierwiastków zostanie wdrożone, a za 2/3 czasu babilońskiemu zajęłoby odrzucenie liczby całkowitej. I chociaż testy te nie przyspieszają znacząco procesu, to redukcja wszystkich liczb testowych do nieparzystej liczby przez podzielenie wszystkich potęg 4 naprawdę przyspiesza test babiloński.

Zrobiłem test porównania czasu. Przetestowałem kolejno wszystkie liczby całkowite od 1 do 10 milionów. Używając samej metody babilońskiej (z moim specjalnie dostosowanym początkowym przypuszczeniem), Surface 3 zajęło mi średnio 165 sekund (ze 100% dokładnością). Używając tylko testów logicznych w moim algorytmie (z wyjątkiem babilońskiego), zajęło to 127 sekund, odrzucił 99% wszystkich liczb całkowitych jako niekwadratowe, nie odrzucając przez pomyłkę żadnych doskonałych kwadratów. Spośród tych liczb całkowitych, które przeszły, tylko 3% było idealnymi kwadratami (znacznie większa gęstość). Używając powyższego pełnego algorytmu, który wykorzystuje zarówno testy logiczne, jak i ekstrakcję korzeni babilońskich, mamy 100% dokładność i zakończenie testu w zaledwie 14 sekund. Testowanie pierwszych 100 milionów liczb całkowitych zajmuje około 2 minut i 45 sekund.

EDYCJA: Udało mi się skrócić czas dalej. Mogę teraz przetestować liczby całkowite od 0 do 100 milionów w ciągu 1 minuty i 40 sekund. Dużo czasu jest marnowane na sprawdzanie typu danych i ich pozytywności. Wyeliminuj pierwsze dwie kontrole i skrócę eksperyment o minutę. Należy założyć, że użytkownik jest wystarczająco inteligentny, aby wiedzieć, że negatywy i elementy pływające nie są idealnymi kwadratami.

CogitoErgoCogitoSum
źródło
Jeśli chodzi o prostotę, trudno przebić zaakceptowaną odpowiedź. Jeśli chodzi o wydajność, twój powinien być lepszy. Jestem sceptyczny co do wartości redukcji celu przez potęgi kwadratowe małych liczb pierwszych, ale obliczanie symboli jacobi dla małych liczb pierwszych powinno być wygraną. A im większe liczby, tym większa korzyść dla tej odpowiedzi.
Prezydent James K. Polk
1
Redukcja przez potęgi małych liczb pierwszych jest niezbędna, aby obliczenia symboli Jacobiego zapewniły deterministyczne wyniki. W przeciwnym razie jest w najlepszym przypadku probabilistyczna lub deterministyczna dla niekwadratowości, ale nie weryfikuje prostokątności. To częściowo dlatego faktoryzuję według potęg kwadratów; jedyne symbole jacobi, które obliczam, dotyczą tych samych małych liczb pierwszych, które uwzględniam. Robię to również po to, aby zmniejszyć rozmiar numeru testowego, aby metoda babilońska użyta później była nieco szybsza (ale jest to dyskusyjne).
CogitoErgoCogitoSum
Cóż, z pewnością jest to dobra i wyjątkowa odpowiedź i jeśli będę miał trochę czasu w przyszłości, chciałbym się tym pobawić, wypróbuj czasy zmieniające liczbę małych liczb pierwszych, aby zobaczyć, czy można znaleźć optymalną liczbę przy danej wielkości bitu .
Prezydent James K. Polk
Jak najbardziej, przetestuj mój kod. Złam to. Nie jestem programistą z zawodu, jestem magistrem matematyki. Python to tylko hobby. Byłbym ciekawy, czy jest średnio wydajniejszy.
CogitoErgoCogitoSum
1
Jeśli nadal zainteresowany jest zasadniczo duplikat pytanie tutaj z ciekawych odpowiedzi, zwłaszcza odpowiedź A.Rex użytkownika .
Prezydent James K. Polk
12
import math

def is_square(n):
    sqrt = math.sqrt(n)
    return (sqrt - int(sqrt)) == 0

Idealny kwadrat to liczba, którą można wyrazić jako iloczyn dwóch równych liczb całkowitych. math.sqrt(number)powrót a float. int(math.sqrt(number))rzutuje wynik do int.

Jeśli pierwiastek kwadratowy jest liczbą całkowitą, na przykład 3, to math.sqrt(number) - int(math.sqrt(number))będzie 0, a ifinstrukcja będzie False. Jeśli pierwiastek kwadratowy byłby liczbą rzeczywistą, taką jak 3,2, to będzie Truei wypisuje "to nie jest idealny kwadrat".

Błąd w przypadku dużego elementu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

0xPwn
źródło
Zmiana if (math.sqrt(number)-int(math.sqrt(number))):do a=math.sqrt(number)ówczesnego inną linię dla: if a-int(a):. Dzieje się tak, ponieważ wystarczy tylko raz obliczyć pierwiastek kwadratowy, który imo dla dużego n jest znaczący
unseen_rider
@JamesKPolk Dlaczego tak jest?
user1717828
Jestem całkiem pewien, że sqrt - int (sqrt) jest identyczne z sqrt% 1. Twoja cała funkcja mogłaby po prostu zwrócić math.sqrt (n)% 1 == 0
CogitoErgoCogitoSum
6

Moja odpowiedź brzmi:

def is_square(x):
    return x**.5 % 1 == 0

Zasadniczo wykonuje pierwiastek kwadratowy, a następnie modulo o 1, aby usunąć część całkowitą, a jeśli wynik jest równy 0, w Trueprzeciwnym razie zwróć False. W tym przypadku x może być dowolną dużą liczbą, tylko nie tak dużą, jak maksymalna liczba zmiennoprzecinkowa obsługiwana przez Pythona: 1.7976931348623157e + 308

Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

Lasagnenator
źródło
5

Można to rozwiązać za pomocą decimalmodułu, aby uzyskać dowolną dokładność pierwiastków kwadratowych i łatwo sprawdzić „dokładność”:

import math
from decimal import localcontext, Context, Inexact

def is_perfect_square(x):
    # If you want to allow negative squares, then set x = abs(x) instead
    if x < 0:
        return False

    # Create localized, default context so flags and traps unset
    with localcontext(Context()) as ctx:
        # Set a precision sufficient to represent x exactly; `x or 1` avoids
        # math domain error for log10 when x is 0
        ctx.prec = math.ceil(math.log10(x or 1)) + 1  # Wrap ceil call in int() on Py2
        # Compute integer square root; don't even store result, just setting flags
        ctx.sqrt(x).to_integral_exact()
        # If previous line couldn't represent square root as exact int, sets Inexact flag
        return not ctx.flags[Inexact]

Do demonstracji z naprawdę dużymi wartościami:

# I just kept mashing the numpad for awhile :-)
>>> base = 100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324
>>> sqr = base ** 2
>>> sqr ** 0.5  # Too large to use floating point math
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float

>>> is_perfect_power(sqr)
True
>>> is_perfect_power(sqr-1)
False
>>> is_perfect_power(sqr+1)
False

Jeśli zwiększysz rozmiar testowanej wartości, w końcu stanie się to raczej powolne (zajmuje blisko sekundy w przypadku kwadratu 200 000 bitów), ale w przypadku bardziej umiarkowanych liczb (powiedzmy 200 000 bitów) jest to nadal szybsze niż człowiek zauważył indywidualne wartości (~ 33 ms na moim komputerze). Ale ponieważ szybkość nie była Twoim głównym zmartwieniem, jest to dobry sposób na zrobienie tego ze standardowymi bibliotekami Pythona.

Oczywiście byłoby znacznie szybciej w użyciu gmpy2i po prostu testowaniu gmpy2.mpz(x).is_square(), ale jeśli pakiety innych firm nie są twoją rzeczą, powyższe działa całkiem dobrze.

ShadowRanger
źródło
5

Właśnie opublikowałem niewielką zmianę niektórych z powyższych przykładów w innym wątku ( Znajdowanie idealnych kwadratów ) i pomyślałem, że uwzględnię niewielką zmianę tego, co tutaj zamieściłem (używając nsqrt jako zmiennej tymczasowej), na wypadek, gdyby było to interesujące / posługiwać się:

import math

def is_square(n):
  if not (isinstance(n, int) and (n >= 0)):
    return False 
  else:
    nsqrt = math.sqrt(n)
    return nsqrt == math.trunc(nsqrt)

Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

spryt
źródło
2

To jest moja metoda:

def is_square(n) -> bool:
    return int(n**0.5)**2 == int(n)

Weź pierwiastek kwadratowy z liczby. Konwertuj na liczbę całkowitą. Weź kwadrat. Jeśli liczby są równe, w przeciwnym razie jest to doskonały kwadrat.

Jest to nieprawidłowe w przypadku dużego kwadratu, takiego jak 152415789666209426002111556165263283035677489.

Archu Sm
źródło
Nie działa dla liczb ujemnych, ale nadal jest świetnym rozwiązaniem!
Rick M.
1

Możesz wyszukiwać binarnie za zaokrąglony pierwiastek kwadratowy. Wyrównaj wynik do kwadratu, aby sprawdzić, czy pasuje do oryginalnej wartości.

Prawdopodobnie lepiej ci będzie z odpowiedzią FogleBirds - choć uważaj, ponieważ arytmetyka zmiennoprzecinkowa jest przybliżona, co może zrzucić to podejście. Zasadniczo można uzyskać fałszywie dodatni wynik z dużej liczby całkowitej, która jest na przykład o jeden większa niż doskonały kwadrat, z powodu utraty precyzji.

Steve314
źródło
1

Jeśli moduł (reszta) pozostałość po podzieleniu przez pierwiastek kwadratowy wynosi 0, to jest to kwadrat doskonały.

def is_square(num: int) -> bool:
    return num % math.sqrt(num) == 0

Sprawdziłem to na liście doskonałych kwadratów dochodzących do 1000.

GeneralCode
źródło
0
  1. Zdecyduj, jak długo będzie to numer.
  2. weź deltę 0,000000000000 ....... 000001
  3. sprawdź, czy (sqrt (x)) ^ 2 - x jest większe / równe / mniejsze niż delta i zdecyduj na podstawie błędu delta.
Cezar Alexandru Vancea
źródło
0

Ta odpowiedź nie odnosi się do zadanego pytania, ale do niejawnego pytania, które widzę w opublikowanym przez Ciebie kodzie, tj. „Jak sprawdzić, czy coś jest liczbą całkowitą?”

Pierwsza odpowiedź na to pytanie brzmi: „Nie!” I prawdą jest, że w Pythonie sprawdzanie typów zwykle nie jest właściwe.

Jednak w przypadku tych rzadkich wyjątków zamiast szukać kropki dziesiętnej w ciągu reprezentującym liczbę, wystarczy użyć funkcji isinstance :

>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False

Oczywiście dotyczy to raczej zmiennej niż wartości. Gdybym chciał ustalić, czy wartość jest liczbą całkowitą, zrobiłbym to:

>>> x=5.0
>>> round(x) == x
True

Ale jak wszyscy szczegółowo omówili, istnieją kwestie zmiennoprzecinkowe, które należy wziąć pod uwagę w większości przykładów tego rodzaju rzeczy niebędących zabawkami.

Vicki Laidler
źródło
1
Co oznacza sformułowanie „dotyczy to zmiennej, a nie wartości”? Możesz bez problemu użyć round (5.0) == 5.0 i isinstance (x, int). (A OOWTDI ma po prostu wywołać x.is_integer ().)
Veky
0

Jeśli chcesz zapętlić zakres i zrobić coś dla każdej liczby, która NIE jest idealnym kwadratem, możesz zrobić coś takiego:

def non_squares(upper):
    next_square = 0
    diff = 1
    for i in range(0, upper):
        if i == next_square:
            next_square += diff
            diff += 2
            continue
        yield i

Jeśli chcesz zrobić coś dla każdej liczby, która JEST idealnym kwadratem, generator jest jeszcze łatwiejszy:

(n * n for n in range(upper))
Moberg
źródło
0

Myślę, że to działa i jest bardzo proste:

import math

def is_square(num):
    sqrt = math.sqrt(num)
    return sqrt == int(sqrt)

Jest to niepoprawne w przypadku dużego obiektu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

alejandro izquierdo
źródło
To jest to samo, co powyższa odpowiedź.
Kowalski
0

Wariant rozwiązania @Alex Martelli bez set

Kiedy x in seenjest True:

  • W większości przypadków jest to ostatnia dodana, np. 1022 daje xsekwencję 511, 256, 129, 68, 41, 32, 31 , 31 ;
  • W niektórych przypadkach (np. Dla poprzedników doskonałych kwadratów) jest to przedostatni dodany, np. 1023 daje 511, 256, 129, 68, 41, 32 , 31, 32 .

Dlatego wystarczy zatrzymać się, gdy tylko prąd xbędzie większy lub równy poprzedniemu:

def is_square(n):
    assert n > 1
    previous = n
    x = n // 2
    while x * x != n:
        x = (x + (n // x)) // 2
        if x >= previous:
            return False
        previous = x
    return True

x = 12345678987654321234567 ** 2
assert not is_square(x-1)
assert is_square(x)
assert not is_square(x+1)

Równoważność z oryginalnym algorytmem testowanym dla 1 <n <10 ** 7. W tym samym przedziale ten nieco prostszy wariant jest około 1,4 razy szybszy.

Aristide
źródło
0
a=int(input('enter any number'))
flag=0
for i in range(1,a):
    if a==i*i:
        print(a,'is perfect square number')
        flag=1
        break
if flag==1:
    pass
else:
    print(a,'is not perfect square number')
Pemba Tamang
źródło
Chociaż ten kod może rozwiązać problem, dobra odpowiedź powinna również wyjaśniać, co robi kod i jak pomaga.
BDL
0

Chodzi o to, aby uruchomić pętlę od i = 1 do floor (sqrt (n)), a następnie sprawdzić, czy podniesienie do kwadratu daje n.

bool isPerfectSquare(int n) 
{ 
    for (int i = 1; i * i <= n; i++) { 

        // If (i * i = n) 
        if ((n % i == 0) && (n / i == i)) { 
            return true; 
        } 
    } 
    return false; 
} 
Pragati Verma
źródło
-3
import math

def is_square(n):
    sqrt = math.sqrt(n)
    return sqrt == int(sqrt)

Błąd w przypadku dużego elementu innego niż kwadrat, takiego jak 152415789666209426002111556165263283035677490.

Ravi Sankar Raju
źródło
2
To jest tylko kod odpowiedzi. Proszę podać trochę uzasadnienia.
hotzst
Nie możesz zrozumieć, jak przedrzeć się przez to @hotzst? To ma sens i nie jestem nawet ekspertem w Pythonie. Nie jest to najlepszy test, ale jest ważny zarówno w teorii, jak i w małych przypadkach.
CogitoErgoCogitoSum
1
@CogitoErgoCogitoSum: Nie rozumiesz. Odpowiedzi zawierające tylko kod nie są wyszukiwane za pomocą wyszukiwarek, takich jak Google. Nie ma znaczenia, czy można zrozumieć odpowiedź.
Prezydent James K. Polk