задачка интересная... но кроме написания специализированной функции для вычисления корней из целых чисел в голову ничего не приходит
что-нибудь вроде этого:
| Код |
bool IsSquare(unsigned int x)
{
usnigned int RootLow=0;
unsigned int RootDelta=x/2;
while(RootDelta>0)
{
unsigned int temp=RootLow+RootDelta;
if(temp*temp<=x)
RootLow=temp;
RootDelta/=2;
}
return (x==SquareLow);
}
|
сразу говорю - не проверял
идея такая: ищем корень двоичным поиском
RootLow - левая граница отрезка
RootDelta - половина длины отрезка
на каждом шагу сравниваем RootLow+RootDelta и sqrt(x)
если меньше - выбираем левый полуотрезок, больше - правый
чтобы выбрать левый - просто делим RootDelta на 2
правый - добавляем RootDelta к RootLow, и опять делим RootDelta пополам
дальше - пользуемся тем что, y<sqrt(x) - то же самое, что y*y<x
таким образом подходим все ближе к корню из x снизу
превысить его мы не можем
если в конце дошли до него - значит, корень целый, если нет - значит нет...
по идее, долго функция работать не должна - максимум 31 проход по циклу
кроме того, за верхнюю оценку корня из x здесь взято само x
можно смело брать x/2, что уменьшит количество проходов на 1
или вообще в начале проверить x>2^16 и в этом случае за оценку взять x/2^8, что уменьшит количество проходов на 8, т.е. на четверть - тоже неплохо...
конечно, можно было городить что-то более сложное, чтобы получить более хорошую оценку, но не факт, что оно стоит того, т.к. тело цикла вычислительно очень простое, а предварительная проверка должна занимать меньше времени, чем она экономит, чтобы было выгодно ее делать...
Добавлено @ 00:20
а вот это, кстати, - опасно
если input будет 2^30, число благополучно выйдет за пределы unsigned int
насколько я понял, изначально в задаче нужно определить, можно ли представить число k в виде n*(n+1)/2
тогда лучше такую задачу и решать, чтобы было поменьше мороки с опасностью выхода за границы диапазона
т.к. функция n*(n+1)/2 такая же монотонная, как и корень, предложенную функцию можно переделать для нее...
(только надо будет осторожно вычислять n*(n+1)/2 - сначала найти среди n и n+1 четное число, поделить его на 2, а уже потом перемножать, опять же на тот случай, если мы подойдем слишком близко к границе диапазона) |
