Überprüfung auf eine Quadratzahl
Eine Binärsuche lässt sich auf jede beliebige sortierte Liste anwenden – sei es eine Liste mit aufsteigenden Höhen, ganzen Zahlen, Gleitkommazahlen etc. Sogar die Menge der ganzen Zahlen , die Menge der natürlichen Zahlen oder die Menge der rationalen Zahlen kann dafür herangezogen werden. Dabei wählen wir in jeder Iteration einen möglichen Wertebereich aus und verwerfen den Teil, den wir nicht mehr benötigen.
Herausforderung
Gegeben ist eine positive ganze Zahl
n. Die Aufgabe besteht darin, zu überprüfen, ob n eine Quadratzahl ist, ohne dabei die Funktion sqrt zu verwenden.Eingabe
Die Eingabe besteht aus einer einzelnen ganzen Zahl
n (2 ≤ n ≤ ).Ausgabe
Das Programm soll
Yes ausgeben, wenn n eine Quadratzahl ist, und No andernfalls.Beispiele
Eingabe | Ausgabe |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Tipp
Wenn
n eine Quadratzahl ist ⇒ es gibt eine Zahl x, sodass . Daher kann man versuchen, x im Bereich [1, 2, …, n] zu finden.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB