Maison  >  Article  >  développement back-end  >  Comment déterminer s'il s'agit d'un nombre carré parfait valide en PHP

Comment déterminer s'il s'agit d'un nombre carré parfait valide en PHP

醉折花枝作酒筹
醉折花枝作酒筹original
2021-07-13 16:00:011509parcourir

Étant donné un nombre entier positif num, écrivez une fonction qui renvoie True si num est un nombre carré parfait, sinon elle renvoie False. Que devons-nous faire à ce moment-là ? Aujourd'hui, l'éditeur vous le guidera et vous pourrez vous y référer si vous en avez besoin.

Comment déterminer s'il s'agit d'un nombre carré parfait valide en PHP

Étant donné un nombre entier positif num, écrivez une fonction qui renvoie True si num est un carré parfait et False sinon.

Remarque : N'utilisez aucune fonction de bibliothèque intégrée, telle que sqrt.

Exemple 1 :

输入:16
输出:True

Exemple 2 :

输入:14
输出:False

Idées de résolution de problèmes 1

php ne peut pas utiliser la fonction pow. L'opération est ** 0,5 La multiplication par 0,5 a le même effet que le numéro racine à partir de PHP5.6.0.

Code

class Solution {
    /** 
    * @param Integer $num 
    * @return Boolean 
    */
    function isPerfectSquare($num) {
        return $num**0.5 == (int)($num**0.5);
    }}

Idée de résolution de problèmes 2

Utilisez les propriétés des nombres carrés parfaits Un nombre carré parfait est la somme d'une série de nombres impairs. , par exemple :

1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
....
1+3+...+(2n-1) = (2n-1 + 1) n/2 = n* n
时间复杂度为 O(sqrt(n))。

Code

class Solution {
    /** 
    * @param Integer $num 
    * @return Boolean 
    */
    function isPerfectSquare($num) {
        $start = 1;
        while($num > 0)
        {
            $num -= $start;   // 累减到最后是 0 
            $start += 2;      // 每次 +2 保持是连续奇数
        }
        return $num == 0;
    }}

Idée de résolution de problèmes 3

Recherche binaire

Code

class Solution {
    /** 
    * @param Integer $num 
    * @return Boolean 
    */
    function isPerfectSquare($num) {
        $left = 0;
        $right = $num;
        while($left < $right)
        {
            $mid = $right - floor(($right-$left)/2);
            if ($mid * $mid == $num) {
                return true;
            } elseif ($mid * $mid > $num) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        return $left * $left == $num;
    }}

Apprentissage recommandé : tutoriel vidéo php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn