Авторизация

Логин: Пароль:
Регистрация Забыли свой пароль?

Узнать, является ли число квадратом?

Страницы: 1
Узнать, является ли число квадратом?, быстро
#1
11.08.2010 00:18:43
Какой самый быстрый алгоритм для того, чтобы узнать, является ли данное целое число (достаточно большое) квадратом некоторого другого целого числа?
Accende lumen sensibus, infude ainorem corbidus!
 
 
#2
11.08.2010 00:19:44
извлечь корень и проверить целый он или нет?
 
 
#3
11.08.2010 00:21:44
Возможно, есть более оптимальные способы - не всегда нужно извлекать корень (можно посмотреть по остаткам от деления). Если есть еще какие-то эвристики, то можно максимально их использовать - извлечение корня все-таки не быстрое дело
Accende lumen sensibus, infude ainorem corbidus!
 
 
#4
11.08.2010 13:03:12
Я бы извлекал корень.
 
 
#5
14.08.2010 17:10:10
Проще действительно извлечь корень. Просто если расписывать число по разрядам, то не увидите был ли переход разрядов при умножении числа или нет. Не очень удобно и трудоемко получается, если просто делить на число. В принципе можно это попробовать, но это нужно каждый раз число делить ну скажем на все числа от 10 по 19, чтобы не пропустить моменты когда число делиться и на 10 и еще раз на 10 и может делиться и на 15 и еще раз на 15. Например 72900. Хотя можете выписать квадраты чисел от 11 по 19 и делить на них.
Изменено: Ольга Кабушева - 14.08.2010 17:12:07
 
 
#6
14.08.2010 19:52:02
сперва можно проверить на четность
если четно то извлекать корень и проверять остаток
 
 
#7
14.08.2010 20:10:57
Цитата
Frees пишет:
сперва можно проверить на четность

Точно уверены? 11^2=121. Нечетно. Четность в этом случае подразумевает, что корень может быть кратным 2 и то если число делиться на 4, а не на 2.
 
 
#8
14.08.2010 21:13:46
Цитата
Ольга Кабушева пишет:
Точно уверены

уже нет))) признаю глупость сказал....
 
 
#9
15.08.2010 01:00:17
Самый просто способ попробовать разложить на составляющие, но мне кажется он более трудоемкий, чем просто извлечение корня.
 
 
#10
28.08.2010 12:32:18
Можно использовать такой метод, однако насчет скорости не знаю:

Имеем входную данную: целое число a
1. s:=1;
2. h:=1;
3. Если s=a то, а - квадрат и выход.
4. Если s>a то, а - не квадрат и выход.
5. h:=h+2;
6. s:=s+h;

Достоверность алгоритма. Вообще этот алгоритм вычисляет сумму членов арифметической прогрессии, у которого первый элемент = 1, шаг = 2. Далее подставляем в формулу суммы арифметической прогрессии и мы получим квадрат, некого числа.
 
 
#11
16.10.2010 20:56:55
Цитата
Можно использовать такой метод, однако насчет скорости не знаю:
Имеем входную данную: целое число a
1. s:=1;
1. s:=1;
2. h:=1;
2. h:=1;
3. Если s=a то, а - квадрат и выход.
3. Если s=a то, а - квадрат и выход.
4. Если s>a то, а - не квадрат и выход.
4. Если s>a то, а - не квадрат и выход.
5. h:=h+2;
5. h:=h+2;
6. s:=s+h;
6. s:=s+h;


Это самый оптимальный вариант полностью согласен.
c:\linux\bin
c:\linux\etc\X11\xorg.conf
d:\home\user
Страшный сон линуксоида.
 
 
#12
18.10.2010 21:54:52
Я бы воспользовался извлечением корня
 
 
#13
19.10.2010 02:03:01
У нас число очень большое, этот алгоритм займет больше времени, чем просто извлечение корня. Либо же задавать начальные условия большие, а не равные 1. Но как их определить? Ведь число может быть разным. В итоге проще извлечь корень, чем изводить себя ожиданием, глядя на работу этого алгоритма.
 
 
#14
23.10.2010 20:48:39
Можно использовать рекурсивную формулу:
X(n+1)=1/2*(X(n)+A/X(n))
где X(0)=A
A-число, из которого надо извлечь корень.
Итерацию повторяем, пока Xn и X(n+1) не совпадут с точностью до целой части.
 
 
 
Страницы: 1
Читают тему (гостей: 1, пользователей: 0, из них скрытых: 0)