Vérification d’un carré parfait
Il est possible d’effectuer une recherche binaire sur n’importe quelle liste ordonnée : cela peut être une liste de hauteurs classées par ordre croissant, de nombres entiers, de nombres à virgule flottante, etc. Cette technique peut même s’appliquer à l’ensemble des entiers , à l’ensemble des nombres naturels ou encore à l’ensemble des nombres rationnels . L’idée reste de choisir une plage de solutions potentielles, puis d’éliminer à chaque itération la partie inutile.
Challenge
Étant donné un entier positif
n, vous devez déterminer s’il s’agit d’un carré parfait, sans utiliser la fonction sqrt.Entrée
L’entrée contient un seul entier
n (2 ≤ n ≤ ).Sortie
Le programme doit afficher
Yes si n est un carré parfait, et No dans le cas contraire.Exemples
Entrée | Sortie |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Indice
Si
n est un carré parfait ⇒ il existe un autre nombre x tel que . Par conséquent, vous pouvez essayer de trouver x dans l’intervalle [1, 2, …, n].Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB