Добрый день. Может кто-нибудь сказать или показать , как на С++ можно получить кубический корень от числа N? Спасибо.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 03:46:44 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Например возведением в степень 1/3: pow(x, 1./3);
бинпоиском
Бинарный поиск для монотонных функций. Кубическим корнем из числа x называется такое число y, что y^3 = x. Сформулируем задачу так: для данного вещественного числа x (x ≥ 1) найти кубический корень с точностью не менее 5 знаков после точки. Функция при x ≥ 1, ограничена сверху числом x, а снизу единицей. Таким образом, за нижнюю границу мы выбираем 1, за верхнюю само число x. После этого делим текущий отрезок пополам, возводим середину в куб и если куб больше x, то заменяем верхнюю грань, иначе нижнюю. Код будет выглядеть следующим образом: r = x ; l = 1 ; while (fabs(l-r)>eps) { m = ( l+r ) /2 ; if (m*m*m<x) l=m ; else r=m ; } Для того чтобы пользоваться функцией fabs, необходимо подключить библиотеку math.h.
Бинпоиск в таких случаях работает долго, уточняя по одной цифре в двоичном разложении за раз. Лучше уж итерационный метод, например Ньютона:
Ищем корень кубический из A , в качестве x0 берём что-то приближённое. Итерационный метод возводит точность в квадрат, а не умножает на 2, как бинпоиск.
Удивляюсь. Я воспринял исходный вопрос как то, что автор не знает pow. Или не слышал о log/exp. Или не подозревает, что извлечь корень кубический, это то же самое, что возвести в степень 1.0/3.
А тут такие серьёзные люди предлагают алгоритмические методы решения задачи.
Вопрос же был не «как получить кубический корень», а «как на С++ можно получить кубический корень».
Может, правда, вопрос был об очень большом целом N, но, тогда действительно только дихотомия и длинное умножение, думаю.
Разве в длинной арифметике не лучше итерационным с делением?
А разве он будет сходиться на целых числах? Да и писать длинное деление как-то не клево. А вот в вещественной... Хотя тут уже без BigDecimal печально...
Будет выдаваться результат с точностью до +-1, а уж три значения можно и проверить.
Да, согласен. Там же только делить на 2 надо, а это за O(N).
UPD. Не правильно воспринял. Можно же сделать дихотомию без длинного умножения, только с делением на 2, что за O(N). Любое другое длинное деление не на заранее известную константу, действительно напрягает.
Так возведение в квадрат идёт за O(N2) , как и длинное деление. Где здесь лучше?
Длинное деление очень просто пишется в варианте N^2 * log2(base). В "кнутовском" варианте за O(n^2) код сложнее, как и сама идея, но для кого-то может быть тоже не сложно пишется.
cbrt(n), не?