![]() |
Модераторы: Daevaorn |
![]() ![]() ![]() |
|
MOP |
|
||||
![]() Новичок Профиль Группа: Участник Сообщений: 17 Регистрация: 28.8.2005 Репутация: нет Всего: нет |
не обязательно извлекать...
нужно только знать, извлекается ли целый квадратный корень из целого неотрицательного числа... срочно... ------------------------------------------------------------------------------------------------- Дополнение: вообщем проблема вот в чем:
вывод:
с числами по-меньше - никаких проблем... такое только с большими получается, что квадратный корни двух разных!!! чисел - одинаковы. может кто что подскажет.... Это сообщение отредактировал(а) MOP - 31.8.2005, 17:56 |
||||
|
|||||
Mayk |
|
|||
![]() ^аВаТаР^ сообщение>> ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: 45 Всего: 134 |
Ну если число относительно мелкое(допустим, в районе миллиона), то можно разложить на множители через заране построенную таблицу простых чисел.
Очевидно, что если корень извлекается, то при разложении получится что-то типа a*a*b*b*b*b*c*c(a,b,c - простые), а корень будет a*b*b*c. Ещё у нас где-то была у нас темка по извлечению корней из целых чисел... Вот она: http://forum.vingrad.ru/index.php?showtopic=54722. Посмотри, может там что полезное найдешь. -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
MOP |
|
|||
![]() Новичок Профиль Группа: Участник Сообщений: 17 Регистрация: 28.8.2005 Репутация: нет Всего: нет |
объясню, зачем мне это надо...
решал я одну задачку : http://acm.timus.ru/problem.aspx?space=1&num=1209 по ходу решил её (на листочке). все правильно, ошибок нет, если решать на калькуляторе. в общем мое решение свелось к тому, что нужно определить является ли арифметический квадратный корень из (8*k-7) целым числом. если целое, то на k-той позиции - единица, если дробное - ноль. (если кому интересно решение - пишите - выложу). на листочке - все правильно... но когда пытаюсь решить с помощью С++ - тонет на больших числах... вот код:
подскажите плз, как еще можно узнать вычисляется ли из числа корень... |
|||
|
||||
maxim1000 |
|
||||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 17 Всего: 110 |
задачка интересная... но кроме написания специализированной функции для вычисления корней из целых чисел в голову ничего не приходит
что-нибудь вроде этого:
сразу говорю - не проверял идея такая: ищем корень двоичным поиском 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, а уже потом перемножать, опять же на тот случай, если мы подойдем слишком близко к границе диапазона) -------------------- qqq |
||||
|
|||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 17 Всего: 110 |
ага... вот я сам себя и поймал...
если x будет большим, то на первой же итерации произойдет нечто ужасное: temp будет равен x/2 при вычислении его квадрата произойдет переполнение... так что более точная оценка снизу все-таки нужна сделать ее можно вообще по-простому: считаем количество значащих разрядов x - пусть это будет m значит x<2^(m+1) значит хорошей оценкой сверху будет (int)sqrt(2^(m+1)) можно, конечно, считать эти оценки в процессе, но лучше посчитать их на обычном калькуляторе и занести в таблицу, чтобы не терять времени на вычисления (а то ведь при нечетных (m+1) корень придется действительно вычислять)... Добавлено @ 00:33 P.S.ну и наследил я тут ![]() -------------------- qqq |
|||
|
||||
Mayk |
|
||||
![]() ^аВаТаР^ сообщение>> ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: 45 Всего: 134 |
Бери Ньютона, он рулит. http://algolist.manual.ru/maths/count_fast/intsqrt.php все лонги замени на long long'и или даже на long double. Или возьми BigInteger'ы (реализация там же есть).
угу, интересно. ps. Лучше использовать логические операции. То есть примерно так: char pow10[32]; bitArray[0]= 11010010; bitArray[1]= 00100010; Ну и так далее. А потом логическое И. И всё тип-топ. Это сообщение отредактировал(а) Mayk - 1.9.2005, 06:01 -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
||||
|
|||||
Mayk |
|
|||
![]() ^аВаТаР^ сообщение>> ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: 45 Всего: 134 |
Млин, я идиот. 2**31 битов это 2**28 байт, что офигенно много.
Ладно, где наши не пропадали. Решение в лоб:
довольно быстро находит решение для 0x7FFFFFFF. Если можно позволить себе хранение 131072 интегеров(а именно столько единиц в последовательности длинной 2**31), то вся задача сводится к бинарному поиску индекса по массиву индексов. Если же такая роскошь не позволительна, то можно использовать как массив, так и лобовой способ и способ с sqrt. Сейчас бум сравнивать их по времени: находим 0x7ffffff цифр. При решении с бинарным поиском по массиву затрачивается менее 30 секунд(26-30) При решении с double'ным sqrt менее 40(34-40) (разброс сильный, так как в фоне много программ висят ресурсоемких). Но тут у sqrt много преобразований int<->double происходит. Счас будем избавляться ![]() -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
MOP |
|
||||||||||
![]() Новичок Профиль Группа: Участник Сообщений: 17 Регистрация: 28.8.2005 Репутация: нет Всего: нет |
на сколько я понял, то почти так... т.е. k=n*(n+1)/2 - можно и так (а можно и так:)
k - интерпритирует порядковый номер числа(исчисление с единицы - так надо по условию задачи.. поэтому и формула другая) n - порядковый номер единицы(т.е. какая по счету единица находится в к-ой позиции... исчисление с нуля) при соблюдении всех этих условий мы попадаем в единицу и обратно - при не соблюдении в ноль.... я решил пойти таким путем переписал уравнение:
если его корни будут удавлетворять условиям
то на позиции k - единица решаем уравнение... D=b*b - 4ac; D= 1+8(k-1) = 8k-7 n = ( -1 + sqrt(D) ) / 2 n = ( -1 - sqrt(D) ) / 2 - это уравнение можем сразу отбросить, т.к. оно не удовлетворяет области определения (?) - при всех положительных целых k (это и есть область определения) n удет отрицательным (вот этто-то и не удовлетворяет) а для того, чтобы из первого урвнения получить допустимое n, корень из дискриминанта должен быть целым числом... соответственно и значение под корнем должно быть полным квадратом... вот и получается
можно пойти и другим путем, но я пошел этим и случайно обнаружил проблему при работе с С++... если бы на такое наткнуться в реальном проекте - было бы не сладко... хотя кому нужно вычислять такие громадные корни.... |
||||||||||
|
|||||||||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20580 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 1 Всего: 454 |
Есть библиотеки работы с экстремально большими числами - какие проблемы? хоть миллион цифр... кста, бывает что надобится. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Dov |
|
||||||||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: 15 Всего: 88 |
В твоём примере
попробуй заменить строку
на
-------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
||||||||
|
|||||||||
Siscipsak |
|
|||
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 31.8.2022 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
impaphy |
|
|||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 4.9.2022 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
fedGlasse |
|
|||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 6.9.2022 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
elolcange |
|
|||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 9.9.2022 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
DrawSwade |
|
|||
Новичок Профиль Группа: Участник Сообщений: 5 Регистрация: 12.9.2022 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
![]() ![]() ![]() |
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |